- 第 112篇 -
Date: 2025 - 07 - 20
Author: 鄭龍浩（仟墨）

隊列（Queue）

1 基本介紹

1.1 定義

隊列（Queue）是一種先進先出（FIFO, First-In-First-Out）的線性數據結構，只允許在隊尾插入（入隊）、在隊頭刪除（出隊）

1.2 棧 與 隊列的區別

• 棧 是只允許一端進行插入或刪除的線性表 –> 所以后進先出（在棧頂進行插入刪除）
• 隊列 是只允許在一端進行插入，在另一端刪除的線性表 –> 所以先進先出（在隊尾插入，隊頭刪除）
• 先進先出：FIFO（First In First Out)

1.3 重要術語

隊頭、隊尾、空隊尾

隊頭：允許刪除的一端

隊尾：允許插入的一端

空隊尾：沒有任何元素的隊列

2 基本操作

• 初始化：InitQueue(*Q)
• 清空：ClearQueue(*Q)
• 銷毀：DestroyQueue(*Q)
• 入隊：EnQueue(*Q, ElemType x)
• 出隊：DeQueue(*Q, ElelType* x)
• 讀取隊頭元素：GetHeadQueue(*Q, ElemType* x)
• 判斷是否為空：IsEmpty(*Q)
• 判斷是否已滿：IsFull(Queue *Q)（只有順序隊列有這個）
• 隊列長度：QueueLength(Queue *Q)
• 打印：PrintQueue(*Q)

3 順序隊列(循環版本)

兩種版本

有好幾個版本

注意：只有帶size或tag參數的隊列結構不需要浪費空間，即浪費最后一個存儲單元，不帶這倆參數的版本，如果不空出最后一個存儲單元，就無法通過 rear == fron 判斷出來：是滿？是空？

當空出一個存儲單元的時候就可以判斷出是滿還是空了

所以如果不帶size或tag參數就必然要浪費一個存儲單元，但是從整的結構來說，這樣反而節省了空間，因為帶了size或者tag的參數，每個節點都會多個變量，所以實際上來說，并沒節省。

版本1 - 指向指向隊尾元素的下一個位置（即隊尾后邊）

• 版本1.1 - rear 指向隊尾后邊 且 結構中無size或tag參數
  • 必須空出最后一個存儲單元
  • 初始化時，各參數默認為：
    • front = 0
    • rear = 0
  • 隊空條件：front == rear
  • 隊滿條件：(rar + 1) % MaxSize == front
• 版本1.2 - raer 指向隊尾后邊 且 結構中有size參數
  • 不需要空出任何存儲單元
  • 初始化時，各參數默認為：
    • front = 0
    • rear = 0
    • size = 0
  • 可以直接通過size判斷隊列的狀態
  • 隊空條件：size = 0
  • 隊滿條件：size == MaxSize
• 版本1.3 - rear 指向隊尾后邊 且 結構中有tag參數
  • 不需要空出任何存儲單元
  • 初始化時，各參數默認為：
    • front = 0
    • rear = 0
    • tag= 0（初始化相當于上一次操作出隊）
  • 通過tag標記出最后一次操作是入隊還是出隊（0是出隊，1是入隊）
  • 隊空條件：front == rear && tag == 0（如果上一次操作是出隊tag==0，出現front == rear 就是隊空）
  • 隊滿條件：front == rear && tag == 1（如果上一次操作是入隊tag==1，出現front == raer 就是隊滿

版本2 - rear 指向隊尾元素

• 版本2.1 - rear 指向隊尾 且 結構中無size或tag參數

  • 必須空出最后一個存儲單元
  • 初始化時，各參數默認為：
    • front = 0
    • rear = -1
  • 隊空條件：(rear + 1) % MaxSize == front
  • 隊滿條件：(rear + 2) % MaxSize == front

• 版本2.2 - rear 指向隊尾 且 結構中有size參數

  • 不需要空出存儲單元
  • 初始化時，各參數默認為：
    • front = 0
    • rear = -1
    • size = 0
  • 通過size變量直接判斷隊列的狀態
  • 隊空條件：size == 0
  • 隊滿條件：size == MaxSize

