零、前言

??「 資料結構 」 和 「 演算法 」 是密不可分的，兩者往往是「 相輔相成 」的存在，所以，在學習 「 資料結構 」 的程序中，不免會遇到各種「 演算法 」，
??到底是先學 資料結構 ，還是先學 演算法，我認為不必糾結這個問題，一定是一起學的，
??資料結構 常用的操作一般為：「 增 」「 刪 」「 改 」「 查 」，基本上所有的資料結構都是圍繞這幾個操作進行展開的，
??那么這篇文章，作者將用 「 九張動圖 」 來闡述一種 「 先進先出 」 的資料結構

「 佇列 」


🙉飯不食，水不飲，題必須刷🙉

C語言免費動漫教程，和我一起打卡！ 🌞《光天化日學C語言》🌞
LeetCode 太難？先看簡單題！ 🧡《C語言入門100例》🧡
資料結構難？不存在的！ 🌳《畫解資料結構》🌳
LeetCode 太簡單？演算法學起來！ 🌌《夜深人靜寫演算法》🌌
?? 佇列可以用 順序表 實作，也可以用 鏈表 實作，濃縮為以下三張圖：

佇列操作三部曲
佇列的鏈表實作
佇列的順序表實作
??看不懂沒有關系，我會把它拆開來一個一個講，首先來看一下今天要學習的內容目錄，

一、概念

1、佇列的定義

??佇列 是僅限在 一端 進行 插入，另一端 進行 洗掉 的 線性表，
??佇列 又被稱為 先進先出 （First In First Out） 的線性表，簡稱 FIFO ，

2、隊首

??允許進行元素洗掉的一端稱為 隊首，如下圖所示：

3、隊尾

??允許進行元素插入的一端稱為 隊尾，如下圖所示：

二、介面

1、可寫介面

1）資料入隊

??佇列的插入操作，叫做 入隊，它是將 資料元素 從 隊尾 進行插入的程序，如圖所示，表示的是 插入 兩個資料（綠色 和 藍色）的程序：

2）資料出隊

??佇列的洗掉操作，叫做 出隊，它是將 隊首 元素進行洗掉的程序，如圖所示，表示的是 依次 洗掉 兩個資料（紅色 和 橙色）的程序：

3）清空佇列

??佇列的清空操作，就是一直 出隊，直到佇列為空的程序，當 隊首 和 隊尾 重合時，就代表隊尾為空了，如圖所示：

2、只讀介面

1）獲取隊首資料

??對于一個佇列來說只能獲取 隊首 資料，一般不支持獲取 其它資料，

2）獲取佇列元素個數

??佇列元素個數一般用一個額外變數存盤，入隊 時加一，出隊 時減一，這樣獲取佇列元素的時候就不需要遍歷整個佇列，通過 O ( 1 ) O(1) O(1) 的時間復雜度獲取佇列元素個數，

3）佇列的判空

??當佇列元素個數為零時，就是一個 空隊，空隊 不允許 出隊 操作，

三、佇列的順序表實作

1、資料結構定義

對于順序表，在 C語言 中表現為 陣列，在進行 佇列的定義 之前，我們需要考慮以下幾個點：
??1）佇列資料的存盤方式，以及佇列資料的資料型別；
??2）佇列的大小；
??3）隊首指標；
??4）隊尾指標；

• 我們可以定義一個 堆疊 的 結構體，C語言實作如下所示：

#define DataType int       // (1)
#define maxn 100005        // (2)

struct Queue {             // (3)
    DataType data[maxn];   // (4)
    int head, tail;        // (5)
};

• ( 1 ) (1) (1) 用DataType這個宏定義來統一代表佇列中資料的型別，這里將它定義為整型，根據需要可以定義成其它型別，例如浮點型、字符型、結構體 等等；
• ( 2 ) (2) (2) maxn代表我們定義的佇列的最大元素個數；
• ( 3 ) (3) (3) Queue就是我們接下來會用到的 佇列結構體；
• ( 4 ) (4) (4) DataType data[maxn]作為佇列元素的存盤方式，即 陣列，資料型別為DataType，可以自行定制；
• ( 5 ) (5) (5) head即隊首指標，tail即隊尾指標，head == tail代表空隊；當佇列非空時，data[head]代表了隊首元素（而隊尾元素是不需要關心的）；

2、入隊

1、影片演示

??如圖所示，綠色元素 為新插入隊尾的資料，執行完畢以后，隊尾指標加一，隊首指標不變，需要注意的是，順序表實作時，隊尾指標指向的位置是沒有資料的，具體來看下代碼實作，

