目录
引言
队列的性质
队列的基本操作
初始化
判空
销毁
队列的长度
插入
删除
返回队头元素
循环队列
假溢出
空与满的判定
实现
初始化
插入
判空
销毁
删除
返回队列长度
返回队列头元素
判满
引言
队列和栈一样，也是数据结构的一种，可以用数组实现，也可以用链表实现。它常用于各种应用程序中，包括操作系统、网络通信等。一个最典型的例子就是操作系统中的作业排队。在允许多道程序运行的计算机系统中，同时有几个作业运行。如果运行的结果多需要通过通道输出，那就要按请求输出的先后顺序排队。每当通道传输完毕可以接受新的输出任务时，队头的作业先从队列中退出作输出操作。
队列的性质
队列的性质与栈相反，它是一种“先进先出”的线性表。它只允许在队列的一端进行插入，在另一端进行删除。允许插入的一端叫队尾，允许删除的一端叫队头。
队列的基本操作
队列的操作和栈的操作类似，下面将以链式队列为例，逐一讲解各个操作。因为是用单链表实现队列，如果仅仅记录队头，那么在插入数据时必须得遍历一遍链表，找到队列的尾，才能链接上新的结点，这是一个不小的消耗，所以，除了对链表的结点封装成一个结构体(A)外，还可以再封装一个结构体(B)，B结构体成员里包含结构体A。这么说很抽象，还是看代码吧！
typedef int QueueDataType;
typedef struct QueueNode
{
QueueDataType data;
struct QueueNode* next;
}QueueNode;
typedef struct Queue
{
QueueNode* phead;//指向链表头
QueueNode* ptail;//指向链表尾
int size;//记录长度
}Queue;这样就方便对队列进行维护了。
初始化
初始化时，可以malloc出一些空间给队列，也可以不用，等到插入时再开辟空间也行，都无可厚非，我这里选择后者。
代码：
void QueueInit(Queue* pq)
{
assert(pq);
pq->phead = NULL;
pq->ptail = NULL;
pq->size = 0;
}判空
链表为空的标志是size == 0.
代码：
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->size == 0;
}销毁
因为队列底层是用单链表实现，所以在销毁时得一个节点一个节点的释放。在销毁节点A前，需要先记录A的下一个结点，否则把A释放后，将找不到它的下一个节点。销毁链表时还有一个细节，当只有一个节点时，free头结点后，要将头指针和尾指针都置空，如果仅把头指针置空，那么尾指针就是野指针。
代码：
void QueueDestroy(Queue* pq)
{
assert(pq);
while (pq->phead)
{
QueueNode* next = pq->phead->next;
free(pq->phead);
pq->phead = next;
if (next == NULL) pq->ptail = NULL;//只有一个节点时，防止ptail为野指针
}
}队列的长度
size就是队列的长度，返回size即可。
代码：
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}插入
由于定义了尾指针，所以在插入前，就不需要遍历链表找尾了。第一种情况，链表不为空，不需要调整头指针，直接将新节点链接到尾节点后面即可，但不要忘了size++。第二种情况，链表为空，插入时，头指针和尾指针的指向都需要修改。
代码：
//创建节点
QueueNode* BuyNode(QueueDataType x)
{
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
if (newnode == NULL)
{
perror("malloc fail");
return NULL;
}
newnode->next = NULL;
newnode->data = x;
return newnode;
}
void QueuePush(Queue* pq, QueueDataType x)
{
assert(pq);
QueueNode* newnode = BuyNode(x);
if (pq->phead == NULL)
{
pq->phead = pq->ptail = newnode;
}
else
{
pq->ptail->next = newnode;
pq->ptail = newnode;//更新尾指针
}
pq->size++;
}
删除
第一点，当队列为空时，无法删除。第二，队列的删除操作是在队头进行的，所以需要更新头指针的指向。最后，不要忘了size--。
代码：
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
QueueNode* newhead = pq->phead->next;
free(pq->phead);
pq->phead = newhead;
pq->size--;
}返回队头元素
通过头指针便可以访问到队头元素。当队列为空时，无法返回。
代码：
QueueDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->phead->data;
}循环队列
循环队列是把顺序队列首尾相连，把存储队列元素的数组从逻辑上看成一个环，成为循环队列。在物理上，它就是个数组，在逻辑上，我们要把它想象成一个圆环。循环队列的实现一般定义两个指针，头指针front和尾指针rear，front和rear开始都赋为0，每插入一个元素，rear++，每删除一个元素，front++，这和顺序栈如出一辙。front指向头，rear指向尾元素的下一个位置。
循环队列遵循先进先出的原则。
从队尾入队列，从队头出队列。
用数组实现的循环队列支持下标的随机访问，访问速度快。
假溢出
请看上图，往队列里插入8个元素使队列呈满的状态，接着删除两个元素，此时，队列里有两个空位，但这两个空位是无法使用的，因为rear已经越界了，无法再继续插入。这种现象就叫作“假溢出”。这就导致了空间的浪费。
克服假溢出的方法有两种，第一种，把数组元素往前挪动，使其起始位置从0开始，显然，这种方法是很浪费时间的。第二种方法，就是使用循环队列，当存到最后一个地址后，下一个存放的位置就是从0开始。这也使得用数组实现的循环队列长度是固定的，不能动态增长。
空与满的判定
循环队列的循环效果是用取余运算来实现的。在实现循环队列之前，我们首先搞清楚下面的问题——如何区分循环队列的空与满。
对比图a和图d1，我们发现，当循环队列为空时，存在front == rear，当循环队列满时，也存在front == rear，这样，就导致无法区分循环队列的空和满。解决方案有两种，第一种，令设一个变量来记录队列中的元素个数，以区分空和满；第二种，留出一个元素的空间，当队列头指针在队列尾指针的下一位置时，队列为满，队列为空的标志是front == rear，这样就将空和满这两种情况给区分开了。
实现
#define MIXSIZE 10
typedef int CQueueDataType;
typedef struct CycleQueue
{
CQueueDataType a[MIXSIZE];
int front;
int rear;
}CycleQueue;初始化
代码：
void CycleQueueInit(CycleQueue* pcq)
{
assert(pcq);
pcq->front = 0;
pcq->rear = 0;
}插入
如果队列已满，那么将无法插入。因为循环队列是定长的，长度不可动态增长。往队列中插入数据时还有以下细节：
第一种情况，直接rear++即可。第二种情况，在插入数据以后，如果直接rear++，将会越界，需要做特殊处理。
以上两种情况的统一处理方式为：
rear = （rear + 1）% MIXSIZE；
当rear为最后一个元素的下标时，rear + 1 就是MIXSIZE，再模上MIXSIZE，正好为0，回到了数组的起始位置。由于取模操作本质上是去掉整除的部分，所以当rear < MIXSIZE时，进行取模操作后也可以得到正确的结果。
代码：
void CycleQueuePush(CycleQueue* pcq, CQueueDataType x)
{
assert(pcq);
assert(!CycleQueueFull(pcq));
pcq->a[pcq->rear] = x;
pcq->rear = (pcq->rear + 1) % MIXSIZE;
}判空
循环队列为空的标志是：front == rear。
代码：
bool CycleQueueEmtpy(CycleQueue* pcq)
{
assert(pcq);
return pcq->front == pcq->rear;
}销毁
代码：
void CycleQueueDestroy(CycleQueue* pcq)
{
assert(pcq);
free(pcq->a);
pcq->front = 0;
pcq->rear = 0;
}删除
由于循环队列是用数组实现，所谓的删除并不是抹除数据，而是通过控制下标，让该元素在删除后无法被访问到。这里和插入时一样，有一个很类似的细节：
front++后可能会越界，统一的处理方式如下：
front = （front + 1）% MIXSIZE；
代码：
void CycleQueuePop(CycleQueue* pcq)
{
assert(pcq);
pcq->front = (pcq->front + 1) % MIXSIZE;
}返回队列长度
求循环队列长度的公式：
len = (rear - front + MIXSIZE) % MIXSIZE;
代码：
int CycleQueueLen(CycleQueue* pcq)
{
assert(pcq);
return (pcq->rear - pcq->front + MIXSIZE) % MIXSIZE;
}返回队列头元素
队列头元素的下标为front。
代码：
CQueueDataType CycleQueueFront(CycleQueue* pcq)
{
assert(pcq);
return pcq->a[pcq->front];
}判满
循环队列满的标志：
（rear + 1）% MIXSIZE == front；
代码：
bool CycleQueueFull(CycleQueue* pcq)
{
assert(pcq);
return (pcq->rear + 1) % MIXSIZE == pcq->front;
}完！
————————————————————————————————————————————————————————————
