順序隊(duì)列及其實(shí)現(xiàn)

順序隊(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í)一種最簡單的實(shí)現(xiàn)方法。

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

由于順序隊(duì)列的底層使用的是數(shù)組，因此需預(yù)先申請一塊足夠大的內(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í)，對應(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ì)列最簡單方法的 C 語言實(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ì)后的示意圖。通過對比兩張圖，你會(huì)發(fā)現(xiàn)，指針 top 和 rear 重合位置指向了 a[4] 而不再是 a[0]。也就是說，整個(gè)順序隊(duì)列在數(shù)據(jù)不斷地進(jìn)隊(duì)出隊(duì)過程中，在順序表中的位置不斷后移。

順序隊(duì)列整體后移造成的影響是：

• 順序隊(duì)列之前的數(shù)組存儲(chǔ)空間將無法再被使用，造成了空間浪費(fèi);

• 如果順序表申請的空間不足夠大，則直接造成程序中數(shù)組 a 溢出，產(chǎn)生溢出錯(cuò)誤;

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

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

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

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

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

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

#include <stdio.h>
#define max 5//表示順序表申請的空間大小
int enQueue(int *a,int front,int rear,int data){
    //添加判斷語句，如果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)不同，但是判斷條件相同。為了對其進(jìn)行區(qū)分，最簡單的解決辦法是：犧牲掉數(shù)組中的一個(gè)存儲(chǔ)空間，判斷數(shù)組滿員的條件是：尾指針的下一個(gè)位置和頭指針相遇，就說明數(shù)組滿了，即程序中第 5 行所示。