@[toc]
本篇文章将讲解队列。
队列的定义
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。
可以将队列类比成日常生活中的排队，比如食堂派对打饭，银行排队处理业务等。
比如下图的队列：
队列只允许从队尾(rear)插入，从队头(front)删除，所以对于队列结构，先插入的元素总是先被删除。
队列的抽象数据类型定义
定义如下：
ADT Queue{
数据对象：D = {
ai|ai∈ElemSet,i = 1,2,...,n-1,n,n>=0}
数据关系：R = {
<ai-1,ai>|ai-1,ai∈D,i=2,3,...,n-1,n}
基本操作：
InitQueue(&Q);//初始化对了
DestroyQueue(&Q);//销毁队列
ClearQueue(&Q);//清空队列
QueueLength(Q);//求队列长度
GetHead(Q,&val);//求队头元素
EnQueue(&Q,val);//入队
DeQueue(&Q,&val);//出队
......
}ADT Queue
AI 代码解读
队列的顺序实现
队列同样可以顺序实现和链式实现，分别称作：顺序队列和链式队列。
先来说说队列的顺序实现，可以通过数组实现，顺序队列的结构定义如下：
typedef struct {
int *base;//初始化的动态分配存储空间
int front;//头指针
int rear;//尾指针
}Queue,*PQueue;
AI 代码解读
注意这里的头指针和尾指针并不是真正的指针，它只是数组的下标，起一个类似于指针的作用而已。
初始情况下，队列为空该如何表示呢？
队列由数组实现，所以数组为空即为队列空，我们将头指针和尾指针都置为0，即表示空队列。
顺序队列的基本操作
入队
假设如下的一个队列：
如何实现入队操作呢？
将元素放入队尾下标的位置，然后让队尾下标加1，即：base[rear] = val;rear++。
此时队列已满，尾指针rear的值为5，所以判断队列是否满，就看队尾指针rear的值是否等于数组的最大容量，即：rear == MAXSIZE。
出队
继续看这个队列：
如何实现出队呢？
取出队头下标对应的元素值，然后队头指针加1，即：val = base[front];front++。
我们继续将队列元素出队，直到最后一个元素也出队，此时队头指针和队尾指针相等：
所以，判断队列是否空的条件为：rear == front。
普通顺序队列的缺陷
不过通常我们都不会使用这样的队列来解决实际问题，为什么呢？我们来看看它的缺陷。
假设有下面的一个队列：
该队列是如何形成的呢？首先有一个空队列，然后执行入队操作，直到队满，此时尾指针rear的值为5；然后执行三次出队操作，状态就如上图。
试想一下，现在还能执行入队操作吗？
在入队操作执行之前，我们首先要判断队列是否满，如果满，则无法入队。
队列是否满的条件是rear == MAXSIZE，很显然，这里表示队满了。但实际上，队列满了吗？当然没满，下面还有三个空闲位置呢。
所以，普通队列存在着一个溢出的问题。
若头指针front == 0，而尾指针rear == MAXSIZE，此时表示队列真的满了，这时候入队是真溢出。
若头指针front≠0，而尾指针rear == MAXSIZE，此时队列并没有真的满，这时候后入队是假溢出。
循环队列
为了解决假溢出的问题，我们可以将普通的队列改造成循环队列。
我们可以让队列中的空间循环使用，比如下面的情况：
此时判断该队列是满的，如何循环利用起下面的空间呢？
当rear的值为MAXSIZE的时候，我们可以将rear的值赋值为0，使尾指针rear重新指回到数组开头，如果rear所指的位置是空着的，就可以继续使用了；头指针front也是如此。
因为队头和队尾指针可以循环移动，所以空循环队列和满循环队列的判断条件就无法确定了，为此，我们可以牺牲队列中的一个空间，来区分队满和队空。比如下面的情况：
少用一个空间，而此时判断队列是否满的情况就是(rear + 1) % MAXSIZE == front。
循环顺序队列的基本操作
下面介绍循环队列的一些基本操作。
顺序队列的初始化
初始化操作就是开辟一段数组内存，然后将队头和队尾指针置为0。
Queue InitQueue(){
Queue q;
//分配数组内存
q.base = (int*) malloc(sizeof(int) * MAXSIZE);
if(q.base == NULL){
exit(-1);
}
q.front = q.rear = 0;
return q;
}
AI 代码解读
求顺序队列的长度
普通的队列求长度只需要用队尾指针减去队头指针即可，但是循环队列的指针可以随意指向，所以很可能出现相减得负数的情况，为此，我们需要对结果进行一定的处理：
int QueueLength(Queue q){
return (q.rear - q.front + MAXSIZE) % MAXSIZE;
}
AI 代码解读
顺序队列的入队操作
循环队列的入队操作和普通队列没有什么区别，区别在于要针对队尾指针做循环处理。
int EnQueue(PQueue q,int val){
//判断队列是否满
if((q->rear + 1) % MAXSIZE == q->front){
return -1;
}
q->base[q->rear] = val;
q->rear = (q->rear + 1) % MAXSIZE;
return 1;//入队成功，返回1
}
AI 代码解读
这里巧妙地使用取模操作，使尾指针rear在0到MAXSIZE之间循环。
顺序队列的出队操作
出队操作就没有什么说的了，细节都已经讲明白了。
int OnQueue(PQueue q,int *val){
//判断队列是否空
if(q->front == q->rear){
return -1;
}
*val = q->base[q->front];
q->front = (q->front + 1) % MAXSIZE;
return 1;//出队成功，返回1
}
AI 代码解读
取顺序队列的队头元素
取队头元素很简单， 直接输出队头指针对应的元素值即可：
int GetHead(Queue q){
//判断队列是否空
if(q.front == q.rear){
return -1;
}
return q.base[q.front];
}
AI 代码解读
队列的链式实现
和其它数据结构一样，顺序队列的缺点是存储容量不灵活，所以如果对存储容量有要求，就需要使用链式队列。
下面是链式队列的结构定义：
//结点
typedef struct Node{
int data;
struct Node *next;
}Node,*PNode;
//队列
typedef struct {
PNode front;//头指针
PNode rear;//尾指针
}Queue,*PQueue;
AI 代码解读
链式队列的基本操作
下面介绍链式队列的一些基本操作。
链式队列的初始化
void InitQueue(PQueue q){
//初始队头和队尾指针均指向头结点
q->front = q->rear = (PNode) malloc(sizeof(Node));
if(q->front == NULL || q->rear == NULL){
exit(-1);
}
q->front->next = NULL;//队头结点指针域置为NULL
}
AI 代码解读
链式队列的初始化也非常简单，首先开辟一个空间作为头结点，然后让队头队尾指针均指向头结点，最后让队头结点指针域赋值为NUULL。
链式队列的销毁
void DestroyQueue(PQueue q){
PNode p;
//当前结点是否为空
while(q->front != NULL){
//保存当前结点
p = q->front->next;
free(p);//释放内存
q->front = p;
}
}
AI 代码解读
链式队列的入队操作
void EnQueue(PQueue q,int val){
//创建新结点
PNode p = (PNode) malloc(sizeof(Node));
if(p == NULL){
exit(-1);
}
p->data = val;
p->next = NULL;//队尾结点指针域为NULL
q->rear->next = p;//将队尾结点指向新结点
q->rear = p;//队尾指针为新结点
}
AI 代码解读
在队尾插入结点。
链式队列的出队操作
int OnQueue(PQueue q,int *val){
PNode p;
//判断队列是否空
if(q->front == q->rear){
return -1;
}
p = q->front->next;
*val = p->data;
q->front->next = p->next;
if(q->rear == p){
q->rear = q->front;
}
free(p);
return 1;//出队成功，返回1
}
AI 代码解读
在队头删除结点。
这些操作都非常简单，就不一一分析了，会发现，有链表的基本，再来学习这些东西会非常简单。
源代码
顺序队列代码
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#define MAXSIZE 10
typedef struct {
int *base;//初始化的动态分配存储空间
int front;//头指针
int rear;//尾指针
}Queue,*PQueue;
int GetHead(Queue q){
//判断队列是否空
if(q.front == q.rear){
return -1;
}
return q.base[q.front];
}
int EnQueue(PQueue q,int val){
//判断队列是否满
if((q->rear + 1) % MAXSIZE == q->front){
return -1;
}
q->base[q->rear] = val;
q->rear = (q->rear + 1) % MAXSIZE;
return 1;//入队成功，返回1
}
int OnQueue(PQueue q,int *val){
//判断队列是否空
if(q->front == q->rear){
return -1;
}
*val = q->base[q->front];
q->front = (q->front + 1) % MAXSIZE;
return 1;//出队成功，返回1
}
int QueueLength(Queue q){
return (q.rear - q.front + MAXSIZE) % MAXSIZE;
}
Queue InitQueue(){
Queue q;
//分配数组内存
q.base = (int*) malloc(sizeof(int) * MAXSIZE);
if(q.base == NULL){
exit(-1);
}
q.front = q.rear = 0;
return q;
}
AI 代码解读
链式队列代码
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#define MAXSIZE 10
//结点
typedef struct Node{
int data;
struct Node *next;
}Node,*PNode;
//队列
typedef struct {
PNode front;//头指针
PNode rear;//尾指针
}Queue,*PQueue;
int OnQueue(PQueue q,int *val){
PNode p;
//判断队列是否空
if(q->front == q->rear){
return -1;
}
p = q->front->next;
*val = p->data;
q->front->next = p->next;
if(q->rear == p){
q->rear = q->front;
}
free(p);
return 1;//出队成功，返回1
}
void EnQueue(PQueue q,int val){
//创建新结点
PNode p = (PNode) malloc(sizeof(Node));
if(p == NULL){
exit(-1);
}
p->data = val;
p->next = NULL;//队尾结点指针域为NULL
q->rear->next = p;//将队尾结点指向新结点
q->rear = p;//队尾指针为新结点
}
void DestroyQueue(PQueue q){
PNode p;
//当前结点是否为空
while(q->front != NULL){
//保存当前结点
p = q->front->next;
free(p);//释放内存
q->front = p;
}
}
void InitQueue(PQueue q){
//初始队头和队尾指针均指向头结点
q->front = q->rear = (PNode) malloc(sizeof(Node));
if(q->front == NULL || q->rear == NULL){
exit(-1);
}
q->front->next = NULL;//队头结点指针域置为NULL
}
AI 代码解读