• 版本2.3 - rear 指向隊尾 且 結構中有tag參數

  • 不需要空出存儲單元

  • 初始化時，各參數默認為：

    • front = 0
    • rear = -1
    • tag= 0（初始化相當于上一次操作出隊）

  • 通過tag標記出最后一次操作是出隊還是入隊（0是出隊，1是入隊）

  • 隊空條件：front == (rear + 1) % MaxSize && tag == 0

  • 隊滿條件：front == (rear + 1) % MaxSize && tag == 1

兩種版本區別

版本1：rear 指向隊尾的下一個位置

front 指向隊頭元素，rear 指向下一個可插入的位置。隊列長度計算為 (rear - front + MaxSize) % MaxSize，隊空條件是 front == rear，隊滿條件是 (rear + 1) % MaxSize == front。此版本邏輯清晰，計算簡單，是最常用的實現方式。

版本2：rear 指向隊尾元素

front 指向隊頭元素，rear 直接指向隊尾元素。隊列長度計算為 (rear - front + 1 + MaxSize) % MaxSize，隊空條件是 (rear + 1) % MaxSize == front，隊滿條件是 (rear + 2) % MaxSize == front。此版本需要額外調整計算，容易出錯，一般不建議使用。

版本1.1 - rear指向隊尾后邊 且 無 size 或 tag

• 先進先出 -> 隊尾進，隊頭出

• 隊頭指針：front 指向隊頭元素

• 隊尾指針：rear 指向隊尾元素的后一個位置

• 必須知道：即使是順序隊列，隊頭指針也不可能一直指向data[0]

  初始化后，如果一直入隊操作，隊頭指針肯定是一直指向0的，但是如果執行了出隊操作，那么隊頭指針會指向1，再執行出隊操作，會指向2… –> 現在的front指向2，隊頭元素是data[2]

  假設此時隊尾指針指向的是MaxSize-1，然后進行入隊操作，執行完入隊以后，隊尾指針不會指向MaxSize而是0，

  也就是要將線性的結構轉換為一個環形的、循環的結構，方法如下：

  Q->rear = (Q->rear + 1) % MaxSize
  

  也就是當rear指向線性結構的末尾的時候要從頭開始

  因為現在的data[0]和data[1]都是空的并且訪問data[MaxSize]會越界（因為數組索引是0~MaxSize），所以rear要指向0，如果再入隊操作，在data[0]的位置會存儲一個值，然后rear指向1，此時僅有一個data[1]還未存儲數據

  注意了！！！！

  那么這個位置是否可以存儲數據呢？

  答案是否定的， 我們必須犧牲一個元素在隊列的末尾，原因如下：

  因為判斷隊列是否為空以及初始化的時候都是front == rear

  如果真的在執行一次入隊操作，隊尾元素會是data[1]，而rear指向了2，

  那么此時的front和rear都同時指向2，那么我到底是將這種情況歸為滿隊，還是空隊呢，所以為了避免這種情況的發生，統一約定：

  • 隊列的最后一個位置要空出來（犧牲一個存儲單元）

  • 隊列已滿的條件：rear下一個位置是front，即

    (Q->rear + 1) % MaxSize == Q->front
    

  • 隊列為空的條件：

    Q->front == Q->rear
    

• 使用模運算將線狀的存儲空間在邏輯上變成了環狀

SeqQueue.h

#pragma once
#include "stdio.h"
#include "stdlib.h"
#include "stdbool.h"
#define MaxSize 10
typedef int ElemType;
typedef struct {ElemType data[MaxSize]; // 靜態數組存放元素int front, rear; // 隊頭指針 隊尾指針
}SeqQueue;// 初始化
void InitQueue(SeqQueue* Q);// 銷毀隊列
void DestroyQueue(SeqQueue* Q);// 清空隊列
void ClearQueue(SeqQueue* Q);// 判斷隊列是否為空
bool IsEmpty(SeqQueue* Q);// 入隊
bool EnQueue(SeqQueue* Q, ElemType x);// 出隊
bool DeQueue(SeqQueue* Q, ElemType* x);// 讀取隊頭元素
bool GetHeadQueue(SeqQueue* Q, ElemType* x);// 判斷隊列是否已滿
bool IsFull(SeqQueue* Q);// 隊列長度
int QueueLength(SeqQueue* Q);// 打印
void PrintQueue(SeqQueue* Q);

