佇列

一、什么是佇列

佇列同樣是一種特殊的線性表，它和堆疊的閹割方式不一樣，它的插入只允許在隊尾進行，它的洗掉只允許在隊頭進行，因此它有先進先出的特性（FIFO），

佇列和我們日常排隊是類似的，相比日常排隊，佇列是嚴格禁止插隊的，我們可以通過下圖來理解佇列：

一個佇列的第一個元素被稱為隊頭，佇列的最后一個元素被稱為隊尾，佇列中最常用的兩種操作就是入隊和出隊，也就是俗稱的插入、洗掉操作，在佇列中，只能出隊隊頭元素，入隊元素只能在隊尾之后，

二、佇列的表示

佇列同樣可以用順序存盤和鏈式存盤兩種結構來表示，

（1）順序存盤結構

因為我們要關注隊頭和隊尾的位置，因此我們分別設定對頭指標和隊尾指標，于是我們結構體的定義如下：

#define MAXSIZE 20
typedef int ElemType;
typedef struct{
    ElemType data[MAXSIZE];		//用靜態陣列存放佇列元素
    int front, rear;		    //隊頭和隊尾指標
}SqQueue;

在使用順序存盤結構實作佇列時，我們會構造一個邏輯上回圈的佇列，后續會有更詳細的講解，

（2）鏈式存盤結構

鏈式存盤結構實作的佇列也是一個閹割版的鏈表，因此它節點的定義和鏈表是一樣的，但是鏈佇列還要額外定義一個佇列結構體：

//鏈佇列節點結構體
typedef struct QNode{
    ElemType data;
    struct QNode *next;
}QNode;
//鏈佇列結構體
typedef struct{
    //頭尾指標
    QNode *front, *rear;
}LinkedQueue;

鏈佇列的結構體中包含了一個頭指標和尾指標，

三、回圈佇列的實作

（1）回圈佇列

我們先看看如果沒有回圈佇列的概念，我們應該如何用順序存盤結構實作佇列，

在初始狀態，我們將隊頭、隊尾指標指向0，在操作佇列的程序中，我們保證隊頭指標指向隊頭的下標，隊尾指標指向隊尾的下一個位置，有了這些規則后我們對一個長度為6的佇列進行5次入隊，5次出隊操作，如圖示：

在這個操作程序中，除了隊空的情況，隊頭指標都指向隊頭元素的位置，而且隊空時隊頭指標等于隊尾指標，

我們來關注一下上面的操作我們應該如何判斷隊滿的情況，一種想法是判斷尾指標是否等于MAXSIZE-1，但是這樣做有個很明顯的問題，當我們對一個MAXSIZE=6的佇列，入隊5次再出隊5次后我們的尾指標等于MAXSIZE-1，但是我們佇列其實是空的，為了解決這個問題，我們采用回圈佇列這種邏輯結構，如圖示：

