第 3.1 章 栈和队列

Stack and Queue

受限线性表

栈和队列都是线性表，但它们限制了插入和删除的位置。

结构	插入位置	删除位置	规则
栈	栈顶	栈顶	后进先出
队列	队尾	队头	先进先出

限制操作位置会带来更清晰的语义，也会让很多算法自然表达。

函数调用 局部变量、返回地址和参数组成调用栈

Linux 缓冲区和任务等待队列维持处理顺序

Kafka 消息按追加顺序进入分区日志

JavaScript 事件循环把待处理任务排入队列

学习目标

• 掌握栈 ADT、数组栈和链式栈
• 理解双栈共享数组的空间优化
• 使用栈完成括号匹配、后缀表达式求值、中缀转后缀
• 掌握队列 ADT、循环队列和链式队列
• 使用队列生成杨辉三角并完成网格最短路径标号
• 能够分析栈与队列应用的时间复杂度和空间复杂度

路线图

运行时性能：为什么端点操作重要

栈和队列的高效来自“只在端点操作”。

• 数组栈的 push/pop 只移动 top，内存连续，cache locality 好
• 链式栈避免扩容搬迁，但每个节点有指针和动态分配开销
• 循环队列用数组复用空间，适合操作系统缓冲区和生产者消费者模型
• 链式队列删除队头、插入队尾稳定为 \(O(1)\)，但节点分散会增加 cache miss

操作系统中的等待队列、I/O 缓冲区和事件循环都依赖这种“受限操作换取可预测成本”的思想。

栈模型

栈 ADT

操作	含义
create()	创建空栈
empty()	判断栈是否为空
full()	判断栈是否已满
push(x)	把 x 压入栈顶
top()	读取栈顶元素
pop()	删除栈顶元素
topAndPop()	读取并删除栈顶元素

栈的核心约束是：只能从栈顶观察和修改。

链式栈

链式栈把单链表头部作为栈顶。

空栈条件是 topOfStack == nullptr。

链式栈代码

template <class T>
class LinkedStack {
 public:
  bool empty() const { return top_ == nullptr; }

  void push(const T& value) {
    top_ = new Node<T>(value, top_);
  }

  const T& top() const {
    if (empty()) throw std::underflow_error("empty stack");
    return top_->data;
  }

  void pop() {
    if (empty()) throw std::underflow_error("empty stack");
    Node<T>* old = top_;
    top_ = top_->next;
    delete old;
  }

 private:
  Node<T>* top_ = nullptr;
};

数组栈

数组栈使用 topOfStack 指向当前栈顶下标。

空栈条件：

\[ topOfStack=-1 \]

满栈条件：

\[ topOfStack=capacity-1 \]

数组栈代码

template <class T>
class ArrayStack {
 public:
  explicit ArrayStack(int capacity) : data_(capacity), top_(-1) {}

  bool empty() const { return top_ == -1; }
  bool full() const { return top_ == static_cast<int>(data_.size()) - 1; }

  void push(const T& value) {
    if (full()) throw std::overflow_error("full stack");
    data_[++top_] = value;
  }

  T pop() {
    if (empty()) throw std::underflow_error("empty stack");
    return data_[top_--];
  }

 private:
  std::vector<T> data_;
  int top_;
};

两个栈共享一个数组

栈应用一：括号匹配

括号匹配代码

void printMatchedPairs(const std::string& expr) {
  std::stack<int> st;
  for (int i = 0; i < static_cast<int>(expr.size()); ++i) {
    if (expr[i] == '(') {
      st.push(i + 1);
    } else if (expr[i] == ')') {
      if (st.empty()) {
        std::cout << "No match for right parenthesis at " << i + 1 << "\n";
      } else {
        int left = st.top();
        st.pop();
        std::cout << left << " " << i + 1 << "\n";
      }
    }
  }
  while (!st.empty()) {
    std::cout << "No match for left parenthesis at " << st.top() << "\n";
    st.pop();
  }
}

每个字符最多入栈或出栈一次，时间复杂度 \(O(n)\)。

表达式处理的两步

编译器和计算器常把中缀表达式转成后缀表达式，再求值。

中缀表达式	后缀表达式
A*B-C*D#	AB*CD*-#
(A+B)*((C-D)*E+F)#	AB+CD-E*F+*#

后缀表达式没有括号，操作数次序不变，运算符出现的次序就是执行次序。

后缀表达式求值

后缀表达式求值代码

double evalPostfix(const std::vector<Token>& tokens) {
  std::stack<double> st;
  for (const Token& token : tokens) {
    if (token.isNumber()) {
      st.push(token.value());
    } else {
      double right = st.top(); st.pop();
      double left = st.top(); st.pop();
      st.push(apply(token.op(), left, right));
    }
  }
  return st.top();
}

注意二元运算的弹栈顺序：先弹出的是右操作数。

中缀转后缀

中缀转后缀规则