SeqQueue.c

#include "sequence_queue.h"
#include "stdio.h"
#include "stdlib.h"// 初始化
void InitQueue(SeqQueue* Q) {// 隊頭 == 隊尾 且都 指向0Q->rear = Q->front = 0;
}// 銷毀隊列
void DestroyQueue(SeqQueue* Q) {Q->front = Q->rear = 0;
}// 清空隊列
void ClearQueue(SeqQueue* Q) {Q->front = Q->rear = 0;
}// 判斷隊列是否為空
bool IsEmpty(SeqQueue* Q) {return Q->front == Q->rear;
}// 入隊
bool EnQueue(SeqQueue* Q, ElemType x) {if (IsFull(Q)) return false; // 隊列已滿，不能入隊Q->data[Q->rear] = x;Q->rear = (Q->rear + 1) % MaxSize; // 隊尾指針要一直保持在 0 ~ MaxSize-1之間return true; // 入隊成功
}// 出隊
bool DeQueue(SeqQueue* Q, ElemType* x) {if (IsEmpty(Q)) return false; // 空隊列不能刪除*x = Q->data[Q->front];Q->front = (Q->front + 1) % MaxSize;return true;
}// 讀取隊頭元素
bool GetHeadQueue(SeqQueue* Q, ElemType* x) {if (IsEmpty(Q)) return false;*x = Q->data[Q->front];return true;
}// 判斷隊列是否已滿
bool IsFull(SeqQueue* Q) {return (Q->rear + 1) % MaxSize == Q->front;
}// 隊列長度
int QueueLength(SeqQueue* Q) {return (Q->rear - Q->front + MaxSize) % MaxSize;
}// 打印
void PrintQueue(SeqQueue* Q) {if (IsEmpty(Q)) {printf("隊列為空\n");return;}printf("隊頭 --> ");int cur = Q->front; // 遍歷下標while (cur != Q->rear) {printf("%d -> ", Q->data[cur]);cur = (cur + 1) % MaxSize;}printf("隊尾\n");
}

版本1.2 - rear指向隊尾后邊 且 有 size

SeqQueue.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>#define MaxSize 10
typedef int ElemType;typedef struct {ElemType data[MaxSize]; // 靜態數組存放元素int front, rear;        // 隊頭指針和隊尾指針int size;               // 隊列當前長度
} SeqQueue;// 初始化隊列
void InitQueue(SeqQueue* Q);// 銷毀隊列
void DestroyQueue(SeqQueue* Q);// 清空隊列
void ClearQueue(SeqQueue* Q);// 判斷隊列是否為空
bool IsEmpty(SeqQueue* Q);// 判斷隊列是否已滿
bool IsFull(SeqQueue* Q);// 入隊
bool EnQueue(SeqQueue* Q, ElemType x);// 出隊
bool DeQueue(SeqQueue* Q, ElemType* x);// 讀取隊頭元素
bool GetHeadQueue(SeqQueue* Q, ElemType* x);// 獲取隊列長度
int QueueLength(SeqQueue* Q);// 打印隊列
void PrintQueue(SeqQueue* Q);

