1.队列的概念及结构

队列对于临时数据的处理也十分有趣，它跟栈一样都是有约束条件的数组（或者链表）。区别在于我们想要按什么顺序去处理数据，而这个顺序当然是要取决于具体的应用场景。

你可以将队列想象成是电影院排队。排在最前面的人会最先离队进入影院。套用到队列上，就是首先加入队列的，将会首先从队列移出。

因此计算机科学家都用缩写“FIFO”（first in, first out）先进先出，来形容它。

与栈类似，队列也有 3个限制（但内容不同）。

  ▶ 只能在末尾插入数据（这跟栈一样）。
  ▶ 只能读取开头的数据（这跟栈相反）。
  ▶ 只能移除开头的数据（这也跟栈相反）。

下面来看看它是怎么运作的，先准备一个空队列。

首先，插入 5（虽然栈的插入就叫压栈，但队列的插入却没有固定的叫法，一般可以叫放入、
加入、入队）。

然后，插入 9。 

接着，插入 100。 

目前为止，队列表现得还跟栈一样，但要是移除数据的话，就会跟栈反着来了，因为队列是从开头移除数据的。

想移除数据，得先从 5 开始，因为开头就是它。 

接着，移除 9。 

这样一来，队列就只剩下 100了。 

2.队列的实现

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

2.1队列结构的定义

typedef struct Queue
{QNode* head; //记录队头的位置QNode* tail; //记录队尾的位置int size; //记录队列的长度
}Queue;

2.2队列中存储数据的结点

typedef int QDataType;typedef struct QueueNode
{QDataType data; //存储的数据struct QueueNode* next; //记录下一个结点的位置
}QNode;

2.3函数接口的实现

首先是在Queue.h文件中进行函数声明

Queu.h

#pragma once
#include
#include
#include
#includetypedef int QDataType;typedef struct QueueNode
{QDataType data; //存储的数据struct QueueNode* next; //记录下一个结点的位置
}QNode;typedef struct Queue
{QNode* head; //记录队头的位置QNode* tail; //记录队尾的位置int size; //记录队列的长度
}Queue;//队列的初始化
void QueueInit(Queue* pq);
//释放malloc出的内存
void QueueDestroy(Queue* pq);
//入队
void QueuePush(Queue* pq, QDataType x);
//出队
void QueuePop(Queue* pq);
//获取队头的数据
QDataType QueueFront(Queue* pq);
//获取队尾的数据
QDataType QueueBack(Queue* pq);
//判断队列是否为空
bool QueueEmpty(Queue* pq);
//队列数据的个数
int QueueSize(Queue* pq);

在Queue.c文件中进行函数的定义

Queue.c

#define _CRT_SECURE_NO_DEPRECATE 1
#include"Queue.h"void QueueInit(Queue* pq)
{assert(pq);pq->head = NULL;pq->tail = NULL;pq->head = 0;
}void QueueDestroy(Queue* pq)
{assert(pq);//用cur找尾QNode* cur = pq->head;while (cur){QNode* del = cur;cur = cur->next;free(del);}pq->size = 0;pq->head = pq->tail = NULL;
}void QueuePush(Queue* pq,QDataType data)
{assert(pq);QNode* newNode = (Queue*)malloc(sizeof(Queue));if (newNode == NULL){perror("malloc fail");exit(-1);}//初始化结点newNode->data = data;newNode->next = NULL;if (pq->tail == NULL){//队列为空时入队pq->head = newNode;pq->tail = newNode;}else{//队列不为空时入队pq->tail->next = newNode;pq->tail = newNode;}pq->size++;
}void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq->head->next == NULL){//只有一个结点时free(pq->head);pq->head = pq->tail = NULL;}else{//一般情况QNode* del = pq->head;pq->head = pq->head->next;free(del);}pq->size--;
}QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}bool QueueEmpty(Queue* pq)
{assert(pq);//return pq->size==0;return pq->head == NULL && pq->tail == NULL;
}int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}