隊列（queue）是一種遵循先入先出規則的線性數據結構。顧名思義，隊列模擬了排隊現象，即新來的人不斷加入隊列尾部，而位于隊列頭部的人逐個離開。

如圖 5-4 所示，我們將隊列頭部稱為“隊首”，尾部稱為“隊尾”，將把元素加入隊尾的操作稱為“入隊”，刪除隊首元素的操作稱為“出隊”。

圖 5-4 ? 隊列的先入先出規則

5.2.1 ? 隊列常用操作?

隊列的常見操作如表 5-2 所示。需要注意的是，不同編程語言的方法名稱可能會有所不同。我們在此采用與棧相同的方法命名。

表 5-2 ? 隊列操作效率

方法名	描述	時間復雜度
push()	元素入隊，即將元素添加至隊尾
pop()	隊首元素出隊
peek()	訪問隊首元素

我們可以直接使用編程語言中現成的隊列類：

/* 初始化隊列 */
queue<int> queue;/* 元素入隊 */
queue.push(1);
queue.push(3);
queue.push(2);
queue.push(5);
queue.push(4);/* 訪問隊首元素 */
int front = queue.front();/* 元素出隊 */
queue.pop();/* 獲取隊列的長度 */
int size = queue.size();/* 判斷隊列是否為空 */
bool empty = queue.empty();

5.2.2 ? 隊列實現?

為了實現隊列，我們需要一種數據結構，可以在一端添加元素，并在另一端刪除元素，鏈表和數組都符合要求。

1. ? 基于鏈表的實現?

如圖 5-5 所示，我們可以將鏈表的“頭節點”和“尾節點”分別視為“隊首”和“隊尾”，規定隊尾僅可添加節點，隊首僅可刪除節點。

圖 5-5 ? 基于鏈表實現隊列的入隊出隊操作

以下是用鏈表實現隊列的代碼：

#include <iostream>
#include <vector>
#include <stdexcept> // 用于異常處理
#include <stack>
using namespace std;
/* 用列表實現隊列的代碼*/struct ListNode {int val;ListNode* next;ListNode(int value) : val(value), next(nullptr) {}
};// 隊列類的定義
class LinkedListQueue
{private:ListNode* front, * rear; //隊列頭，隊列尾int queSize; //隊列長度//釋放鏈表內存void freeMemoryLinkedList(ListNode* node) {while (node != nullptr) {ListNode* temp = node;node = node->next;delete temp;}}public:// 構造函數LinkedListQueue() : front(nullptr), rear(nullptr), queSize(0) {}//析構函數~LinkedListQueue() {freeMemoryLinkedList(front);}//獲取隊列大小int size() {return queSize;}//判斷隊列是否為空bool isEmpty() {return queSize == 0;}//入隊 (尾插) void push(int num) {ListNode* node = new ListNode(num);if (front == nullptr) { // 隊列為空，頭尾部指向新節點front = node;rear = node;}else { // 隊列不為空，尾插rear->next = node;rear = node;}queSize++;}//出隊 (刪除頭節點)int pop() {if (isEmpty()){throw out_of_range("隊列為空，不能出隊");}int val = front->val;//先保存隊首值ListNode* temp = front;	//備份隊節點front = front->next;	 //指向下一節點delete temp;//釋放原隊首節點queSize--;if (front == nullptr) { //如果隊列為空，重置rearrear = nullptr;}return val;}//訪問隊列首元素int peek() {if (isEmpty()){throw out_of_range("隊列為空");}return front->val;}//轉換為vector返回vector<int> toVector() {vector<int> res(size());ListNode* node = front;for (int i = 0; i < res.size(); i++){res[i] = node->val;node = node->next;}return res;}
};int main() {LinkedListQueue q;q.push(10);q.push(20);q.push(30);cout << "隊列中元素 : ";vector<int> v = q.toVector();for (int num : v){cout << num << " ";}cout << endl;cout << "隊首元素: " << q.peek() << endl;while (!q.isEmpty()) {cout << "出隊元素: " << q.pop() << endl;}cout << "隊列長度: " << q.size() << endl;system("pause");return 0;}