隊(duì)列的基本原理和操作方法

這篇文章主要介紹“隊(duì)列的基本原理和操作方法”，在日常操作中，相信很多人在隊(duì)列的基本原理和操作方法問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”隊(duì)列的基本原理和操作方法”的疑惑有所幫助！接下來，請跟著小編一起來學(xué)習(xí)吧！

10年積累的網(wǎng)站設(shè)計(jì)制作、成都網(wǎng)站設(shè)計(jì)經(jīng)驗(yàn)，可以快速應(yīng)對客戶對網(wǎng)站的新想法和需求。提供各種問題對應(yīng)的解決方案。讓選擇我們的客戶得到更好、更有力的網(wǎng)絡(luò)服務(wù)。我雖然不認(rèn)識(shí)你，你也不認(rèn)識(shí)我。但先建設(shè)網(wǎng)站后付款的網(wǎng)站建設(shè)流程，更有鳳泉免費(fèi)網(wǎng)站建設(shè)讓你可以放心的選擇與我們合作。

提要鉤玄：本文主要介紹隊(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)：

• 存儲(chǔ)數(shù)據(jù)的數(shù)組 —— data[]

• 表示隊(duì)列的最大容量的值 —— MAXSIZE

• 標(biāo)識(shí)隊(duì)頭端的隊(duì)頭下標(biāo) —— front

• 標(biāo)識(shí)隊(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ì)列的最大存儲(chǔ)容量 /*順序隊(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

• 存儲(chǔ)數(shù)據(jù)的數(shù)據(jù)域 —— data

• 指向下一個(gè)結(jié)點(diǎn)的指針域 —— next

2.指向鏈表的頭指針 —— head

3.標(biāo)識(shí)隊(duì)頭端的隊(duì)頭指針 —— front

4.標(biāo)識(shí)隊(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ì)列的存儲(chǔ)問題!

先再次明確隊(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ì)列

明明才存儲(chǔ)了一個(gè)元素，卻因?yàn)榧贊M，整個(gè)隊(duì)列不能再存儲(chǔ)了。這樣的隊(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ù)變量來存儲(chǔ)長度，這樣比較麻煩。因?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"); }

到此，關(guān)于“隊(duì)列的基本原理和操作方法”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請繼續(xù)關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)砀鄬?shí)用的文章！

分享文章：隊(duì)列的基本原理和操作方法
路徑分享：http://bm7419.com/article4/jjcioe.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站建設(shè)、網(wǎng)站內(nèi)鏈、用戶體驗(yàn)、網(wǎng)站收錄、網(wǎng)站設(shè)計(jì)、虛擬主機(jī)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)