当前字符	动作
操作数	直接输出
(	入运算符栈
)	弹出并输出，直到遇到 (
运算符	弹出优先级不低于当前运算符的栈顶，再把当前运算符入栈
结束符 #	弹出并输出剩余运算符

该算法同样是线性时间。

队列模型

队列是只允许在一端插入、另一端删除的线性表。

端点	操作
rear	新元素入队
front	旧元素出队

队列也称先进先出结构。

队列 ADT

操作	含义
create()	创建空队列
empty()	判断是否为空
full()	判断是否已满
front()	读取队头
back()	读取队尾
enqueue(x)	在队尾加入 x
dequeue()	删除并返回队头

普通数组队列的问题

若每次出队都把元素整体左移，出队是 \(O(n)\)。

若只移动 front，前面会出现空洞。

循环数组的目标是复用这些空洞。

循环队列

循环队列代码

template <class T>
class CircularQueue {
 public:
  explicit CircularQueue(int capacity)
      : data_(capacity), front_(0), back_(-1), size_(0) {}

  bool empty() const { return size_ == 0; }
  bool full() const { return size_ == static_cast<int>(data_.size()); }

  void enqueue(const T& value) {
    if (full()) throw std::overflow_error("full queue");
    back_ = increment(back_);
    data_[back_] = value;
    ++size_;
  }

  T dequeue() {
    if (empty()) throw std::underflow_error("empty queue");
    T value = data_[front_];
    front_ = increment(front_);
    --size_;
    return value;
  }

 private:
  int increment(int x) const { return (x + 1) % data_.size(); }
  std::vector<T> data_;
  int front_;
  int back_;
  int size_;
};

只保存 rear 和 length

若数组长度为 \(m\)，保存队尾 rear 和队列长度 length，队头位置为：

\[ front=(rear-length+1+m)\bmod m \]

队空条件：

\[ length=0 \]

队满条件：

\[ length=m \]

链式队列

队头删除，队尾插入。

链式队列代码

template <class T>
class LinkedQueue {
 public:
  bool empty() const { return front_ == nullptr; }

  void enqueue(const T& value) {
    Node<T>* node = new Node<T>(value);
    if (empty()) {
      front_ = back_ = node;
    } else {
      back_->next = node;
      back_ = node;
    }
  }

  T dequeue() {
    if (empty()) throw std::underflow_error("empty queue");
    Node<T>* old = front_;
    T value = old->data;
    front_ = front_->next;
    if (front_ == nullptr) back_ = nullptr;
    delete old;
    return value;
  }

 private:
  Node<T>* front_ = nullptr;
  Node<T>* back_ = nullptr;
};

队列应用一：杨辉三角

第 \(i\) 行的系数来自上一行相邻两项之和：

\[ \binom{i}{j}=\binom{i-1}{j-1}+\binom{i-1}{j} \]

可以使用队列保存上一行，从左到右生成下一行。

队列应用二：网格布线

网格布线算法

bool findPath(Position start, Position finish) {
  std::queue<Position> q;
  grid[start.row][start.col] = 2;
  q.push(start);
  while (!q.empty()) {
    Position here = q.front();
    q.pop();
    for (Position next : neighbors(here)) {
      if (grid[next.row][next.col] == 0) {
        grid[next.row][next.col] = grid[here.row][here.col] + 1;
        if (next == finish) return true;
        q.push(next);
      }
    }
  }
  return false;
}

队列保证按距离递增顺序扩展，因此第一次到达终点就是最短路径。

网格布线复杂度

设网格规模为 \(m\times m\)。

编号阶段每个格子最多入队一次：

\[ O(m^2) \]

路径重构只沿最短路径回退：

\[ O(PathLen) \]

栈与队列对比

维度	栈	队列
删除规则	最近加入者先删除	最早加入者先删除
典型算法	DFS、递归、表达式处理	BFS、缓冲区、调度
关键指针	top	front 与 rear
数组实现	单端增长	循环数组
链式实现	表头作为栈顶	头删尾插

练习 1：打印缓冲区

主机把打印数据依次写入缓冲区，打印机依次取出。

答案：队列。

原因：先写入的数据必须先被打印，逻辑结构应满足先进先出。

练习 2：栈容量

元素 a,b,c,d,e,f,g 依次进栈，每个元素出栈后立即进入队列，出队顺序为：

b,d,c,f,e,a,g

答案：容量至少为 3。

一种可行过程为：

push a, push b, pop b, push c, push d, pop d, pop c, push e, push f, pop f, pop e, pop a, push g, pop g

过程中最大栈深为 3。

练习 3：循环队列

数组 Q[m] 保存循环队列，rear 指示队尾，length 表示元素个数。

队头位置：

\[ front=(rear-length+1+m)\bmod m \]

队空：length == 0。

队满：length == m。

练习 4：循环左移

把数组

\[ X_0,X_1,\ldots,X_{n-1} \]

循环左移 \(p\) 位，得到：

\[ X_p,\ldots,X_{n-1},X_0,\ldots,X_{p-1} \]

答案：三次逆置。

循环左移代码

template <class T>
void reverseRange(std::vector<T>& a, int left, int right) {
  while (left < right) {
    std::swap(a[left++], a[right--]);
  }
}

template <class T>
void rotateLeft(std::vector<T>& a, int p) {
  int n = static_cast<int>(a.size());
  p %= n;
  reverseRange(a, 0, p - 1);
  reverseRange(a, p, n - 1);
  reverseRange(a, 0, n - 1);
}

时间复杂度 \(O(n)\)，额外空间 \(O(1)\)。