队列的基本概念
队列（Queue），是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。向队列中插入元素称为入队，删除元素称为出队。其操作特性是先进先出
队列的常见操作：
| 函数名 | 功能 |
|---|---|
| InitQueue(*Q) | 初始化队列，构造一个空队列Q |
| QueueEmpty(Q) | 判断队列空 |
| EnQueue(*Q, x) | 入队，若队列未满，将x加入 |
| DeQueue(*Q, *x) | 出队，若队列非空，删除队头元素 |
| GetHead(*Q, *x) | 读队头元素 |
队列的顺序存储结构
队列的顺序存储
队列的顺序实现是分配一块连续的存储单元存放队列中的元素，并设置两个指针：队头指针front和队尾指针rear。
存储类型结构体如下：
#define MaxSize 50
typedef struct {
int data[MaxSize];
int front, rear;
}Queue;
初始时：Q->front = Q->rear = 0;（如下图1）
进队：队列不满时，先送值到队尾元素，再将队尾指针加一；（如下图2）
出队：队列非空时，先取队头元素值，再将队头指针加一。（如下图3）
我们能不能使用Q->rear == MaxSize作为队列满的条件呢？
答案是：不能！！
如下图4所示，队列中仅有一个元素时，仍满足该条件，但此时队列出现上溢出。
这种溢出不是真正的溢出，在data数组中仍然存在很多可以存放元素的空位置，是假溢出。
循环队列
为了解决上文提到的假溢出，我们引入了循环队列——把顺序队列的表从逻辑上视作一个环，当队首指针Q->front = MaxSize - 1后，再向前一个位置就自动回到0。
一些运算
初始时：Q->front = Q->rear = 0;
队首指针进1： Q->front = (Q->front + 1) % MaxSize;
队尾指针进1： Q->rear = (Q->rear + 1) % MaxSize;
队列长度： (Q->rear + MaxSize - Q->front) % MaxSize;
判空
显然队空的条件是Q->front == Q->rear；
那么，当入队元素的速度快于出队元素的速度，会发生什么呢？
===》队尾指针会很快赶上队首指针，如下图d1所示。
为了区分是队空还是队满，有三种处理方式：
-
如下图d2，牺牲一个单元来区分队空和队满，入队时少用一个队列单元，约定以”队头指针在队尾指针的下一个位置作为队满的标志“
队满条件：（Q->rear + 1) % MaxSize == Q->front;
队空条件： Q->front == Q->rear;
队列元素个数： (Q->rear - Q->front + MaxSize) % MaxSize
-
类型中增设一个size数据成员，用于表示元素个数。删除成功size减一，插入成功size加一。队空时，Q->size == 0；队满时， Q->size == MaxSize。
-
类型中增设一个tag数据成员，以区分是队空开始队满。删除成功置tag=0，若导致 Q->front == Q->rear，则队空；插入成功置1，若导致 Q->front == Q->rear，则队满。
接下来我们来看图，图示循环队列出入队：
代码
初始化
void InitQueue(Queue *Q) {
Q->rear = Q->front = 0;
}
判空
bool IsEmpty(Queue *Q) {
return Q->rear == Q->front;
}
入队
void EnQueue(Queue *Q, int x) {
if((Q->rear + 1) % MaxSize == Q->front)
return ;
Q->data[Q.rear] = x;
Q->dear = (Q->dear + 1) % MaxSize;
}
出队
void DeQueue(Queue *Q, int *x) {
if(IsEmpty(Q))
return ;
*e = Q->data[Q->front];
Q->front = (Q->front + 1) % MaxSize;
}
队列的链式存储结构
队列的链式表示称为链队列，实际上是一个同时又队头指针和队尾指针的单链表。头指针指向队头节点，尾指针指向队尾节点。
结构体：
typedef struct LinkNode {
int data;
struct LinkNode *next;
}LinkNode;
typedef struct {
LinkNode *front, *rear;
}LinkQueue;
以上图源来自我的大佬同学，作者：Amαdeus，出处：https://www.cnblogs.com/MAKISE004/p/17063234.html
代码
初始化
void InitQUeue(LinkQueue *Q) {
Q->front = Q->rear = (LinkNode *)malloc(sizeof(LinkNode));
Q->front->next = NULL;
}
判空
bool IsEmpty(LinkQueue *Q) {
return Q->front == Q->rear;
}
入队
void EnQueue(LinkQueue *Q, int x) {
LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
s->data = x;
s->next = NULL;
Q->rear->next = s;
Q->rear = s;
}
出队
void DeQueue(LinkQueue *Q, int *x) {
if(IsEmpty(Q))
return ;
LinkNode *m = Q->front->next;
x = p->data;
Q->front->next = m->next;
if(Q->rear == m)
Q->rear = Q->front;
free(m);
}
写在最后
画图花了好长时间，果然昨天先写数组是一种正确的选择（经过一学期的最优化学习，我的LaTeX和markdown功底已经突飞猛进了（我的意思不是这学期的课只学会了LaTeX），敲代码总比画图快）。好了，开玩笑归开玩笑，还是希望学有所成的！