2、原始碼詳解

• 入隊 操作，算上函式引數串列，總共也才幾句話，代碼實作如下：

void QueueEnqueue(struct Queue *que, DataType dt) {  // (1)
    que->data[ que->tail ] = dt;                     // (2)
    que->tail = que->tail + 1;                       // (3)
}

• ( 1 ) (1) (1) que是一個指向佇列物件的指標，由于這個介面會修改佇列物件的成員變數，所以這里必須傳指標，否則，就會導致函式執行完畢，傳參物件沒有任何改變；
• ( 2 ) (2) (2) 將傳參的元素 入隊；
• ( 3 ) (3) (3) 將 隊尾指標 自增 1；
• 注意，這個介面在呼叫前，需要保證 隊尾指標 小于 佇列元素最大個數，即que->tail < maxn，
• 如果 C語言 寫的熟練，我們可以把 ( 2 ) (2) (2) 和 ( 3 ) (3) (3) 合成一句話，如下：

void QueueEnqueue(struct Queue *que, DataType dt) {
    que->data[ que->tail++ ] = dt;
}

• que->tail++運算式的值是自增前的值，并且自身進行了一次自增，

3、出隊

1、影片演示

??如圖所示，橙色元素 為原先的 隊首元素，執行 出隊 操作以后，黃色元素 成為當前的 隊首元素，執行完畢以后，隊首指標加一，由于是線性表實作，隊首元素前面的那些元素已經變成無效的了，具體來看下代碼實作，

2、原始碼詳解

• 出隊 操作，只需要簡單的改變，將 隊首指標 加一 即可，代碼實作如下：

void QueueDequeue(struct Queue* que) {
    ++que->head;
}

4、清空佇列

1、影片演示

??如圖所示，對于陣列來說，清空佇列的操作只需要將 隊首指標 和 隊尾指標 都置零 即可，資料不需要清理，下次繼續 入隊 的時候會將之前的記憶體重復利用，

2、原始碼詳解

• 清空佇列的操作只需要將 隊首指標 和 隊尾指標 都歸零即可，代碼實作如下：

void QueueClear(struct Queue* que) {
    que->head = que->tail = 0;
}

5、只讀介面

• 只讀介面包含：獲取隊首元素、獲取佇列大小、佇列的判空，實作如下：

DataType QueueGetFront(struct Queue* que) {
    return que->data[ que->head ];      // (1)
}
int QueueGetSize(struct Queue* que) {
    return que->tail - que->head;       // (2)
}
int QueueIsEmpty(struct Queue* que) {
    return !QueueGetSize(que);          // (3)
}

• ( 1 ) (1) (1) que->head代表了 隊首指標，即 隊首下標，所以真正的 隊首元素 是 que->data[ que->head ]；
• ( 2 ) (2) (2) 因為只有在 入隊 的時候，隊尾指標 加一；出隊 的時候，隊首指標 加一；所以 佇列元素個數 就是兩者的差值；
• ( 3 ) (3) (3) 當 佇列元素 個數為 零 時，佇列為空，

6、佇列的順序表實作原始碼

• 佇列的順序表實作的原始碼如下：

/**************************** 順序表 實作佇列 ****************************/
#define DataType int
#define maxn 100005

struct Queue {
    DataType data[maxn];
    int head, tail;
};

void QueueClear(struct Queue* que) {
    que->head = que->tail = 0;
}
void QueueEnqueue(struct Queue *que, DataType dt) {
    que->data[ que->tail++ ] = dt;
}
void QueueDequeue(struct Queue* que) {
    ++que->head;
}

DataType QueueGetFront(struct Queue* que) {
    return que->data[ que->head ];
}
int QueueGetSize(struct Queue* que) {
    return que->tail - que->head;
}
int QueueIsEmpty(struct Queue* que) {
    return !QueueGetSize(que);
}

/**************************** 順序表 實作佇列 ****************************/

四、佇列的鏈表實作

1、資料結構定義

對于鏈表，在進行 佇列的定義 之前，我們需要考慮以下幾個點：
??1）佇列資料的存盤方式，以及佇列資料的資料型別；
??2）佇列的大小；
??3）隊首指標；
??4）隊尾指標；

• 我們可以定義一個 佇列 的 結構體，C語言實作如下所示：

typedef int DataType;               // (1)
struct QueueNode;                   // (2)
struct QueueNode {                  // (3)
    DataType data;
    struct QueueNode *next;
};

struct Queue {
    struct QueueNode *head, *tail;  // (4)
    int size;                       // (5)
};

