隊列的存儲結構和常見操作（c 語言實現）
一、隊列（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 <stdio.h>
4 #include <stdlib.h>
5 #include <stdbool.h>
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 insertQueue(&queue, 2);
14 insertQueue(&queue, 3);
15 traversal(queue);
16
17 puts("先進先出，刪除隊列從頭開始， 0 ");
18 deleteQueue(&queue);
19 traversal(queue);
20
21 puts("先進先出，刪除隊列從頭開始， 1 ");
22 deleteQueue(&queue);
23 traversal(queue);
24
25 puts("先進先出，刪除隊列從頭開始， 2 ");
26 deleteQueue(&queue);
27 traversal(queue);
28
29 puts("先進先出，刪除隊列從頭開始， 3");
30 deleteQueue(&queue);
31 traversal(queue);
32
33 destoryQueue(&queue);
34 return 0;
35 }
復制代碼
結果：
初始化隊列 queue
隊尾依次插入0 1 2 3
隊列第1個元素是：0
隊列第2個元素是：1
隊列第3個元素是：2
隊列第4個元素是：3
先進先出，刪除隊列從頭開始， 0
隊列第1個元素是：1
隊列第2個元素是：2
隊列第3個元素是：3
先進先出，刪除隊列從頭開始， 1
隊列第1個元素是：2
隊列第2個元素是：3
先進先出，刪除隊列從頭開始， 2
隊列第1個元素是：3
先進先出，刪除隊列從頭開始， 3
銷毀成功！
Program ended with exit code: 0
3、順序隊列
限制僅在表頭刪除和表尾插入的順序表，利用一組地址連續的存儲單元依次存放隊列中的數據元素。因為隊頭和隊尾的位置是變化的，所以也要設頭、尾指針。
初始化時的頭尾指針，初始值均應置為 0。 入隊尾指針增 1 ，出隊頭指針增 1 。頭尾指針相等時隊列為空，在非空隊列裡，頭指針始終指向隊頭元素，尾指針始終指向隊尾元素的下一位置。
初始為空隊列，那麼頭尾指針相等。
入隊，那麼尾指針加1，頭指針不變。先進先出，J1先進隊，則 rear+1，尾指針始終指向隊尾元素的下一位！如，J2進隊，rear 繼續+1，J3進隊，尾指針繼續加1，如圖
出隊，則尾指針不變，頭指針加1，注意這裡都是加1，先進先出原則，J1先刪除，front+1，指向了 J2，J2刪除，front+1指向了 J3，如圖
最後，J3刪除，則頭指針再次和尾指針相等，說明隊列空了。如圖
在順序隊列中，當尾指針已經指向了隊列的最後一個位置的下一位置時，若再有元素入隊，就會發生“溢出”。如圖位置，再次入隊，就會溢出。
4、循環隊列的誕生
順序隊列的 “假溢出” 問題：隊列的存儲空間未滿，卻發生了溢出。很好理解，比如 rear 現在雖然指向了最後一個位置的下一位置，但是之前隊頭也刪除了一些元素，那麼隊頭指針經歷若干次的 +1 之後，遺留下了很多空位置，但是順序隊列還在傻乎乎的以為再有元素入隊，就溢出呢！肯定不合理。故循環隊列誕生！
解決“假溢出”的問題有兩種可行的方法：
(1)、平移元素：把元素平移到隊列的首部。效率低。否決了。
(2)、將新元素插入到第一個位置上，構成循環隊列，入隊和出隊仍按“先進先出”的原則進行。操作效率高、空間利用率高。
雖然使用循環隊列，解決了假溢出問題，但是又有新問題發生——判空的問題，因為僅憑 front = rear 不能判定循環隊列是空還是滿。比如如圖：
這是空循環隊列的樣子
這是滿循環隊列的樣子
解決辦法：
(1)、另設一個布爾變量以區別隊列的空和滿；
(2)、少用一個元素的空間，約定入隊前測試尾指針在循環下加 1 後是否等於頭指針，若相等則認為隊滿；（最常用）
(3)、使用一個計數器記錄隊列中元素的總數。
對於第2個方案，必須犧牲一個元素的空間，那麼入隊的時候需要測試，循環意義下的加 1 操作可以描述為：
復制代碼
1 if (rear + 1 = MAXQSIZE)
2
3 rear = 0;
4
5 else
6
7 rear ++;
復制代碼
利用模運算可簡化為：
1 rear = (rear + 1)% MAXQSIZE
基本操作
復制代碼
1 #ifndef ___queue_Header_h
2 #define ___queue_Header_h
3 #include <stdio.h>
4 #include <stdlib.h>
5 #define MAX_SIZE 5
6
7 typedef struct{
8 int *base;
9 int rear;//如果隊列不空，指向隊尾元素的下一個位置
10 int front;//初始的時候指向表頭
11 } CirularQueue;
12
13 //初始化
14 void initQueue(CirularQueue *queue)
15 {
16 queue->base = (int *)malloc(MAX_SIZE*sizeof(int));
17
18 if (NULL == queue->base) {
19 exit(0);
20 }
21
22 queue->front = queue->rear = 0;
23 }
復制代碼
求長度
復制代碼
//求長度
int getLength(CirularQueue queue)
{
//這樣把所以的情況都考慮到了
return (queue.rear - queue.front + MAX_SIZE) % MAX_SIZE;
}
復制代碼
第一種情況，長度的求法
第二種情況，長度的求法，利用模運算，兩個情況合二為一！
復制代碼
//入隊，先判滿
void insertQueue(CirularQueue *queue, int e)
{
if ((queue->rear + 1) % MAX_SIZE == queue->front) {
puts("循環隊列是滿的！");
}
else
{
queue->base[queue->rear] = e;
queue->rear = (queue->rear + 1) % MAX_SIZE;
}
}
復制代碼
如下時為滿，損失一個空間，不存儲元素。方便判滿
復制代碼
1 //出隊
2 void deleteQueue(CirularQueue *queue)
3 {
4 if (queue->front == queue->rear) {
5 puts("隊列是空的！");
6 }
7 else
8 {
9 queue->front = (queue->front + 1) % MAX_SIZE;
10 }
11 }
12
13 //遍歷
14 void traversal(CirularQueue queue)
15 {
16 int q = queue.front;
17
18 for (int i = 0; i < getLength(queue); i++) {
19 printf("循環隊列的第%d個元素為%d\n", i + 1, queue.base[q]);
20 q++;
21 }
22 }
23
24 #endif
復制代碼
測試
復制代碼
1 #include "Header.h"
2
3 int main(int argc, const char * argv[]) {
4 CirularQueue queue;
5 puts("循環隊列初始化：");
6 initQueue(&queue);
7
8 puts("循環隊列初始化後長度：");
9 printf("%d\n", getLength(queue));
10
11 puts("循環隊列5個元素入隊，總長度為5，但是損失一個位置空間，實際存儲4個元素。先進先出原則：");
12 puts("循環隊列元素0入隊");
13 insertQueue(&queue, 0);
14 puts("循環隊列元素1入隊");
15 insertQueue(&queue, 1);
16 puts("循環隊列元素2入隊");
17 insertQueue(&queue, 2);
18 puts("循環隊列元素3入隊");
19 insertQueue(&queue, 3);
20
21 puts("循環隊列元素遍歷：");
22 traversal(queue);
23
24 puts("循環隊列元素繼續入隊，無法完成：");
25 insertQueue(&queue, 4);
26
27 puts("循環隊列元素0出隊之後，先進先出原則：");
28 deleteQueue(&queue);
29 traversal(queue);
30
31 puts("循環隊列元素1出隊之後，先進先出原則：");
32 deleteQueue(&queue);
33 traversal(queue);
34
35 puts("循環隊列元素2出隊之後，先進先出原則：");
36 deleteQueue(&queue);
37 traversal(queue);
38
39 puts("循環隊列元素3出隊之後，先進先出原則：");
40 deleteQueue(&queue);
41 traversal(queue);
42
43 puts("4個元素全部刪除，循環隊列已經空了：");
44 deleteQueue(&queue);
45
46 traversal(queue);
47
48 return 0;
49 }
復制代碼
結果；
循環隊列初始化：
循環隊列初始化後長度：
0
循環隊列5個元素入隊，總長度為5，但是損失一個位置空間，實際存儲4個元素。先進先出原則：
循環隊列元素0入隊
循環隊列元素1入隊
循環隊列元素2入隊
循環隊列元素3入隊
循環隊列元素遍歷：
循環隊列的第1個元素為0
循環隊列的第2個元素為1
循環隊列的第3個元素為2
循環隊列的第4個元素為3
循環隊列元素繼續入隊，無法完成：
循環隊列是滿的！
循環隊列元素0出隊之後，先進先出原則：
循環隊列的第1個元素為1
循環隊列的第2個元素為2
循環隊列的第3個元素為3
循環隊列元素1出隊之後，先進先出原則：
循環隊列的第1個元素為2
循環隊列的第2個元素為3
循環隊列元素2出隊之後，先進先出原則：
循環隊列的第1個元素為3
循環隊列元素3出隊之後，先進先出原則：
4個元素全部刪除，循環隊列已經空了：
隊列是空的！
Program ended with exit code: 0
小結：
若用戶需要循環隊列，那麼要設置隊列的最大長度，否則無法完成判斷空，如果用戶不知道最大長度是多少，那麼應該使用鏈隊。隊列在程序設計中和棧一樣，應用很多，未完待續。