SeqQueue.c

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>#define MaxSize 10
typedef int ElemType;typedef struct {ElemType data[MaxSize]; // 靜態數組存放元素int front, rear;        // 隊頭指針和隊尾指針int size;               // 隊列當前長度
} SeqQueue;// 初始化隊列
void InitQueue(SeqQueue* Q) {Q->front = Q->rear = 0;Q->size = 0;
}// 銷毀隊列
void DestroyQueue(SeqQueue* Q) {Q->front = Q->rear = 0;Q->size = 0;
}// 清空隊列
void ClearQueue(SeqQueue* Q) {Q->front = Q->rear = 0;Q->size = 0;
}// 判斷隊列是否為空
bool IsEmpty(SeqQueue* Q) {return Q->size == 0;
}// 判斷隊列是否已滿
bool IsFull(SeqQueue* Q) {return Q->size == MaxSize;
}// 入隊
bool EnQueue(SeqQueue* Q, ElemType x) {if (IsFull(Q)) return false;Q->data[Q->rear] = x;Q->rear = (Q->rear + 1) % MaxSize;Q->size++;return true;
}// 出隊
bool DeQueue(SeqQueue* Q, ElemType* x) {if (IsEmpty(Q)) return false;*x = Q->data[Q->front];Q->front = (Q->front + 1) % MaxSize;Q->size--;return true;
}// 讀取隊頭元素
bool GetHeadQueue(SeqQueue* Q, ElemType* x) {if (IsEmpty(Q)) return false;*x = Q->data[Q->front];return true;
}// 獲取隊列長度
int QueueLength(SeqQueue* Q) {return Q->size;
}// 打印隊列
void PrintQueue(SeqQueue* Q) {if (IsEmpty(Q)) {printf("隊列為空\n");return;}printf("隊頭 --> ");int cur = Q->front;for (int i = 0; i < Q->size; i++) {printf("%d -> ", Q->data[cur]);cur = (cur + 1) % MaxSize;}printf("隊尾\n");
}

版本1.3 - rear指向隊尾后邊 且 有 tag

SeqQueue.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>#define MaxSize 10
typedef int ElemType;typedef struct {ElemType data[MaxSize]; // 靜態數組存放元素int front, rear;        // 隊頭指針和隊尾指針bool tag;               // 最近操作標記: true為入隊, false為出隊
} SeqQueue;// 初始化隊列
void InitQueue(SeqQueue* Q);// 銷毀隊列
void DestroyQueue(SeqQueue* Q);// 清空隊列
void ClearQueue(SeqQueue* Q);// 判斷隊列是否為空
bool IsEmpty(SeqQueue* Q);// 判斷隊列是否已滿
bool IsFull(SeqQueue* Q);// 入隊
bool EnQueue(SeqQueue* Q, ElemType x);// 出隊
bool DeQueue(SeqQueue* Q, ElemType* x);// 讀取隊頭元素
bool GetHeadQueue(SeqQueue* Q, ElemType* x);// 獲取隊列長度
int QueueLength(SeqQueue* Q);// 打印隊列
void PrintQueue(SeqQueue* Q);

SeqQueue.c

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>#define MaxSize 10
typedef int ElemType;typedef struct {ElemType data[MaxSize]; // 靜態數組存放元素int front, rear;        // 隊頭指針和隊尾指針bool tag;               // 最近操作標記: true為入隊, false為出隊
} SeqQueue;// 初始化隊列
void InitQueue(SeqQueue* Q) {Q->front = Q->rear = 0;Q->tag = false;
}// 銷毀隊列
void DestroyQueue(SeqQueue* Q) {Q->front = Q->rear = 0;Q->tag = false;
}// 清空隊列
void ClearQueue(SeqQueue* Q) {Q->front = Q->rear = 0;Q->tag = false;
}// 判斷隊列是否為空
bool IsEmpty(SeqQueue* Q) {return Q->front == Q->rear && Q->tag == false;
}// 判斷隊列是否已滿
bool IsFull(SeqQueue* Q) {return Q->front == Q->rear && Q->tag == true;
}// 入隊
bool EnQueue(SeqQueue* Q, ElemType x) {if (IsFull(Q)) return false;Q->data[Q->rear] = x;Q->rear = (Q->rear + 1) % MaxSize;Q->tag = true;return true;
}// 出隊
bool DeQueue(SeqQueue* Q, ElemType* x) {if (IsEmpty(Q)) return false;*x = Q->data[Q->front];Q->front = (Q->front + 1) % MaxSize;Q->tag = false;return true;
}// 讀取隊頭元素
bool GetHeadQueue(SeqQueue* Q, ElemType* x) {if (IsEmpty(Q)) return false;*x = Q->data[Q->front];return true;
}// 獲取隊列長度
int QueueLength(SeqQueue* Q) {if (IsFull(Q)) return MaxSize;return (Q->rear - Q->front + MaxSize) % MaxSize;
}// 打印隊列
void PrintQueue(SeqQueue* Q) {if (IsEmpty(Q)) {printf("隊列為空\n");return;}printf("隊頭 --> ");int cur = Q->front;int count = QueueLength(Q);for (int i = 0; i < count; i++) {printf("%d -> ", Q->data[cur]);cur = (cur + 1) % MaxSize;}printf("隊尾\n");
}

