學(xué)習(xí)隊(duì)列，看這一篇就夠了！
提要鉤玄：本文主要介紹隊(duì)列的結(jié)構(gòu)、基本原理及操作，涉及到兩種實(shí)現(xiàn)：順序隊(duì)列和鏈隊(duì)列。
1. 什么是隊(duì)列?
先舉一個(gè)日常例子，排隊(duì)買飯。
排隊(duì)買飯
大家按先來后到的順序，在窗口前排隊(duì)買飯，先到先得，買完之后走開，輪到下一位買，新來的人排在隊(duì)尾，不能插隊(duì)。
可見，上面的“隊(duì)”的特點(diǎn)是只允許從一端進(jìn)入，從另一端離開。
這樣的一個(gè)隊(duì)，放在數(shù)據(jù)結(jié)構(gòu)中就是“隊(duì)列”。
首先，隊(duì)列是一個(gè)線性表，所以它具有線性表的基本特點(diǎn)。
其次，隊(duì)列是一個(gè)受限的線性表，受限之處為：只允許從一端進(jìn)入隊(duì)列，從另一端離開。
根據(jù)以上特點(diǎn)，可以畫出示意圖：
出隊(duì)元素 1，入隊(duì)元素 4 之后：
下面是幾個(gè)相關(guān)名詞：
- 入隊(duì)：進(jìn)入隊(duì)列，即向隊(duì)列中插入元素
- 出隊(duì)：離開隊(duì)列，即從隊(duì)列中刪除元素
- 隊(duì)頭：允許出隊(duì)(刪除)的一端
- 隊(duì)尾：允許入隊(duì)(插入)的一端
- 隊(duì)頭元素：隊(duì)列中最先入棧的元素
- 隊(duì)尾元素：隊(duì)列中最后入棧的元素
我們可以直接將隊(duì)頭元素看作隊(duì)頭，隊(duì)尾元素看作隊(duì)尾。(這些名詞概念，有所理解即可，不必細(xì)究)
隊(duì)列的重要特性是在隊(duì)尾進(jìn)行入隊(duì)操作，在隊(duì)頭進(jìn)行出隊(duì)操作，所以上圖元素的入隊(duì)順序?yàn)椋?、2、3，出隊(duì)順序?yàn)椋?、2、3，也即，先入隊(duì)的先出隊(duì)(First In First Out, FIFO)，后入隊(duì)的后出隊(duì)(Last In Last Out, LILO).
總結(jié)一下，隊(duì)列是一種只允許在一端進(jìn)行插入操作，在另一端進(jìn)行刪除操作的先入先出的受限的線性表。
2. 隊(duì)列的實(shí)現(xiàn)思路
和棧一樣，隊(duì)列也可以有兩種實(shí)現(xiàn)方式：數(shù)組實(shí)現(xiàn)的順序隊(duì)列和鏈表實(shí)現(xiàn)的鏈隊(duì)列。
2.1. 數(shù)組實(shí)現(xiàn)——順序隊(duì)列
一個(gè)用數(shù)組實(shí)現(xiàn)的順序隊(duì)列如下圖所示：
順序隊(duì)列
可以看到，要實(shí)現(xiàn)一個(gè)順序隊(duì)列，我們需要以下結(jié)構(gòu)：
- 存儲數(shù)據(jù)的數(shù)組 —— data[]
- 表示隊(duì)列的最大容量的值 —— MAXSIZE
- 標(biāo)識隊(duì)頭端的隊(duì)頭下標(biāo) —— front
- 標(biāo)識隊(duì)尾端的隊(duì)尾下標(biāo) —— rear
front 和 rear 會(huì)隨著入隊(duì)和出隊(duì)操作而變化，為了方便起見，我們規(guī)定在非空隊(duì)列中，隊(duì)尾下標(biāo)是隊(duì)尾元素的下一個(gè)元素的下標(biāo)。
了解了結(jié)構(gòu)之后，我們可以很容易使用 C 語言的結(jié)構(gòu)體實(shí)現(xiàn)它：
- #define MAXSIZE 5 //順序隊(duì)列的最大存儲容量
- /*順序隊(duì)列的結(jié)構(gòu)體*/
- typedef struct {
- int data[MAXSIZE];
- int front; //隊(duì)頭下標(biāo)
- int rear; //隊(duì)尾下標(biāo)
- } QueueArray;
2.2. 鏈表實(shí)現(xiàn)——鏈隊(duì)列
我們使用帶頭節(jié)點(diǎn)的單鏈表來實(shí)現(xiàn)隊(duì)列，如下圖所示：
鏈隊(duì)列
可以看到，要實(shí)現(xiàn)一個(gè)鏈隊(duì)列，需要以下結(jié)構(gòu)：
1.單鏈表的基本單元結(jié)點(diǎn) —— QueueNode
- 存儲數(shù)據(jù)的數(shù)據(jù)域 —— data
- 指向下一個(gè)結(jié)點(diǎn)的指針域 —— next
2.指向鏈表的頭指針 —— head
3.標(biāo)識隊(duì)頭端的隊(duì)頭指針 —— front
4.標(biāo)識隊(duì)尾端的隊(duì)尾指針 —— rear
其中，頭指針 head 和隊(duì)頭指針 front 都指向了單鏈表的第一個(gè)結(jié)點(diǎn)，所以這個(gè)指針可以合二為一，隊(duì)頭指針即頭指針。
如此一來，我們可以借助鏈表的尾插法實(shí)現(xiàn)隊(duì)列的入隊(duì)操作，借助鏈表的頭刪法實(shí)現(xiàn)隊(duì)列的出隊(duì)操作。
搞清了結(jié)構(gòu)，用結(jié)構(gòu)體實(shí)現(xiàn)如下：
- /*單鏈表的結(jié)點(diǎn)的結(jié)構(gòu)體*/
- typedef struct QueueNode {
- int data; //數(shù)據(jù)域
- struct QueueNode *next; //指針域
- } QueueNode;
- /*鏈隊(duì)列的結(jié)構(gòu)體*/
- typedef struct {
- QueueNode *front; //隊(duì)頭指針
- QueueNode *rear; //隊(duì)尾指針
- } QueueLink;
3. 隊(duì)列的狀態(tài)
3.1. 順序隊(duì)列(問題版)
【空隊(duì)列】：空隊(duì)列中沒有元素，此時(shí)，隊(duì)頭下標(biāo)和隊(duì)尾下標(biāo)均為 0，即front = rear = 0：
空隊(duì)列
【非空非滿隊(duì)列】：隊(duì)列不是空隊(duì)列且有剩余空間：
非空非滿隊(duì)列
【滿隊(duì)列】：順序隊(duì)列分配的固定空間用盡，沒有多余空間，不能再插入元素，此時(shí) front = 0，rear = MAXSIZE：
滿隊(duì)列
從上圖中可以看出，非空隊(duì)列的隊(duì)尾下標(biāo) rear 始終是隊(duì)尾元素的下一個(gè)元素的下標(biāo)。
3.2. 假滿隊(duì)列
以上是用數(shù)組實(shí)現(xiàn)的順序隊(duì)列的三種狀態(tài)，但上圖中三種隊(duì)列是存在問題的，那就是隊(duì)列的存儲問題!
先再次明確隊(duì)列的兩條重要特性：
- 隊(duì)列只允許在隊(duì)頭刪除元素，在隊(duì)尾插入元素
- 我們規(guī)定：front 是隊(duì)頭元素的下標(biāo)，rear 是隊(duì)尾元素的下標(biāo)，二者會(huì)隨著出隊(duì)和入隊(duì)操作而變化
由于上面的三幅圖中 front 都在下標(biāo) 0 處，所以不容易看出問題，請看下面的過程圖：
入隊(duì)出隊(duì)過程圖
簡單用文字描述以下上述過程：
圖1：空隊(duì)列
圖2：進(jìn)隊(duì) 3 個(gè)元素：1、2、3
圖3：出隊(duì) 2 個(gè)元素：1、2
圖4：入隊(duì) 2 個(gè)元素：4、5
到此為止，一切正常。
圖5：入隊(duì) 1 個(gè)元素，但在圖4中 rear = 5已經(jīng)超出數(shù)組的最大范圍，所以圖5入隊(duì)一個(gè)元素會(huì)報(bào)錯(cuò)，這個(gè)隊(duì)列不能再插入元素了。
圖5的隊(duì)列滿了嗎?沒滿!能繼續(xù)插入元素嗎?不能!有剩余空間卻不能用，這就好比有空房的酒店不讓客戶入住，這叫不會(huì)做生意。
滿隊(duì)列的是空間用盡，不能再插入元素的隊(duì)列，雖然圖5的隊(duì)列也不能繼續(xù)插入元素了，但它還有剩余空間，所以這樣的隊(duì)列還不能稱之為滿隊(duì)列，可稱之為假滿隊(duì)列。
之所以假滿隊(duì)列存在問題，是因?yàn)轫樞蜿?duì)列的空間是有限的，通過若干入隊(duì)操作之后，我們的 rear “跑”到數(shù)組外從而導(dǎo)致越界了。
假滿隊(duì)列
明明才存儲了一個(gè)元素，卻因?yàn)榧贊M，整個(gè)隊(duì)列不能再存儲了。這樣的隊(duì)列肯定不是合格的數(shù)據(jù)結(jié)構(gòu)。
怎么解決呢?報(bào)錯(cuò)是 rear 越界導(dǎo)致，而隊(duì)列的前大部分都是空閑的，所以當(dāng) rear 越界時(shí)，我們可不可以將其移動(dòng)到下標(biāo) 0 處呢?
顯然是可以的，這樣就構(gòu)成了一個(gè)“循環(huán)”，我們稱這種 front 和 rear可以循環(huán)利用的隊(duì)列為循環(huán)隊(duì)列。
3.3. 循環(huán)隊(duì)列
為了突出“循環(huán)”二字，我們將這種順序隊(duì)列畫成一個(gè)圓：
循環(huán)隊(duì)列
循環(huán)隊(duì)列的 rear 和 front 能夠在隊(duì)列中一圈一圈地轉(zhuǎn)，像鐘表的時(shí)針和分針一樣。不會(huì)再出現(xiàn)不能利用的空間了。
順序隊(duì)列的形式從“直的”變成這種可循環(huán)的之后，對于狀態(tài)的判斷也改變了。
【空隊(duì)列】：隊(duì)列中沒有元素，如上圖。
請注意，空隊(duì)列的條件并不是 front = rear = 0，比如一個(gè)空隊(duì)列經(jīng)過 3 次入隊(duì)和 3 次出隊(duì)操作后仍為空隊(duì)列：
空隊(duì)列
所以，循環(huán)隊(duì)列為空隊(duì)列時(shí)，條件應(yīng)該為 front = rear
【滿隊(duì)列】：隊(duì)列中沒有空閑空間
滿隊(duì)列
上圖是一個(gè)最大容量為 8 的空隊(duì)列，入隊(duì) 7 個(gè)元素后，隊(duì)列中還剩 1 個(gè)空閑位置，如果此時(shí)我們再入隊(duì) 1 個(gè)元素：
是滿隊(duì)列嗎?
此時(shí)隊(duì)列中確實(shí)沒有空閑空間了，但注意，此時(shí)隊(duì)列滿足了 rear = front ，但滿足 rear = front的隊(duì)列不應(yīng)該是空隊(duì)列嗎?
這就產(chǎn)生誤會(huì)了。
不如我們退一步海闊天空，少用一個(gè)元素，借此來消除誤會(huì)。如下圖，規(guī)定這樣是一個(gè)滿隊(duì)列。
滿隊(duì)列
我們規(guī)定，front 出現(xiàn)在 rear 的下一個(gè)位置時(shí)，隊(duì)列為滿隊(duì)列。
比如在上圖的滿隊(duì)列中， front = 3 在 rear = 2 的下一個(gè)位置。
所以隊(duì)列為滿隊(duì)列的判定條件為：rear + 1 = front，但這的條件是不準(zhǔn)確的。
因?yàn)檠h(huán)隊(duì)列中的 front 和 rear 都是循環(huán)使用的，就像鐘表的時(shí)針一樣，所以我們僅根據(jù)下標(biāo)的大小來判斷位置是不合理的。下面兩個(gè)均是滿隊(duì)列，右圖不滿足rear + 1 = front：
就像鐘表的時(shí)針滿 12 歸零一樣，front 和 rear 也應(yīng)該滿某個(gè)數(shù)后歸零，這個(gè)數(shù)就是 MAXSIZE。
比如 rear = 7 時(shí)，如果按平常做法來 ，下一步應(yīng)該是 rear = 8，但在這里，我們讓其歸零，所以下一步應(yīng)該是 rear = 0。
用數(shù)學(xué)公式來表示上面的歸零過程就是：rear % MAXSIZE
所以滿隊(duì)列的判斷條件應(yīng)該為：(rear + 1) % MAXSIZE = front。
【非空非滿隊(duì)列】：很好理解，不再贅述。
3.4. 鏈隊(duì)列
我們使用帶頭結(jié)點(diǎn)的單鏈表來實(shí)現(xiàn)鏈隊(duì)列。
【空隊(duì)列】：即一個(gè)空鏈表，此時(shí)隊(duì)頭指針(兼鏈表頭指針)和隊(duì)尾指針均指向頭結(jié)點(diǎn)。
空隊(duì)列
【非空隊(duì)列】：不像順序隊(duì)列那樣有空間的限制，鏈隊(duì)列的空間是不受限制的(只要你的內(nèi)存足夠大)，所以自然不存在“滿隊(duì)列”“循環(huán)隊(duì)列”的概念。
4. 初始化
在進(jìn)行隊(duì)列的操作前，應(yīng)該先將其初始化出來，即初始化一個(gè)空隊(duì)列出來。
4.1. 順序隊(duì)列
將隊(duì)列的隊(duì)頭下標(biāo)和隊(duì)尾下標(biāo)置為 0 即可。
- /**
- * 初始化順序隊(duì)列：將隊(duì)頭下標(biāo)和隊(duì)尾下標(biāo)置為0
- * queue: 指向隊(duì)列的指針
- */
- void init(QueueArray *queue)
- {
- queue->front = 0;
- queue->rear = 0;
- }
4.2. 鏈隊(duì)列
創(chuàng)造出頭結(jié)點(diǎn)，然后將隊(duì)頭指針和隊(duì)尾指針均指向頭結(jié)點(diǎn)即可。
- /**
- * 初始化鏈隊(duì)列：將隊(duì)頭指針和隊(duì)尾指針指向頭結(jié)點(diǎn)
- */
- void init(QueueLink *queue)
- {
- //創(chuàng)造頭結(jié)點(diǎn)
- QueueNode *head_node = create_node(0);
- //隊(duì)頭指針 隊(duì)尾指針指向頭結(jié)點(diǎn)
- queue->front = head_node;
- queue->rear = head_node;
- }
5. 入隊(duì)操作
入隊(duì)操作只允許元素從隊(duì)尾進(jìn)。
5.1. 順序隊(duì)列
前面我們規(guī)定，順序隊(duì)列的隊(duì)尾下標(biāo)為隊(duì)尾元素的下一個(gè)元素，所以直接將待入隊(duì)元素放入隊(duì)尾下標(biāo)處，然后隊(duì)尾下標(biāo)“加一”。(注意：循環(huán)隊(duì)列中的加一要對 MAXSIZE 取模)
入隊(duì)過程
- /**
- * 入隊(duì)操作
- * queue: 指向隊(duì)列的指針
- * elem: 入隊(duì)的數(shù)據(jù)
- * return: 0失敗，1成功
- */
- int en_queue(QueueArray *queue, int elem)
- {
- //判斷隊(duì)列是否已滿
- if ((queue->rear + 1) % MAXSIZE == queue->front) {
- printf("隊(duì)列已滿，無法繼續(xù)入隊(duì)。\n");
- return 0;
- }
- //元素入隊(duì)
- queue->data[queue->rear] = elem;
- //隊(duì)尾下標(biāo)加一
- queue->rear = (queue->rear + 1) % MAXSIZE;
- return 1;
- }
5.2. 鏈隊(duì)列
鏈隊(duì)列的入隊(duì)操作本質(zhì)是單鏈表的尾插法：
- /** * 入隊(duì)操作
- * queue: 指向隊(duì)列的指針
- * elem: 入隊(duì)的數(shù)據(jù)
- */
- void en_queue(QueueLink *queue, int elem)
- {
- //創(chuàng)造新結(jié)點(diǎn)
- QueueNode *new = create_node(elem);
- //入隊(duì)（尾插法）
- queue->rear->next = new;
- queue->rear = new;
- }
6. 出隊(duì)操作
出隊(duì)操作只允許元素從隊(duì)頭出。
6.1. 順序隊(duì)列
將隊(duì)頭下標(biāo)處的元素出隊(duì)，然后將隊(duì)頭下標(biāo)“加一”(對 MAXSIZE 取模)。
出隊(duì)過程
- /**
- * 出隊(duì)操作
- * queue: 指向隊(duì)列的指針
- * elem: 指向保存出隊(duì)數(shù)據(jù)的變量
- * return: 0失敗，1成功
- */
- int de_queue(QueueArray *queue, int *elem)
- {
- //判讀隊(duì)列是否為空
- if (queue->front == queue->rear) {
- printf("隊(duì)列空，無元素可出。\n");
- return 0;
- }
- //元素出隊(duì)
- *elem = queue->data[queue->front];
- //隊(duì)頭下標(biāo)加一
- queue->front = (queue->front + 1) % MAXSIZE;
- return 1;
- }
6.2. 鏈隊(duì)列
鏈隊(duì)列的出隊(duì)操作本質(zhì)上是單鏈表的頭刪法。注意，如果出隊(duì)的是隊(duì)列中最后一個(gè)元素，需要在出隊(duì)后，將隊(duì)尾指針重新指向頭結(jié)點(diǎn)，重新形成空隊(duì)列。
- /**
- * 出隊(duì)操作
- * queue: 指向隊(duì)列的指針
- * elem: 指向保存變量的指針
- * return: 0失敗，1成功
- */
- int de_queue(QueueLink *queue, int *elem)
- {
- //判讀隊(duì)列是否為空
- if (queue->front == queue->rear) {
- printf("隊(duì)列空，無元素可出。\n");
- return 0;
- }
- QueueNode *front_node = queue->front->next; //隊(duì)頭元素
- //保存數(shù)據(jù)
- *elem = front_node->data;
- //隊(duì)頭元素出隊(duì)（頭刪法）
- queue->front->next = front_node->next;
- //如果元素出完，隊(duì)尾指針重新指向頭結(jié)點(diǎn)
- if (front_node == queue->rear)
- queue->rear = queue->front;
- free(front_node);
- }
7. 遍歷操作
這里以打印整個(gè)隊(duì)列為例，介紹如何遍歷隊(duì)列。
順序隊(duì)列有隊(duì)頭下標(biāo)和隊(duì)尾下標(biāo)，鏈隊(duì)列有隊(duì)頭指針和隊(duì)尾指針，我們要做的就是借助一個(gè)臨時(shí)變量，從隊(duì)頭下標(biāo)逐個(gè)遍歷到隊(duì)尾下標(biāo)即可。
7.1. 順序隊(duì)列
借助臨時(shí)變量 i，從隊(duì)頭下標(biāo)開始逐個(gè)“加一”直到隊(duì)尾下標(biāo)結(jié)束。
開始標(biāo)志為：i = front
加一操作為：i = (i + 1) % MAXSIZE
結(jié)束標(biāo)志為：i % MAXSIZE = rear
- /**
- * 打印隊(duì)列
- */
- void output(QueueArray queue)
- {
- int i = queue.front;
- while (i % MAXSIZE != queue.rear) {
- printf("%d ", queue.data[i]);
- i = (i + 1) % MAXSIZE;
- }
- printf("\n");
- }
如何計(jì)算順序隊(duì)列的長度?當(dāng)然你可以遍歷隊(duì)列然后借助計(jì)數(shù)變量來存儲長度，這樣比較麻煩。因?yàn)轫樞蜿?duì)列是使用數(shù)組實(shí)現(xiàn)的，所以順序隊(duì)列的長度我們可以直接根據(jù)下標(biāo)計(jì)算出來。
如果是一個(gè)非循環(huán)隊(duì)列，那很簡單，直接 rear - front 就是隊(duì)列的長度了。
但循環(huán)隊(duì)列不能這樣直接減了，因?yàn)?rear 和 front 之間的位置關(guān)系是不確定的。
左圖 rear < front，我們可以將其長度看成兩部分組成：
- 下標(biāo) 0 到 rear，長度為 rear - 0
- 下標(biāo) MAXSIZE - 1 到 rear，長度為 MAXSIZE - front
所以長度為 rear - front + MAXSIZE
為了滿足右圖 rear > front 的情況，如果按照上式，則此時(shí)多加了一個(gè) MAXSIZE，所以需要對其再對 MAXIZE 取余。
所以循環(huán)隊(duì)列的長度為 (rear - front + MAXSIZE) % MAXSIZE(空隊(duì)列也滿足)。
7.2. 鏈隊(duì)列
借助指針 p 從隊(duì)頭元素遍歷至隊(duì)尾元素即可。
- /**
- * 打印隊(duì)列
- */
- void output(QueueLink *queue)
- {
- QueueNode *p = queue->front->next; //p指向隊(duì)頭元素
- while (p != NULL) {
- printf("%d ", p->data);
- p = p->next;
- }
- printf("\n");
- }
以上就是隊(duì)列的基本原理及操作。
