一、队列（queue）
队列和栈一样，在实际程序的算法设计和计算机一些其他分支里，都有很多重要的应用，比如计算机操作
系统对进程 or 作业的优先级调度算法，对离散事件的模拟算法，还有计算机主机和外部设备运行速度不匹配的问题解决等，很多很多。其实队列的本质还是线性表！只不过是一种特殊的或者说是受限的线性表，是这样的：
1）、限定在表的一端插入、另一端删除。 插入的那头就是队尾，删除的那头就是队头。也就是说只能在线性表的表头删除元素，在表尾插入元素。形象的说就是水龙头和水管，流水的水嘴是队头，进水的泵是队尾，管子中间不漏水不进水。这样呲呲的流动起来，想想就是这么个过程。
2)、先进先出 (FIFO结构)。显然我们不能在表（队列）的中间操作元素，只能是在尾部进，在头部出去，还可以类似火车进隧道的过程。（first in first out = FIFO 结构）
注意，当队列没有元素的时候，我们就说队列是空队列。
1、双端队列
double-ended queue：限定插入和删除在表的两端进行，也是先进先出 (FIFO)结构，类似铁路的转轨网络。实际程序中应用不多。
这种结构又细分为三类：
1）、输入受限的双端队列：一个端点可插入和删除，另一个端点仅可删除。
2）、输出受限的双端队列：一个端点可插入和删除，另一个端点仅可插入。
3）、等价于两个栈底相连接的栈：限定双端队列从某个端点插入的元素，只能在此端点删除。
2、链队（有链的地方，就有指针）
用链表表示的队列，限制仅在表头删除和表尾插入的单链表。一个链队列由一个头指针和一个尾指针唯一确定。（因为仅有头指针不便于在表尾做插入操作）。为了操作的方便，也给链队列添加一个头结点，因此，空队列的判定条件是：头指针和尾指针都指向头结点。
之前的链式结构，总是使用一个结点的结构来表示链表，其实不太方便，这里使用新的存储结构。定义一个结点结构，和一个队列结构。两个结构嵌套。
复制代码
1 #ifndef queue_Header_h
2 #define queue_Header_h
3 #include
4 #include
5 #include
6
7 //队列的结点结构
8 typedef struct Node{
9 int data;
10 struct Node *next;
11 } Node, *Queue;
12
13 //队列的结构，嵌套
14 typedef struct{
15 Queue front;
16 Queue rear;
17 } LinkQueue;
18
19 //初始化
20 //开始必然是空队列，队尾指针和队头指针都指向头结点
21 void initQueue(LinkQueue *queue)
22 {
23 //初始化头结点
24 queue->front = queue->rear = (Queue)malloc(sizeof(Node));
25
26 if (NULL == queue->front) {
27 exit(0);
28 }
29
30 queue->front->next = NULL;
31 }
32
33 //判空
34 bool isEmpty(LinkQueue queue)
35 {
36 return queue.rear == queue.front true : false;
37 }
38
39 //入队,只在一端入队，另一端出队，同样入队不需要判满
40 void insertQueue(LinkQueue *queue, int temp)
41 {
42 Queue q = (Queue)malloc(sizeof(Node));
43
44 if (NULL == q) {
45 exit(0);
46 }
47 //插入数据
48 q->data = temp;
49 q->next = NULL;
50 //rear 总是指向队尾元素
51 queue->rear->next = q;
52 queue->rear = q;
53 }
54
55 //出队，需要判空
56 void deleteQueue(LinkQueue *queue)
57 {
58 Queue q = NULL;
59
60 if (!isEmpty(*queue)) {
61 q = queue->front->next;
62 queue->front->next = q->next;
63 //这句很关键，不能丢
64 if (queue->rear == q) {
65 queue->rear = queue->front;
66 }
67
68 free(q);
69 }
70 }
71
72 //遍历
73 void traversal(LinkQueue queue)
74 {
75 int i = 1;
76 Queue q = queue.front->next;
77
78 while (q != NULL) {
79 printf("队列第%d个元素是：%d\n", i, q->data);
80 q = q->next;
81 i++;
82 }
83 }
84
85 //销毁
86 void destoryQueue(LinkQueue *queue)
87 {
88 while (queue->front != NULL) {
89 queue->rear = queue->front->next;
90 free(queue->front);
91 queue->front = queue->rear;
92 }
93
94 puts("销毁成功！");
95 }
96
97 #endif
复制代码
测试
复制代码
1 #include "queue.h"
2
3 int main(int argc, const char * argv[])
4 {
5 LinkQueue queue;
6 puts("初始化队列 queue");
7 initQueue(&queue);
8 traversal(queue);
9
10 puts("队尾依次插入0 1 2 3");
11 insertQueue(&queue, 0);
12 insertQueue(&queue, 1);
13 insertQue