• ( 1 ) (1) (1) 佇列結點元素的 資料域，這里定義為整型；
• ( 2 ) (2) (2) struct QueueNode;是對 鏈表結點 的宣告；
• ( 3 ) (3) (3) 定義鏈表結點，其中DataType data代表 資料域；struct QueueNode *next代表 指標域；
• ( 4 ) (4) (4) head作為 隊首指標，tail作為 隊尾指標；
• ( 5 ) (5) (5) 由于 求鏈表長度 的演算法時間復雜度是 O ( n ) O(n) O(n) 的， 所以我們需要記錄一個size來代表現在佇列中有多少元素，每次 入隊時size自增，出隊時size自減，這樣在詢問 佇列 的大小的時候，就可以通過 O ( 1 ) O(1) O(1) 的時間復雜度，

2、入隊

1、影片演示

??如圖所示，head 為 隊首元素，tail 為 隊尾元素，vtx 為當前需要 入隊 的元素，即圖中的 橙色結點，入隊 操作完成后，隊尾元素 變為 vtx，即圖中 綠色結點，

2、原始碼詳解

• 入隊 操作，其實就是類似 尾插法，往鏈表尾部插入一個新的結點，代碼實作如下：

void QueueEnqueue(struct Queue *que, DataType dt) {
    struct QueueNode *insertNode = (struct QueueNode *) malloc( sizeof(struct QueueNode) );           
    insertNode->data = dt;                  // (1)
    insertNode->next = NULL;
    if(que->tail) {                         // (2)
        que->tail->next = insertNode;
        que->tail = insertNode;
    }else {
        que->head = que->tail = insertNode; // (3)
    }
    ++que->size;                            // (4)
}

• ( 1 ) (1) (1) 利用malloc生成一個鏈表結點insertNode，并且填充 資料域 和 指標域；
• ( 2 ) (2) (2) 如果當前 隊尾 不為空，則將insertNode作為 隊尾 的 后繼結點，并且更新insertNode作為新的 后繼結點；
• ( 3 ) (3) (3) 否則，隊首 和 隊尾 都為insertNode；
• ( 4 ) (4) (4) 佇列元素 加一；

3、出隊

1、影片演示

??如圖所示，head 為 隊首元素，tail 為 隊尾元素，temp 為當前需要 出隊 的元素，即圖中的 橙色結點，出隊 操作完成后，隊首元素 變為之前 head 的 后繼結點，即圖中 綠色結點，

2、原始碼詳解

• 出隊 操作，由于鏈表頭結點就是 隊首，其實就是洗掉這個鏈表的頭結點的程序，代碼實作如下：

void QueueDequeue(struct Queue* que) {
    struct QueueNode *temp = que->head;  // (1)
    que->head = temp->next;              // (2)
    free(temp);                          // (3)
    --que->size;                         // (4)
    if(que->size == 0) {                 // (5)
        que->tail = NULL;
    } 
}

• ( 1 ) (1) (1) 將 隊首 保存到temp中；
• ( 2 ) (2) (2) 將 隊首 的 后繼結點 作為新的 隊首；
• ( 3 ) (3) (3) 釋放之前 隊首 對應的記憶體；
• ( 4 ) (4) (4) 佇列元素減一；
• ( 5 ) (5) (5) 當佇列元素為空時，別忘了將 隊尾 指標置空；

4、清空佇列

1、影片演示

??清空佇列 可以理解為：不斷的 出隊，直到 佇列元素 個數為零為止，由于鏈表結點是動態申請的記憶體，所以在沒有其它結點參考時，是需要釋放記憶體的，不像陣列那樣直接將 隊首指標 和 隊尾指標 置空就行的，

2、原始碼詳解

• 對于鏈表而言，清空佇列 的操作需要洗掉每個鏈表結點，代碼實作如下：

void QueueClear(struct Queue* que) {
    while(!QueueIsEmpty(que)) {     // (1)
        QueueDequeue(que);          // (2)
    }
}

• ( 1 ) (1) (1) - ( 2 ) (2) (2) 的每次操作其實就是一個 出隊 的程序，如果 佇列 不為空；則進行 出隊 操作，直到 隊里 為空；

5、只讀介面

• 只讀介面包含：獲取隊首元素、獲取佇列大小、佇列的判空，實作如下：

DataType QueueGetFront(struct Queue* que) {
    return que->head->data;              // (1)
}
int QueueGetSize(struct Queue* que) {
    return que->size;                    // (2)
}
int QueueIsEmpty(struct Queue* que) {
    return !QueueGetSize(que);           // (3)
}

