C与指针-第十七章-队列

前面学习了堆栈的操作，本章主要来学习队列的相关操作。

队列的特点：

1)先进先出(First in First Out FIFO)
例如排队等餐，先排的人拿到快餐后，离开这个队伍，后面一个人前进一位，新来的人在队伍的最后面加入
2)队列只允许在队首进行删除操作，队尾进行添加操作

队列的数据存储方式主要有下面两种方式：

1）动态数组存储
2）链表存储

队列的几个操作：

1)初始化队列：
队列的内容进行初始化，如果是动态申请空间队列，还需要申请空间
2)进队列:
数据从队尾加入
3)出队列:
数据从队首删除
4)判断队列是否为空:
检查队列中是否还有元素
5)判断队列是否已满：
检查队列中元素的个数是否已达到上限

接下来通过代码示例来实现两种存储方式的队列，为了方便操作，这里的数据都使用int类型

1.动态数组存储

queue.h

#ifndef QUEUE_H
#define QUEUE_H

#include <stdio.h>
#include <stdlib.h>

/*初始化并创建队列*/
int init_array_queue(size_t size);

/*销毁队列*/
int destroy_array_queue();

/*入队列*/
void enqueue(int value);

/*出队列*/
int dnqueue();

/*队首元素*/
int queue_top();

/*队列是否为空*/
int is_queue_empty();

/*队列是否已满*/
int is_queue_full();

#endif

###
queue.c

#include "queue.h"

/*保存数据的数组*/
static int *queue_arr=NULL;

/*队列的实际大小*/
static int count;

#define QUEUE_SIZE    100  /*队列中元素数量的限制*/
#define true 1
#define false 0


/*初始化并创建队列*/
int init_array_queue(size_t size){

    queue_arr = (int *)malloc(sizeof(int) * size);
    if (queue_arr == NULL)
    {
        printf("arr malloc error!");
        return false;
    }
    count = 0;
    return true;
}

/*销毁队列*/
int destroy_array_queue(){

  if (queue_arr)
  {
     free(queue_arr);
     queue_arr = NULL;
     count = 0;
  }
  return true;
}

/*入队列*/
void enqueue(int value){

  queue_arr[count++] = value;
}

/*出队列*/
int dnqueue(){

    int i = 0;;
    int ret = queue_arr[0];

    count--;
    while (i++<count)
        queue_arr[i-1] = queue_arr[i];

    return ret;
}

int queue_top(){

  return queue_arr[0];
}

/*队列是否为空*/
int is_queue_empty(){

  return count == 0;
}

/*队列是否已满*/
int is_queue_full(){

  return count == QUEUE_SIZE -1;
}

int main(void){

  init_array_queue(QUEUE_SIZE);
  enqueue(10);
  enqueue(20);
  int top = queue_top();
  printf("queue top is %d\n",top);
  destroy_array_queue();
  return 0;
}

2.链表存储

#include <stdio.h>
#include <stdlib.h>

/*单链表节点*/
typedef struct  NODE
{
    int data;
    struct NODE* next;
}Node;

/*表头*/
static Node *phead = NULL;

/*创建节点*/
static Node* create_node(int data){

    Node *pnode = NULL;
    pnode = (Node*)malloc(sizeof(Node));
    if(!pnode)
    {
        return NULL;
    }
    pnode->data = data;
    pnode->next = NULL;
    return pnode;
}

/*销毁链表*/
static int destory_link(){

    Node *pnode = NULL;
    while(phead != NULL)
    {
        pnode = phead;
        phead = phead->next;
        free(pnode);
    }
    return 0;
}

/*入队列*/
void enqueue(int data){

  if (!phead)
  {
      phead = create_node(data);
      return;
  }
  Node *pnode = create_node(data);
  Node *pend = phead;
  while(pend->next)
  {
      pend = pend->next;
  }
  pend->next = pnode;
}

/*出队列*/
int dnqueue(){

 int ret = phead->data;
 Node *pnode = phead;
 phead = phead->next;
 free(pnode);
 return ret;
}

int queue_top(){

  return phead->data;
}

/*返回链表节点个数*/
int size(){

    int count = 0;
    Node *pend = phead;
    while(pend)
    {
        pend = pend->next;
        count++;
    }
    return count;
}

/*队列是否为空*/
int is_queue_empty(){

  return size() == 0;
}

int main(void){

  enqueue(10); /*入队*/
  enqueue(20);
  int top = queue_top(); /*返回队首元素*/
  printf("queue top is %d\n",top);
  destory_link(); /*销毁队列*/
  return 0;
}