C++栈与队列：数据结构的“单行道”与“流水线”

---

开篇小故事：火车站的两条轨道

想象一个火车站有两条特殊轨道：

• 轨道A（栈）：火车只能从同一端进出，最后进入的车厢必须先离开。
• 轨道B（队列）：火车从一端进入，从另一端离开，先进入的车厢先离开。

这两条轨道代表了两种基础数据结构：栈（Stack） 和 队列（Queue）。它们看似简单，却是构建复杂算法的基石。今天，我们将探索它们在C++中的实现、差异与应用场景。

---

一、栈与队列的核心特性对比

特性	栈（Stack）	队列（Queue）
数据规则	后进先出（LIFO）	先进先出（FIFO）
插入位置	栈顶（push）	队尾（push）
删除位置	栈顶（pop）	队首（pop）
访问权限	仅能访问栈顶元素（top）	可访问队首（front）和队尾（back）
典型应用	函数调用栈、括号匹配、撤销操作	任务调度、BFS广度优先搜索、消息队列

---

二、C++中的栈与队列实现

1. 栈（std::stack）

• 底层容器：默认基于deque，也可使用vector或list。
• 核心操作：

  #include <stack>
  stack<int> s;
  s.push(10);       // 入栈
  s.pop();          // 出栈（不返回元素）
  int top = s.top();// 访问栈顶
  bool isEmpty = s.empty();
  

2. 队列（std::queue）

• 底层容器：默认基于deque，也可使用list（不可用vector，因不支持pop_front）。
• 核心操作：

  #include <queue>
  queue<int> q;
  q.push(20);       // 入队
  q.pop();          // 出队（不返回元素）
  int front = q.front(); // 访问队首
  int back = q.back();   // 访问队尾
  

---

三、栈与队列的经典应用场景

1. 栈的应用：括号匹配

bool isBalanced(string expr) {stack<char> s;for (char c : expr) {if (c == '(' || c == '[') s.push(c);else if (c == ')') {if (s.empty() || s.top() != '(') return false;s.pop();} else if (c == ']') {if (s.empty() || s.top() != '[') return false;s.pop();}}return s.empty();
}
// 示例：isBalanced("([()])") → true

2. 队列的应用：广度优先搜索（BFS）

void bfs(Node* root) {queue<Node*> q;q.push(root);while (!q.empty()) {Node* current = q.front();q.pop();// 处理当前节点for (auto child : current->children) {q.push(child);}}
}

3. 栈与队列的联合应用：用队列实现栈

class MyStack {queue<int> q;
public:void push(int x) {q.push(x);// 将前n-1个元素移到队尾for (int i = 0; i < q.size() - 1; i++) {q.push(q.front());q.pop();}}int pop() {int val = q.front();q.pop();return val;}int top() { return q.front(); }bool empty() { return q.empty(); }
};

---

四、栈与队列的底层实现原理

1. 栈的底层实现

• 数组实现（顺序栈）：

  class ArrayStack {int* data;int capacity;int topIndex;
  public:void push(int val) {if (topIndex == capacity - 1) resize();data[++topIndex] = val;}// ...其他操作
  };
  

• 链表实现（链式栈）：

  class ListNode {int val;ListNode* next;
  };
  class LinkedStack {ListNode* topNode;
  public:void push(int val) {ListNode* newNode = new ListNode(val);newNode->next = topNode;topNode = newNode;}// ...其他操作
  };
  

2. 队列的底层实现

• 循环数组实现：解决数组实现的“假溢出”问题。

  class CircularQueue {int* data;int front, rear, capacity;
  public:void enqueue(int val) {if ((rear + 1) % capacity == front) resize();data[rear] = val;rear = (rear + 1) % capacity;}// ...其他操作
  };
  

• 链表实现：

  class LinkedQueue {ListNode* front;ListNode* rear;
  public:void enqueue(int val) {ListNode* newNode = new ListNode(val);if (rear) rear->next = newNode;else front = newNode;rear = newNode;}// ...其他操作
  };
  

---

五、如何选择栈与队列？

• 选择栈的场景：

  • 需要“撤销”操作（如编辑器撤销功能）。
  • 处理嵌套结构（如递归调用、括号匹配）。
  • 深度优先搜索（DFS）。

• 选择队列的场景：

  • 需要公平性（如打印任务排队）。
  • 处理层级结构（如BFS遍历树或图）。
  • 缓冲数据流（如消息队列）。

---

六、常见错误与规避方法

1. 栈的常见错误

• 空栈操作：访问或弹出空栈的栈顶。

  stack<int> s;
  // s.pop();    // 崩溃！
  // s.top();    // 崩溃！
  

  规避：操作前检查空栈状态。

2. 队列的常见错误

• 使用vector作为底层容器：

  queue<int, vector<int>> q; // 错误！vector不支持pop_front()
  

  规避：使用默认的deque或list。

---

七、性能对比与优化

操作	栈（时间复杂度）	队列（时间复杂度）
插入元素	O(1)	O(1)
删除元素	O(1)	O(1)
访问顶部/首部	O(1)	O(1)
内存占用	连续内存	分散内存（链表）

优化技巧：

• 栈：预分配内存（如vector的reserve）。
• 队列：使用循环数组减少内存碎片。

---

总结：栈与队列——程序世界的“交通规则”

栈与队列如同程序中的两条单行道：

• 栈是“后进先出”的电梯，直达顶层但不容回头。
• 队列是“先进先出”的传送带，公平有序地处理任务。

理解它们的特性与差异，能让你在解决实际问题时，像交通指挥官一样精准调度数据流向！

（完）

---

希望这篇博客能帮助你深入理解栈与队列的设计哲学与实战应用！如果需要调整内容或补充示例，请随时告诉我~ 😊