何为队列
队列(Queue)同栈一样都是一种操作受限制的线性表，他与栈不同的是，队列只允许在表的一端进行插入数据，另一端进行删除数据。就好像我们现实生活中排队，一端入队，另一端出队，所以队列与栈不同的最大特点就是先进先出(FIFO)。
关于队列一些常见概念：
队头(front):允许删除的一端，也叫队首
队尾：允许插入的地方
空队列：不含任何元素的空表
入队：插入元素
出队：删除(弹出)元素
队列的存储结构
队列的顺序存储
队列的顺序存储结构实现是指分配一块连续的存储单元存放队列元素，并附有两个指针头指针(front)和尾指针(rear)；front指向队首元素，rear指向队尾后一个位置。所以当rear = front时，则队列为空(非循环链表)。
代码实现：
#include<stdio.h>
#include<stdlib.h>
typedef struct queue{
int *data;
int front, rear, size, cmp;
}queue;
这里的size只是为了理解方便加入，因为我打算创建一个动态顺序表，所以需要一个cmp来记录容量大小。
可以很容易知道，当front值为0，rear值为cmp的时候视为队满，但实际上，我们在之前说过，队列的队尾指针是在数据后的1位，所以说这时候的数据溢出并不是真的溢出，而是一种假溢出。
另外我们申请的是一个一维数组的空间作为队列空间，很容易想到如果频繁的进行出队入队操作，那么front会一直向后移动，那么前面的空间就会得不到利用，造成极大的空间浪费。所以为了充分利用空间资源，我们需要从逻辑上把存储存储队列视为一个环，当rear移动到空间上限时，移动到空间开始的地址。那么代码实现的话，可以采用对cmp取余的做法实现，但是由于我设置了size，所以我的实现方式更简单粗暴一点。
queue *initQueue(int cmp){
queue *q = (queue *)malloc(sizeof(queue));
q->data = (int *)malloc(sizeof(int) * cmp);
q->cmp = cmp;
q->size = 0;
q->front = 0;
q->rear = 0;
return q;
}
void deleteQueue(queue *q){
free(q->data);
free(q);
}
首先依然是常规的初始化和销毁
int getTop(queue *q){
if(q->size == 0){
return 0;
}
printf("the top is:%d\n", q->data[q->front]);
return q->data[q->front];
}
然后操作方法和栈一样，取队首元素，入队，出队的操作。
void push(queue *q, int val){
if(q->size + 1 == q->cmp){ //扩容
int *t = (int *)malloc(sizeof(int) * q->cmp * 2) ;
for(int i = 0;i < q->size; i++){
*(t+i) = q->data[(q->front + i) % q->cmp];
}
free(q->data); //释放原来空间内存
q->data = t; //指向新数据域
q->front = 0;
q->rear = q->front + q->size;
q->cmp *= 2;
printf("exp!\n");
}
q->data[q->rear] = val; //入队
q->rear++;
if(q->rear == q->cmp){
q->rear = 0;
}
q->size++;
}
因为我们实现的是动态空间，所以会有扩容操作的出现。对于入队操作，因为我们有了size，所以可以不需要特别关注rear，所以在超出数组空间地址的时候，我们直接令其为0即可(通过下标操作)。
但是在这里实现扩容的时候需要我们特别注意，他不可以想栈一样直接进行扩容，因为循环队列的关系
数据：1 9 4 6 7 8 = 4 7 9
下标：0 1 2 3 4 5 6 7 8 9
以上为例可以看到front在下标为7的地方而rear在下标为6的地方如果直接扩容就是在9之后继续开辟空间，很明显这样的操作是错误的，所以说只能先开辟一块空间然后遍历原来的表搬运到新表，这里我的size也起到了作用，当然如果用取余的方法一样可以实现。为了避免内存泄漏记得在搬运之后释放原来申请的空间。
int top(queue *q){
if(q->size == 0 ){
return 0;
}
q->front++;
if(q->front == q->cmp){
q->front = 0;
}
q->size--;
return 1;
}
然后就是出栈操。
void show(queue *q){
for(int t = q->front; t<q->front + q->size; t++){
printf("%d ",q->data[t % q->cmp]);
}
printf("\n");
}
当然还有我们的输出方法，用来检验我们的实现效果
int main(){
queue *q = initQueue(3);
int a,val;
while(1){
scanf("%d", &a);
if(a == 1){
scanf("%d",&val);
push(q ,val );
}
else if(a == 2){
top(q);
}
else if(a == 3){
getTop(q);
}
else{
deleteQueue(q);
}
show(q);
printf("---------------------------------------------\n");
}
return 0;
}
主函数部分，运行结果如下
以上就是顺序存储结构实现循环队列的方法，需要注意如果是动态空间的话，我们需要重新申请空间进行搬运。
队列的链式存储结构
链式存储结构相较于顺序结构更适合链表。用单链表表示就非常适合队列的出队入队操作，而且也不会出现溢出的问题。一般来讲需要两个指针一个头指针和一个尾指针可以很容易实现。但是为了对比上面的循环队列，我这里采用单循环链表实现一个循环队列，采用单循环链表我们只需要一个虚拟头即可。
代码实现
#include<stdio.h>
#include<stdlib.h>
typedef struct node{
int data;
node *next;
}node;
typedef struct queue{
node *head;
int size;
};
可以看到只有一个头指针，同时我们也需要一个size来记录队列大小
queue *initQueue(){
queue *q = (queue *)malloc(sizeof(queue));
q->head = (node *)malloc(sizeof(node));
q->head->next = q->head;
q->head->data = -1;
q->size = 0;
return q;
}
void deleteQueue(queue *q){
node *n = q->head;
while(n){
node *t = n->next;
free(n);
n = t;
}
free(q);
}
初始化和销毁操作，因为我们需要一个虚拟头，所以初始化的时候就建立一个虚拟头，因为我们时循环链表所以要记得指向自身。同样链式结构，在删除的时候要遍历依次释放节点空间。
int getTop(queue *q){
printf("the top is %d\n",q->head->next->data);
return q->head->next->data;
}
查看队首元素
void push(queue *q, int val){
node *n = (node *)malloc(sizeof(node));
n->next = q->head->next;
n->data = -1;
q->head->data = val;
q->head->next = n;
q->head = n;
q->size++;
}
在进行入队操作的时候，因为是循环队列，所以虚拟头与队首和队尾相连，如果我们把虚拟头的值改成我们需要的值，然后再在虚拟头之后插入一个虚拟头就实现了依照偷梁换柱，变成了入队操作。大概是下面这个过程
int top(queue *q){
node *n = q->head->next;
int res = n->data;
q->head->next = q->head->next->next;
free(n);
q->size--;
return res;
}
void show(queue *q){
node *n = q->head->next;
while(n->data != -1){
printf("%d ",n->data);
n = n->next;
}
printf("\n");
}
然后就是出队操作，以及输出方法。
主函数部分与之前的一样我就不放了。
双端队列
双端队列是指两端都可以进行入队和出队操作，其逻辑结构依旧是线性结构，将其两端称为前端和后端，我们也可以限制双端队列的输入输出，让其得到我们需要的输出队列
小节
- 队列和栈相同有一样的逻辑结构，也都可用顺序结构和链式结构实现
- 队列最大特点是FIFO先进先出与栈的后进先出截然不同
- 当用顺序结构实现队列时，会极大的造成空间浪费，所以一般用循环队列实现，循环队列扩容时，处于循环队列特点，我们只能搬运原数据到空间更大的队列中
- 带有队首指针和队尾指针的非循环链表是最适合实现队列的，因为很容易实现出队入队操作，同时也不会有溢出的情况