順序隊列及其實現

順序隊列，即采用順序表模擬實現的隊列結構。

我們知道，隊列具有以下兩個特點：

1、數據從隊列的一端進，另一端出;

2、數據的入隊和出隊遵循"先進先出"的原則;

因此，只要使用順序表按以上兩個要求操作數據，即可實現順序隊列。首先來學習一種最簡單的實現方法。

順序隊列簡單實現

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

圖 1 順序隊列實現示意圖

由于順序隊列初始狀態沒有存儲任何元素，因此 top 指針和 rear 指針重合，且由于順序隊列底層實現靠的是數組，因此 top 和 rear 實際上是兩個變量，它的值分別是隊頭元素和隊尾元素所在數組位置的下標。

在圖 1 的基礎上，當有數據元素進隊列時，對應的實現操作是將其存儲在指針 rear 指向的數組位置，然后 rear+1;當需要隊頭元素出隊時，僅需做 top+1 操作。

例如，在圖 1 基礎上將 {1,2,3,4} 用順序隊列存儲的實現操作如圖 2 所示：

圖 2 數據進順序隊列的過程實現示意圖

在圖 2 基礎上，順序隊列中數據出隊列的實現過程如圖 3 所示：

圖 3 數據出順序隊列的過程示意圖

因此，使用順序表實現順序隊列最簡單方法的 C 語言實現代碼為：

#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，表示隊列為空
    while (front!=rear) {
        printf("出隊元素：%d\n",a[front]);
        front++;
    }
}
int main() {
    int a[100];
    int front,rear;
    //設置隊頭指針和隊尾指針，當隊列中沒有元素時，隊頭和隊尾指向同一塊地址
    front=rear=0;
    //入隊
    rear=enQueue(a, rear, 1);
    rear=enQueue(a, rear, 2);
    rear=enQueue(a, rear, 3);
    rear=enQueue(a, rear, 4);
    //出隊
    deQueue(a, front, rear);
    return 0;
}

程序輸出結果：

出隊元素：1
出隊元素：2
出隊元素：3
出隊元素：4

此方法存在的問題

先來分析以下圖 2b) 和圖 3b)。圖 2b) 是所有數據進隊成功的示意圖，而圖 3b) 是所有數據全部出隊后的示意圖。通過對比兩張圖，你會發現，指針 top 和 rear 重合位置指向了 a[4] 而不再是 a[0]。也就是說，整個順序隊列在數據不斷地進隊出隊過程中，在順序表中的位置不斷后移。

順序隊列整體后移造成的影響是：

• 順序隊列之前的數組存儲空間將無法再被使用，造成了空間浪費;

• 如果順序表申請的空間不足夠大，則直接造成程序中數組 a 溢出，產生溢出錯誤;

為了避免以上兩點，我建議初學者使用下面的方法實現順序隊列。

順序隊列另一種實現方法

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

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

圖 4 環狀順序隊列

圖 4 只是一個想象圖，在真正的實現時，沒必要真創建這樣一種結構，我們還是使用之前的順序表，也還是使用之前的程序，只需要對其進行一點小小的改變：

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

程序運行結果：

1 2 3 4 5 6

使用此方法需要注意的是，順序隊列在判斷數組是否已滿時，出現下面情況：

• 當隊列為空時，隊列的頭指針等于隊列的尾指針;

• 當數組滿員時，隊列的頭指針等于隊列的尾指針;

順序隊列的存儲狀態不同，但是判斷條件相同。為了對其進行區分，最簡單的解決辦法是：犧牲掉數組中的一個存儲空間，判斷數組滿員的條件是：尾指針的下一個位置和頭指針相遇，就說明數組滿了，即程序中第 5 行所示。