順序隊(duì)列，即采用順序表模擬實(shí)現(xiàn)的隊(duì)列結(jié)構(gòu)。

我們知道，隊(duì)列具有以下兩個(gè)特點(diǎn)：
1、數(shù)據(jù)從隊(duì)列的一端進(jìn)，另一端出；
2、數(shù)據(jù)的入隊(duì)和出隊(duì)遵循"先進(jìn)先出"的原則；

因此，只要使用順序表按以上兩個(gè)要求操作數(shù)據(jù)，即可實(shí)現(xiàn)順序隊(duì)列。首先來學(xué)習(xí)一種最簡(jiǎn)單的實(shí)現(xiàn)方法。

順序隊(duì)列簡(jiǎn)單實(shí)現(xiàn)

由于順序隊(duì)列的底層使用的是數(shù)組，因此需預(yù)先申請(qǐng)一塊足夠大的內(nèi)存空間初始化順序隊(duì)列。除此之外，為了滿足順序隊(duì)列中數(shù)據(jù)從隊(duì)尾進(jìn)，隊(duì)頭出且先進(jìn)先出的要求，我們還需要定義兩個(gè)指針（top 和 rear）分別用于指向順序隊(duì)列中的隊(duì)頭元素和隊(duì)尾元素，如圖 1 所示：

圖 1 順序隊(duì)列實(shí)現(xiàn)示意圖

由于順序隊(duì)列初始狀態(tài)沒有存儲(chǔ)任何元素，因此 top 指針和 rear 指針重合，且由于順序隊(duì)列底層實(shí)現(xiàn)靠的是數(shù)組，因此 top 和 rear 實(shí)際上是兩個(gè)變量，它的值分別是隊(duì)頭元素和隊(duì)尾元素所在數(shù)組位置的下標(biāo)。

在圖 1 的基礎(chǔ)上，當(dāng)有數(shù)據(jù)元素進(jìn)隊(duì)列時(shí)，對(duì)應(yīng)的實(shí)現(xiàn)操作是將其存儲(chǔ)在指針 rear 指向的數(shù)組位置，然后 rear+1；當(dāng)需要隊(duì)頭元素出隊(duì)時(shí)，僅需做 top+1 操作。

例如，在圖 1 基礎(chǔ)上將 {1,2,3,4} 用順序隊(duì)列存儲(chǔ)的實(shí)現(xiàn)操作如圖 2 所示：

圖 2 數(shù)據(jù)進(jìn)順序隊(duì)列的過程實(shí)現(xiàn)示意圖

在圖 2 基礎(chǔ)上，順序隊(duì)列中數(shù)據(jù)出隊(duì)列的實(shí)現(xiàn)過程如圖 3 所示：

圖 3 數(shù)據(jù)出順序隊(duì)列的過程示意圖

因此，使用順序表實(shí)現(xiàn)順序隊(duì)列最簡(jiǎn)單方法的 C 語(yǔ)言實(shí)現(xiàn)代碼為：

#include <stdio.h> int enQueue(int *a,int rear,int data){a[rear]=data;rear++;return rear; } void deQueue(int *a,int front,int rear){//如果 front==rear，表示隊(duì)列為空while (front!=rear) {printf("出隊(duì)元素：%d\n",a[front]);front++;} } int main() {int a[100];int front,rear;//設(shè)置隊(duì)頭指針和隊(duì)尾指針，當(dāng)隊(duì)列中沒有元素時(shí)，隊(duì)頭和隊(duì)尾指向同一塊地址front=rear=0;//入隊(duì)rear=enQueue(a, rear, 1);rear=enQueue(a, rear, 2);rear=enQueue(a, rear, 3);rear=enQueue(a, rear, 4);//出隊(duì)deQueue(a, front, rear);return 0; }

程序輸出結(jié)果：

出隊(duì)元素：1 出隊(duì)元素：2 出隊(duì)元素：3 出隊(duì)元素：4

此方法存在的問題
先來分析以下圖 2b) 和圖 3b)。圖 2b) 是所有數(shù)據(jù)進(jìn)隊(duì)成功的示意圖，而圖 3b) 是所有數(shù)據(jù)全部出隊(duì)后的示意圖。通過對(duì)比兩張圖，你會(huì)發(fā)現(xiàn)，指針 top 和 rear 重合位置指向了 a[4] 而不再是 a[0]。也就是說，整個(gè)順序隊(duì)列在數(shù)據(jù)不斷地進(jìn)隊(duì)出隊(duì)過程中，在順序表中的位置不斷后移。