4 鏈式隊列

4.1 兩種版本區別

函數/操作	帶頭結點版本	不帶頭結點版本
初始化隊列	創建頭結點，front/rear指向頭結點	front/rear初始化為NULL
入隊操作	直接插入到rear->next	需先判斷是否為空隊列再插入
出隊操作	刪除front->next結點	直接刪除front結點
判斷隊列空	檢查front == rear	檢查front == NULL
獲取隊頭元素	訪問front->next->data	訪問front->data
清空隊列	釋放所有數據結點，保留頭結點	釋放所有結點
銷毀隊列	釋放頭結點和隊列結構體	直接釋放隊列結構體
隊列長度	從front->next開始計數	從front開始計數
打印隊列	從front->next開始打印	從front開始打印
內存方面	多占用1個頭結點空間	不多占用

4.2 鏈式隊列_帶頭結點

#include "stdio.h"
#include "stdlib.h"
#include "stdbool.h"typedef int ElemType;
// 結點結構
typedef struct LinkNode {ElemType data;struct LinkNode* next;
}LinkNode;// 鏈式隊列結構
typedef struct LinkQueue {LinkNode *front, *rear;
}LinkQueue;#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>typedef int ElemType;// 結點結構
typedef struct LinkNode {ElemType data;struct LinkNode* next;
} LinkNode;// 鏈式隊列結構
typedef struct LinkQueue {LinkNode *front, *rear;
} LinkQueue;// 函數聲明
// 初始化
void InitQueue(LinkQueue* Q);
// 清空
void ClearQueue(LinkQueue* Q);
// 銷毀
void DestroyQueue(LinkQueue** Q);
// 入隊
bool EnQueue(LinkQueue* Q, ElemType x);
// 出隊
bool DeQueue(LinkQueue* Q, ElemType* x);
// 判斷隊空
bool IsEmpty(LinkQueue* Q);
// 讀取隊頭元素
bool GetHead(LinkQueue* Q, ElemType* x);
// 隊列長度
int QueueLength(LinkQueue* Q);
// 打印
void PrintQueue(LinkQueue* Q);// 函數實現
// 初始化（帶頭結點）
void InitQueue(LinkQueue* Q) {Q->front = Q->rear = (LinkNode*)malloc(sizeof(LinkNode));Q->front->next = NULL; // Q->fornt 是頭結點 再加->next是第一個結點
}// 清空（帶頭結點）
void ClearQueue(LinkQueue* Q) {LinkNode* cur = Q->front->next;// 釋放所有結點while (cur != NULL) {LinkNode* temp = cur;cur=cur->next;free(temp);}Q->rear = Q->front = NULL; // 將頭指針和尾指針指向頭結點并且置空
}// 銷毀（帶頭結點）銷毀要用二級指針
void DestroyQueue(LinkQueue** Q) {ClearQueue(*Q);// 釋放頭結點free((*Q)->front);// 此時頭尾指針指向頭結點，釋放誰都一樣// 釋放隊列結構free(*Q);Q = NULL;
}// 入隊（帶頭結點） 
bool EnQueue(LinkQueue* Q, ElemType x) {LinkNode* NewNode = (LinkNode*)malloc(sizeof(LinkNode));if (!NewNode) return false; // 申請內存失敗返回falseNewNode->data = x; // 新結點存儲值NewNode->next = NULL; // 新結點（最后一個結點）的后驅是NULLQ->rear->next = NewNode; // 新結點插入到rear后邊Q->rear = NewNode; // rear指向剛剛插入的元素return true;
}// 出隊（帶頭結點）
bool DeQueue(LinkQueue* Q, ElemType* x) {if (IsEmpty(Q)) return false; // 空隊列無法出隊LinkNode* first = Q->front->next; // 將隊列第一個存儲單元（要刪除的單元）位置保存下來，以防將頭結點的后繼連接到第二個存儲單元后，第一個存儲單元的位置丟失*x = first->data; // 將隊列第一個數據讀取出來Q->front->next = first->next; // 將頭結點后繼連接到第二個存儲單元--> 這樣第一個存儲單元地址就不會保存在隊列當中了，也就相當于刪除了，或者出隊// 如果只有一個存儲結點的話，那么rear隊尾指針指向的就是第一個存儲單元，當把這最后一個存儲單元刪除的時候rear就不該指向這個“已經刪除的結點”了，而應該指向“頭結點”，相當于初始化了if (Q->rear == first) Q->rear = Q->front;free(first);return true;
}// 判斷隊空（帶頭結點）
bool IsEmpty(LinkQueue* Q) {return Q->front == Q->rear;
}// 讀取隊頭元素
bool GetHead(LinkQueue* Q, ElemType* x) {if (IsEmpty(Q)) return false; // 空隊*x = Q->front->next->data;return true;
}// 隊列長度（帶頭結點）
int QueueLength(LinkQueue* Q) {if (IsEmpty(Q)) return 0;LinkNode* cur = Q->front->next; // 從第一個存儲結點開始int len = 0;while (cur != NULL) {len++;cur = cur->next;}return len;
}// 打印（帶頭結點）
void PrintQueue(LinkQueue* Q) {LinkNode* cur = Q->front->next; // 從第一個存儲結點開始printf("隊頭 -> ");while (cur != NULL) {printf("%d -> ", cur->data);cur = cur->next;}printf("隊尾\n");
}
int main(void) {return 0;
}