在物理上，我們還是使用一個連續的陣列來存盤，在邏輯上我們陣列的末尾和陣列開頭是連續的，比如圖中末尾下標是7，起始下標為0，因此我們只需要一個可以滿足下面要求的公式即可：
y = { x + 1 x < m a x ? 1 0 x = m a x ? 1 y = \begin{cases} x+1&x<max-1 \\ 0&x = max-1 \end{cases} y={x+10?x<max?1x=max?1?
其中max就表示陣列長度，比如最大長度為8，我們的尾指標指向下標7，如果佇列還未滿，我們入堆疊則尾指標指向下標0，這很容易讓我們想到模運算，因此在我們移動首尾指標時操作應該如下：

Q->rear = (Q->rear + 1) % MAXSIZE;
Q->front = (Q->front + 1) % MAXSIZE;

下面我們就可以著手實作一下回圈佇列，

（2）佇列初始化

佇列的初始化我們只需要將首尾指標指向0即可：

int InitSqQueue(SqQueue *Q){
    //首尾指標指向0
    Q->front = Q->rear = 0;
    return 1;
}

因此后續我們判斷堆疊是否為空的依據就是首尾指標是否相等，

（3）判斷佇列是否為空

當佇列為空時，我們回傳1，當佇列非空時回傳0：

int EmptySqQueue(SqQueue Q){
    return Q.rear == Q.front ? 1 : 0;
}

（4）入隊操作

入堆疊操作我們需要先判斷佇列是否滿，如何將輸入放入隊尾之后：

int EnSqQueue(SqQueue *Q, ElemType elem){
    //如果佇列滿了，則回傳0
    if((Q->rear + 1) % MAXSIZE == Q->front){
        return 0;
    }
    //將元素插入隊尾之后
    Q->data[Q->rear] = elem;
    //移動隊尾指標
    Q->rear = (Q->rear + 1) % MAXSIZE;
    return 1;
}

（5）出隊操作

出隊操作和入隊相反，我們要判斷是否隊空，以及操作隊頭指標：

int DeSqQueue(SqQueue *Q, ElemType *elem){
    //如果隊空，則回傳0
    if(EmptySqQueue(*Q)){
        return 0;
    }
    //獲取隊頭元素
    *elem = Q->data[Q->front];
    //移動隊頭元素
    Q->front = (Q->front + 1) % MAXSIZE;
    return 1;
}

其它一些操作這里就不實作了，

四、鏈佇列的實作

鏈佇列和鏈表十分相似，這里我們簡單說一下，

（1）初始化

這里我們選擇使用帶頭節點的鏈佇列：

int InitLinkedQueue(LinkedQueue *Q){
    //創建頭節點，讓首尾指標指向頭節點
    Q->front = Q->rear = (QNode*)malloc(sizeof(QNode));
    //如果記憶體不足，則回傳0
    if(!Q->front){
        return 0;
    }
    //初始化頭節點的指標域
    Q->front->next = NULL;
    return 1;
}

（2）判斷隊空

在初始化時我們把佇列首尾指標指向頭節點，因此當首尾指標相同時隊空：

int EmptyLinkedQueue(LinkedQueue Q){
    return Q.front == Q.rear ? 1 : 0;
}

（3）入隊操作

入隊操作在隊尾進行，因此我們只需要在隊尾插入一個元素即可：

int EnLinkedQueue(LinkedQueue *Q, ElemType elem){
    //創建節點
    QNode  *s = (QNode*)malloc(sizeof(QNode));
    //記憶體不足，則回傳0
    if(!s){
        return 0;
    }
    //給節點賦值
    s->data = elem;
    s->next = NULL;
    //在隊尾插入節點
    Q->rear->next = s;
    //移動隊尾指標
    Q->rear = s;
    return 1;
}

（4）出隊操作

出隊操作有幾個需要注意的點：

1. 隊頭指標指向的是頭節點，因此我們實際要洗掉的元素是front->next
2. 在佇列只剩一個元素時，我們要修改隊尾指標

第一點很好理解，我們直接看代碼：

int DeLinkedQueue(LinkedQueue *Q, ElemType *elem){
    //如果隊空，則回傳0
    if(EmptyLinkedQueue(*Q)){
        return 0;
    }
    //定義p指向要洗掉的元素
    QNode *p = Q->front->next;
    //獲取要洗掉的元素值
    *elem = p->data;
    //移動隊頭指標
    Q->front->next = p->next;
    //如果洗掉了最后一個元素，則需要修改隊尾指標
    if(Q->rear == p){
        Q->rear == Q->front;
    }
    free(p);
    return 1;
}

我們看下圖，此時佇列只有一個元素，我們進行出隊操作：

當我們洗掉最后一個節點后，尾指標指向了一片已經銷毀的記憶體，而且在佇列為空的情況，我們的首位指標也不相同，因此我們需要在洗掉最后一個節點時對隊尾指標進行修改，

而判斷是否是最后一個節點的條件就是，頭節點（Q.front）的next是否是尾節點，

（5）銷毀佇列

因為我們是使用malloc函式申請的記憶體，因此我們還需要手動銷毀記憶體：

int DestroyLinkedQueue(LinkedQueue *Q){
    QNode *p = Q->front, *s;
    //判斷p是否移動到隊尾的next
    while (p){
        //保存當前節點指標
        s = p;
        //p向后移動
        p = p->next;
        //銷毀當前節點
        free(s);
    }
    return 1;
}

到此我們就用順序存盤和鏈式存盤兩種方式實作了佇列，