栈与队列：数据结构核心解密

栈和队列的基本

栈（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 #include using namespace std;// 1. 栈的声明与压栈stack 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 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& tokens) { stack 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 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 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 #include using namespace std;// 1. 队列声明与入队queue 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 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 q; if (root) q.push(root); while (!q.empty()) { TreeNode* node = q.front(); q.pop(); cout <val <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& tasks, int n) { queue<pair> q; priority_queue pq; unordered_map 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 backStack, forwardStack; string current;public: BrowserHistory(string homepage) : current(homepage) {} void visit(string url) { backStack.push(current); current = url; forwardStack = stack(); } string back(int s