4.3 鏈式隊列_無頭結點

#include "stdio.h"
#include "stdlib.h"
#include "stdbool.h"typedef int ElemType;
// 結點結構
typedef struct LinkNode {ElemType data;struct LinkNode* next;
}LinkNode;// 鏈式隊列結構
typedef struct LinkQueue {LinkNode *front, *rear;
}LinkQueue;#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>typedef int ElemType;// 結點結構
typedef struct LinkNode {ElemType data;struct LinkNode* next;
} LinkNode;// 鏈式隊列結構
typedef struct LinkQueue {LinkNode *front, *rear;
} LinkQueue;// 函數聲明
// 初始化
void InitQueue(LinkQueue* Q);
// 清空
void ClearQueue(LinkQueue* Q);
// 銷毀
void DestroyQueue(LinkQueue** Q);
// 入隊
bool EnQueue(LinkQueue* Q, ElemType x);
// 出隊
bool DeQueue(LinkQueue* Q, ElemType* x);
// 判斷隊空
bool IsEmpty(LinkQueue* Q);
// 讀取隊頭元素
bool GetHead(LinkQueue* Q, ElemType* x);
// 隊列長度
int QueueLength(LinkQueue* Q);
// 打印
void PrintQueue(LinkQueue* Q);// 函數實現
// 初始化（無頭結點）
void InitQueue(LinkQueue* Q) {// 初始化時，頭尾都指向NULLQ->front = Q->rear = NULL;
}// 清空（無頭結點）
void ClearQueue(LinkQueue* Q) {LinkNode* cur = Q->front;// 釋放所有結點while (cur != NULL) {LinkNode* temp = cur;cur=cur->next;free(temp);}Q->rear = Q->front = NULL; // 將頭指針和尾指針指向NULL
}// 銷毀（無頭結點）應使用二級指針-->因為銷毀后要將Q置空
void DestroyQueue(LinkQueue** Q) {ClearQueue(*Q); // 清空// 釋放隊列結構free(*Q);Q = NULL; // 給Q置空
}// 入隊（無頭結點） 
bool EnQueue(LinkQueue* Q, ElemType x) {// 有頭節點的時候入隊不需要額外判斷是否為空隊，因為頭尾指針此時都是指向的頭結點，操作相同的LinkNode* NewNode = (LinkNode*)malloc(sizeof(LinkNode));if (!NewNode) return false; // 申請內存失敗返回falseNewNode->data = x; // 新結點存儲值NewNode->next = NULL; // 新結點（最后一個結點）的后驅是NULL// 一句：空隊修改隊尾隊頭，不是空隊列只修改尾指針if (IsEmpty(Q)) {// 更新隊頭隊尾指針Q->front = NewNode; // 如果是空隊列，因為沒有頭結點的存在，所以要將這個新的結點放到第一個結點的位置，而Q->front就是指的第一個結點（如果有頭結點的話，指的是頭結點，而Q->front->next指的是第一個結點）Q->rear = NewNode; // 更新尾指針：rear指向剛剛插入的元素} else { // 當不是空隊的時候-Q->rear->next = NewNode; // 新結點插入到rear后邊Q->rear = NewNode; // 更新尾指針：rear指向剛剛插入的元素}return true;
}// 出隊（無頭結點）
bool DeQueue(LinkQueue* Q, ElemType* x) {if (IsEmpty(Q)) return false; // 空隊列無法出隊LinkNode* First = Q->front; // 將隊列第一個存儲單元（要刪除的單元）位置保存下來，以防第二個結點變為第一個結點地址后，第一個結點地址無法釋放*x = First->data; // 將隊列第一個數據讀取出來// 注意：如果是只有一個結點，執行出隊的話，要改變隊尾隊頭指針指向，因為當是空隊的時候隊頭隊尾指針都要指向NULLif (Q->rear == First) {Q->front = NULL;Q->rear = NULL;} else { // 當有多個結點的時候，只需要改變隊頭指向即可Q->front = First->next; // 將第一個結點改為原第二個結點}// 別忘了：釋放原來第一個結點free(First); // 釋放原第一個結點return true;
}// 判斷隊空
bool IsEmpty(LinkQueue* Q) {return Q->front == NULL; // 當是空隊列的時候頭指針指向NULL
}// 讀取隊頭元素（無頭結點）
bool GetHead(LinkQueue* Q, ElemType* x) {if (IsEmpty(Q)) return false; // 空隊*x = Q->front->data;return true;
}// 隊列長度（無頭結點）
int QueueLength(LinkQueue* Q) {if (IsEmpty(Q)) return 0;LinkNode* cur = Q->front; // 從第一個結點開始int len = 0;while (cur != NULL) {len++;cur = cur->next;}return len;
}// 打印（無頭結點）
void PrintQueue(LinkQueue* Q) {LinkNode* cur = Q->front; // 從第一個結點開始printf("隊頭 -> ");while (cur != NULL) {printf("%d -> ", cur->data);cur = cur->next;}printf("隊尾\n");
}
int main(void) {return 0;
}

5 雙端隊列

除了順序隊列和鏈式隊列以外，還有一種隊列叫做雙端隊列

首先，先來將棧、普通隊列與雙端隊列比較一下，都為線性表

• 棧：只允許從一端插入刪除
• 普通隊列：只允許從一端插入，只允許從另一端刪除
• 雙端隊列：只允許從兩端插入或刪除 –> 隊頭隊尾都可以插入和刪除
  • 輸入受限的雙端隊列：允許一端插入刪除；另一端只能允許插入 –> 隊頭只能刪除，隊尾既可以插入和刪除
  • 輸出受限的雙端隊列：允許一端插入刪除；另一端只能允許刪除 –> 隊頭可以插入和刪除，隊尾只能插入