棧和隊列的基本

棧（Stack）是一種后進先出（LIFO, Last In First Out）的數據結構。元素的插入和刪除操作只能在棧頂進行。常見的操作包括壓棧（push）和彈棧（pop）。

隊列（Queue）是一種先進先出（FIFO, First In First Out）的數據結構。元素的插入在隊尾進行，刪除在隊頭進行。常見的操作包括入隊（enqueue）和出隊（dequeue）。

操作方式的差異

棧的插入和刪除操作均在棧頂完成。壓棧操作將元素添加到棧頂，彈棧操作移除棧頂元素。棧不支持在中間或底部直接操作。

隊列的插入操作在隊尾完成，刪除操作在隊頭完成。入隊操作將元素添加到隊尾，出隊操作移除隊頭元素。隊列不支持在中間直接操作。

應用場景的不同

棧常用于需要回溯或撤銷的場景，如函數調用棧、括號匹配、表達式求值。遞歸算法的實現也依賴于棧。

隊列常用于需要按順序處理的場景，如任務調度、消息隊列、廣度優先搜索（BFS）。打印任務的管理也是隊列的典型應用。

實現方式的差異

棧可以通過數組或鏈表實現。數組實現的棧需要預先分配固定大小，鏈表實現的棧可以動態擴展。棧的插入和刪除操作時間復雜度均為 O(1)。

隊列也可以通過數組或鏈表實現。數組實現的隊列可能涉及循環隊列以避免空間浪費，鏈表實現的隊列可以動態擴展。隊列的插入和刪除操作時間復雜度均為 O(1)。

性能特點的對比

棧的插入和刪除操作僅涉及棧頂指針的移動，性能高效且簡單。棧的空間復雜度取決于存儲的元素數量。

隊列的插入和刪除操作涉及隊頭和隊尾指針的移動，性能同樣高效。循環隊列的實現可以優化數組空間利用率。

基于C++棧和隊列的實例

以下是基于C++棧和隊列的實例，涵蓋基礎操作、算法應用和實際場景。所有代碼均遵循標準C++語法，可直接編譯運行。

棧（Stack）實例

基礎操作

#include <stack>
#include <iostream>
using namespace std;// 1. 棧的聲明與壓棧
stack<int> s;
s.push(10);
s.push(20);// 2. 彈棧并獲取棧頂
int top = s.top();
s.pop();// 3. 檢查棧是否為空
bool isEmpty = s.empty();// 4. 獲取棧大小
size_t size = s.size();

算法應用

// 5. 括號匹配檢查
bool isValid(string str) {stack<char> st;for (char c : str) {if (c == '(' || c == '{' || c == '[') st.push(c);else if (st.empty() || abs(c - st.top()) > 2) return false;else st.pop();}return st.empty();
}// 6. 逆波蘭表達式求值
int evalRPN(vector<string>& tokens) {stack<int> s;for (string t : tokens) {if (isdigit(t.back())) s.push(stoi(t));else {int b = s.top(); s.pop();int a = s.top(); s.pop();if (t == "+") s.push(a + b);else if (t == "-") s.push(a - b);else if (t == "*") s.push(a * b);else s.push(a / b);}}return s.top();
}

進階應用

// 7. 使用棧實現隊列
class MyQueue {stack<int> in, out;
public:void push(int x) { in.push(x); }int pop() {if (out.empty()) while (!in.empty()) out.push(in.top()), in.pop();int x = out.top(); out.pop();return x;}
};// 8. 最小棧設計
class MinStack {stack<int> s, min_s;
public:void push(int x) {s.push(x);if (min_s.empty() || x <= min_s.top()) min_s.push(x);}void pop() {if (s.top() == min_s.top()) min_s.pop();s.pop();}int getMin() { return min_s.top(); }
};

隊列（Queue）實例

基礎操作

#include <queue>
#include <iostream>
using namespace std;// 1. 隊列聲明與入隊
queue<int> q;
q.push(10);
q.push(20);// 2. 出隊并獲取隊首
int front = q.front();
q.pop();// 3. 檢查隊列是否為空
bool isEmpty = q.empty();// 4. 獲取隊列大小
size_t size = q.size();

算法應用

// 5. 使用隊列實現棧
class MyStack {queue<int> q;
public:void push(int x) {q.push(x);for (int i = 1; i < q.size(); ++i) q.push(q.front()), q.pop();}int pop() { int x = q.front(); q.pop(); return x; }
};// 6. 二叉樹的層次遍歷
void levelOrder(TreeNode* root) {queue<TreeNode*> q;if (root) q.push(root);while (!q.empty()) {TreeNode* node = q.front(); q.pop();cout << node->val << " ";if (node->left) q.push(node->left);if (node->right) q.push(node->right);}
}

實際場景

// 7. 循環隊列實現
class CircularQueue {int *arr, front, rear, size;
public:CircularQueue(int k) : arr(new int[k]), front(-1), rear(-1), size(k) {}bool enQueue(int value) {if (isFull()) return false;if (isEmpty()) front = 0;rear = (rear + 1) % size;arr[rear] = value;return true;}
};// 8. 任務調度器
int leastInterval(vector<char>& tasks, int n) {queue<pair<int, int>> q;priority_queue<int> pq;unordered_map<char, int> cnt;for (char c : tasks) cnt[c]++;for (auto p : cnt) pq.push(p.second);int time = 0;while (!pq.empty() || !q.empty()) {time++;if (!pq.empty()) {int t = pq.top() - 1;pq.pop();if (t > 0) q.push({t, time + n});}if (!q.empty() && q.front().second == time) {pq.push(q.front().first);q.pop();}}return time;
}

完整項目實例

以下為可擴展的完整項目示例（需包含頭文件）：

瀏覽器歷史記錄（棧應用）

class BrowserHistory {stack<string> backStack, forwardStack;string current;
public:BrowserHistory(string homepage) : current(homepage) {}void visit(string url) {backStack.push(current);current = url;forwardStack = stack<string>();}string back(int s