• ( 1 ) (1) (1) que->head作為 隊首指標，它的 資料域 data就是 隊首元素的值，回傳即可；
• ( 2 ) (2) (2) size記錄的是 佇列元素 的個數；
• ( 3 ) (3) (3) 當 佇列元素 個數為 零 時，佇列為空，

6、佇列的鏈表實作原始碼

/**************************** 鏈表 實作佇列 ****************************/
typedef int DataType;

struct QueueNode;
struct QueueNode {
    DataType data;
    struct QueueNode *next;
};

struct Queue {
    struct QueueNode *head, *tail;
    int size;
};

void QueueEnqueue(struct Queue *que, DataType dt) {
    struct QueueNode *insertNode = (struct QueueNode *) malloc( sizeof(struct QueueNode) );
    insertNode->data = dt;
    insertNode->next = NULL;
    if(que->tail) {
        que->tail->next = insertNode;
        que->tail = insertNode;
    }else {
        que->head = que->tail = insertNode;
    }
    ++que->size;
}

void QueueDequeue(struct Queue* que) {
    struct QueueNode *temp = que->head;
    que->head = temp->next;
    free(temp);
    --que->size;
    if(que->size == 0) {
        que->tail = NULL;
    } 
}

DataType QueueGetFront(struct Queue* que) {
    return que->head->data;
}
int QueueGetSize(struct Queue* que) {
    return que->size;
}
int QueueIsEmpty(struct Queue* que) {
    return !QueueGetSize(que);
}
void QueueClear(struct Queue* que) {
    que->head = que->tail = NULL;
    que->size = 0;
}

/**************************** 鏈表 實作佇列 ****************************/

五、兩種實作的優缺點

1、順序表實作

??在利用順序表實作佇列時，入隊 和 出隊 的常數時間復雜度低，且 清空佇列 操作相比 鏈表實作 能做到 O ( 1 ) O(1) O(1)，唯一的不足之處是：需要預先申請好空間，而且當空間不夠時，需要進行擴容，擴容方式本文未提及，可以參考以下文章：《C/C++ 面試 100 例》（四）vector 擴容策略，
??當然，可以采用 回圈佇列，能夠很大程度上避免擴容問題，但是當 入隊速度 大于 出隊速度 時，不免還是會遇到擴容的問題，

2、鏈表實作

??在利用鏈表實作佇列時，入隊 和 出隊 的常數時間復雜度略高，主要是每插入一個佇列元素都需要申請空間，每洗掉一個佇列元素都需要釋放空間，且 清空佇列 操作是 O ( n ) O(n) O(n) 的，直接將 隊首指標 和 隊尾指標 置慷訓導致記憶體泄漏，
??好處就是：不需要預先分配空間，且在記憶體允許范圍內，可以一直 入隊，沒有順序表的限制，當然，鏈表的實作明顯比陣列實作要復雜，編碼的時候容易出錯，

??需要注意的是，本文在講解程序中，順序表實作 的 隊尾 和 鏈表實作 的 隊尾 不是一個概念，順序表實作的隊尾沒有實際元素值，而鏈表實作的則不然，請自行加以區分，

六、佇列的入門

好啦，接下來，讓我們做幾個佇列的題目練習一下吧，

1、滑動視窗

LeetCode 933. 最近的請求次數
LeetCode 346. 資料流中的移動平均值

2、廣度優先搜索

LeetCode 542. 01 矩陣
LeetCode 994. 腐爛的橘子
LeetCode 116. 填充每個節點的下一個右側節點指標

七、佇列的進階

1、輔助佇列

LeetCode 225. 用佇列實作堆疊

2、單調佇列

LeetCode 1696. 跳躍游戲 VI
LeetCode 1438. 絕對差不超過限制的最長連續子陣列
LeetCode 239. 滑動視窗最大值
LeetCode1425. 帶限制的子序列和

• 關于 「 佇列 」 的內容到這里就結束了，
• 如果還有不懂的問題，可以 「 想方設法 」找到作者的「 聯系方式 」 ，線上溝通交流，

• 有關🌳《畫解資料結構》🌳 的原始碼均開源，鏈接如下：《畫解資料結構》

🙉飯不食，水不飲，題必須刷🙉
C語言免費動漫教程，和我一起打卡！ 🌞《光天化日學C語言》🌞
LeetCode 太難？先看簡單題！ 🧡《C語言入門100例》🧡
資料結構難？不存在的！ 🌳《畫解資料結構》🌳
LeetCode 太簡單？演算法學起來！ 🌌《夜深人靜寫演算法》🌌