順序隊(duì)列整體后移造成的影響是：
順序隊(duì)列之前的數(shù)組存儲(chǔ)空間將無法再被使用，造成了空間浪費(fèi)；
如果順序表申請(qǐng)的空間不足夠大，則直接造成程序中數(shù)組 a 溢出，產(chǎn)生溢出錯(cuò)誤；

為了避免以上兩點(diǎn)，我建議初學(xué)者使用下面的方法實(shí)現(xiàn)順序隊(duì)列。

順序隊(duì)列另一種實(shí)現(xiàn)方法

既然明白了上面這種方法的弊端，那么我們可以試著在它的基礎(chǔ)上對(duì)其改良。

為了解決以上兩個(gè)問題，可以使用巧妙的方法將順序表打造成一個(gè)環(huán)狀表，如圖 4 所示：

圖 4 環(huán)狀順序隊(duì)列

圖 4 只是一個(gè)想象圖，在真正的實(shí)現(xiàn)時(shí)，沒必要真創(chuàng)建這樣一種結(jié)構(gòu)，我們還是使用之前的順序表，也還是使用之前的程序，只需要對(duì)其進(jìn)行一點(diǎn)小小的改變：

#include <stdio.h> #define max 5//表示順序表申請(qǐng)的空間大小 int enQueue(int *a,int front,int rear,int data){//添加判斷語(yǔ)句，如果rear超過max，則直接將其從a[0]重新開始存儲(chǔ)，如果rear+1和front重合，則表示數(shù)組已滿if ((rear+1)%max==front) {printf("空間已滿");return rear;}a[rear%max]=data;rear++;return rear; } int deQueue(int *a,int front,int rear){//如果front==rear，表示隊(duì)列為空if(front==rear%max) {printf("隊(duì)列為空");return front;}printf("%d ",a[front]);//front不再直接 +1，而是+1后同max進(jìn)行比較，如果=max，則直接跳轉(zhuǎn)到 a[0]front=(front+1)%max;return front; } int main() {int a[max];int front,rear;//設(shè)置隊(duì)頭指針和隊(duì)尾指針，當(dāng)隊(duì)列中沒有元素時(shí)，隊(duì)頭和隊(duì)尾指向同一塊地址front=rear=0;//入隊(duì)rear=enQueue(a,front,rear, 1);rear=enQueue(a,front,rear, 2);rear=enQueue(a,front,rear, 3);rear=enQueue(a,front,rear, 4);//出隊(duì)front=deQueue(a, front, rear);//再入隊(duì)rear=enQueue(a,front,rear, 5);//再出隊(duì)front=deQueue(a, front, rear);//再入隊(duì)rear=enQueue(a,front,rear, 6);//再出隊(duì)front=deQueue(a, front, rear);front=deQueue(a, front, rear);front=deQueue(a, front, rear);front=deQueue(a, front, rear);return 0; }

程序運(yùn)行結(jié)果：

1 2 3 4 5 6

使用此方法需要注意的是，順序隊(duì)列在判斷數(shù)組是否已滿時(shí)，出現(xiàn)下面情況：

• 當(dāng)隊(duì)列為空時(shí)，隊(duì)列的頭指針等于隊(duì)列的尾指針；
• 當(dāng)數(shù)組滿員時(shí)，隊(duì)列的頭指針等于隊(duì)列的尾指針；

順序隊(duì)列的存儲(chǔ)狀態(tài)不同，但是判斷條件相同。為了對(duì)其進(jìn)行區(qū)分，最簡(jiǎn)單的解決辦法是：犧牲掉數(shù)組中的一個(gè)存儲(chǔ)空間，判斷數(shù)組滿員的條件是：尾指針的下一個(gè)位置和頭指針相遇，就說明數(shù)組滿了，即程序中第 5 行所示。

參考文章：順序隊(duì)列及C語(yǔ)言實(shí)現(xiàn)（2種方案）

總結(jié)

以上是生活随笔為你收集整理的C语言用数组（顺序表）实现大小固定的队列的方法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。