这一章我们来看队列
队列的概念：
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。
其实我们来对比栈，栈的特点是只能在一端进行操作的，而队列是一端插入一端删除。
用一句很有歧义却很形象的话来讲两者的区别就是：栈就是插进去抽出来，而队列是插进去吐出来。
我们还是上图来更加直观的看队列
队列分为两种，一种是顺序队列，一种是循环队列。
其实从存储结构上讲，队列也分为两种，一种是顺序队列，一种是链队列。
如果从存储上加以区分的话，在实际的物理空间中，数据集中存储的队列是顺序队列，分散存储的队列是链队列。
顺序队列的简单实现（我们要采用数组）
初始是这样的，因为还没有存放任何元素
我们来看入队的过程
我们来看出队的过程
其实这里涉及假溢出和真溢出
我们来解释下
假溢出：就是明明存储空间还有，却放不下数据了。
真溢出：很好理解，就是真的插不进去了。因为空间真的不够用了，被塞满了。
我们来看顺序表实现队列的操作
上代码：
我们这样实现就很简单，避免了使用结构体
#include <stdio.h> int PushQueue(int *a,int rear,int data){ a[rear]=data; rear++; return rear; } void DeQueue(int *a,int front,int rear){ while (front!=rear) { //当font=rear时，我们表示他为空 printf("出队元素：%d\n",a[front]); front++; } } int main() { int a[100]; int front,rear; //设置队头指针和队尾指针，当队列中没有元素时，队头和队尾指向同一块地址 front=rear=0; //入队 rear=PushQueue(a, rear, 1); rear=PushQueue(a, rear, 2); rear=PushQueue(a, rear, 3); rear=PushQueue(a, rear, 4); //出队 DeQueue(a, front, rear); return 0; }
这样的顺序表的实现方式存在假溢出的假象。这样太浪费空间了。我我们想了一种办法，就是采用循环的结构，就是把它看做一个头尾相接循环结构。
我们要判断队满和队空，但是我们发现，在队满和队空的情况下，都存在head=tail的情况，或者是font=rear。我们想办法进行区分。
两种办法：
1：少用一个数据元素的空间，当队尾指针所指的空闲单元的后继单元是队头元素所在的单元时，我们就认为队满，不再插入新的元素。我们有这样判断（Q.rear+1）%MAXSIZE==Q.font，如果满足这个条件，队就满了。队空的条件不受影响，就是Q.rear == Q.font.
我们来看循环队列的结构体定义
#define MAXSIZE 1024 typedef int elemtype typedef struct SequenQueue { elemtype data[MAXSIZE]; int font ; int rear; } SequenQueue;
我们来看一些操作
1：初始化
SequenceQueue *Init_SequenQueue() { SequenQueue * Q; //定义循环队列的指针变量 Q = (SequenQueue *)malloc (sizeof(SquenQueue)) if(Q!=NULL){ Q->font =0; Q->rear =0; } return Q; }
2:判断队列是否为空
int Sequen_Empty(SequenQueue * Q) { if(Q->rear==Q->font){ return 1; } else { return 0; } }
其他的操作都是大同小异的，注意用到空间申请函数了，我们要加上相应的头文件。
能够把复杂的东西做的简单才是最明智的。
我们还是不用结构体。。来看一个完整代码。
下面展示一些 内联代码片。
#include <stdio.h> #define max 5//表示顺序表申请的空间大小 int enQueue(int *a,int front,int rear,int data){ //添加判断语句，如果rear超过max，则直接将其从a[0]重新开始存储，如果rear+1和front重合，则表示数组已满 if ((rear+1)%max==front) { printf("空间已满"); return rear; } a[rear%max]=data; rear++; return rear; } int deQueue(int *a,int front,int rear){ //如果front==rear，表示队列为空 if(front==rear%max) { printf("队列为空"); return front; } printf("%d ",a[front]); //front不再直接 +1，而是+1后同max进行比较，如果=max，则直接跳转到 a[0] front=(front+1)%max; return front; } int main() { int a[max]; int front,rear; //设置队头指针和队尾指针，当队列中没有元素时，队头和队尾指向同一块地址 front=rear=0; //入队 rear=enQueue(a,front,rear, 1); rear=enQueue(a,front,rear, 2); rear=enQueue(a,front,rear, 3); rear=enQueue(a,front,rear, 4); //出队 front=deQueue(a, front, rear); //再入队 rear=enQueue(a,front,rear, 5); //再出队 front=deQueue(a, front, rear); //再入队 rear=enQueue(a,front,rear, 6); //再出队 front=deQueue(a, front, rear); front=deQueue(a, front, rear); front=deQueue(a, front, rear); front=deQueue(a, front, rear); return 0; }
如果不是很理解结构体，用这种方式其实也是同样的道理。
我们来看链栈如何实现
链队列的初始状态
初始状态，尾指针和头指针都指向头结点。
我们来看结构；
typedef struct QNode{ int data; struct QNode * next; }QNode;
1：初始化：
下面展示一些 内联代码片。
QNode * initQueue(){ //创建一个头节点 QNode * queue=(QNode*)malloc(sizeof(QNode)); //对头节点进行初始化 queue->next=NULL; return queue;
2：入队操作：
下面展示一些 内联代码片。
QNode* enQueue(QNode * rear,int data){ //1、用节点包裹入队元素 QNode * enElem=(QNode*)malloc(sizeof(QNode)); enElem->data=data; enElem->next=NULL; //2、新节点与rear节点建立逻辑关系 rear->next=enElem; //3、rear指向新节点 rear=enElem; //返回新的rear，为后续新元素入队做准备 return rear; }
3:出队操作
我们来看代码：
下面展示一些 内联代码片。
void DeQueue(QNode * top,QNode * rear){ if (top->next==NULL) { printf("队列为空"); return ; } // 1、 QNode * p=top->next; printf("%d",p->data); top->next=p->next; if (rear==p) { rear=top; } free(p); }
这里和链表真的太像了
我们来看完整代码；
#include <stdio.h> #include <stdlib.h> typedef struct QNode{ int data; struct QNode * next; }QNode; QNode * initQueue(){ QNode * queue=(QNode*)malloc(sizeof(QNode)); queue->next=NULL; return queue; } QNode* enQueue(QNode * rear,int data){ QNode * enElem=(QNode*)malloc(sizeof(QNode)); enElem->data=data; enElem->next=NULL; //使用尾插法向链队列中添加数据元素 rear->next=enElem; rear=enElem; return rear; } QNode* DeQueue(QNode * top,QNode * rear){ if (top->next==NULL) { printf("\n队列为空"); return rear; } QNode * p=top->next; printf("%d ",p->data); top->next=p->next; if (rear==p) { rear=top; } free(p); return rear; } int main() { QNode * queue,*top,*rear;申明头结点，top指针，和尾指针。 queue=top=rear=initQueue();//创建头结点 //向链队列中添加结点，使用尾插法添加的同时，队尾指针需要指向链表的最后一个元素 rear=enQueue(rear, 1); rear=enQueue(rear, 2); rear=enQueue(rear, 3); rear=enQueue(rear, 4); //入队完成，所有数据元素开始出队列 rear=DeQueue(top, rear); rear=DeQueue(top, rear); rear=DeQueue(top, rear); rear=DeQueue(top, rear); rear=DeQueue(top, rear); return 0; }
