3-栈和队列

栈和队列

栈和队列都是只能在特定位置插入、删除元素的线性数据结构：

在 ACM 模式中，如果题目已经给出操作次数上限，可以直接使用数组模拟栈和队列。这样既能避免动态内存分配，也能清楚地控制每次操作的时间复杂度。

栈

栈可以理解成一摞盘子：新盘子只能放到最上面，取盘子时也只能先取最上面的盘子。因此，最后放入的元素会最先被取出。

数组模拟栈

使用数组 stk 保存栈中的元素，并让 tt 表示栈顶元素的下标：

// tt 表示栈顶下标
int stk[N], tt = 0;

这里使用 1-based 下标：

• stk[1] 是栈底元素；
• stk[tt] 是栈顶元素；
• tt == 0 表示栈为空；
• tt > 0 表示栈不为空。

栈中有效元素始终位于 stk[1] 到 stk[tt] 之间。

基本操作

入栈

先将栈顶下标加一，再把新元素写入栈顶：

stk[++tt] = x;

出栈

将栈顶下标减一，原栈顶元素就不再属于有效区间：

tt--;

数组中的旧值不需要清除，因为之后入栈时会直接覆盖它。

读取栈顶

int top = stk[tt];

读取前必须保证栈不为空，否则 stk[tt] 不是有效的栈顶元素。

判断栈是否为空

if (tt > 0) {
  // 栈不为空
}

也可以直接使用 tt == 0 判断栈为空。

正确性说明

初始化时 tt = 0，有效区间为空，因此栈为空。入栈时，新元素被写入原栈顶之后并成为新的栈顶；出栈时，原栈顶从有效区间中移除，前一个元素成为新的栈顶。由于插入和删除都只发生在栈顶，所以元素的弹出顺序一定与插入顺序相反，满足后进先出的性质。

AcWing 828：模拟栈

题意

维护一个初始为空的栈，支持以下操作：

• push x：将 x 插入栈顶；
• pop：弹出栈顶元素；
• empty：判断栈是否为空；
• query：输出栈顶元素。

题目保证执行 pop 和 query 时栈不为空。

完整代码

#include <iostream>
#include <string>
 
using namespace std;
 
const int N = 100010;
 
int stk[N], tt;
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
 
  int m;
  cin >> m;
 
  while (m--) {
    string op;
    cin >> op;
 
    if (op == "push") {
      int x;
      cin >> x;
      stk[++tt] = x;
    } else if (op == "pop") {
      tt--;
    } else if (op == "empty") {
      cout << (tt == 0 ? "YES" : "NO") << '\n';
    } else {
      cout << stk[tt] << '\n';
    }
  }
 
  return 0;
}

复杂度分析

• 入栈、出栈、读取栈顶和判空都只访问常数个变量，时间复杂度均为 $O(1)$；
• 执行 $m$ 次操作的总时间复杂度为 $O(m)$；
• 数组最多保存 $m$ 个元素，空间复杂度为 $O(m)$。

队列

队列可以理解成排队：新来的元素只能排在队尾，离开的元素只能从队头取出。因此，最先进入队列的元素会最先离开。

数组模拟普通队列

使用数组 q 保存队列中的元素，hh 表示队头下标，tt 表示队尾下标：

// hh 表示队头，tt 表示队尾
int q[N], hh = 0, tt = -1;

初始化后 hh = 0、tt = -1，此时 hh > tt，表示队列为空。队列不为空时，有效元素位于 q[hh] 到 q[tt] 之间。

基本操作

入队

先将队尾下标加一，再把新元素写入队尾：

q[++tt] = x;

出队

将队头下标加一，原队头元素就不再属于有效区间：

hh++;

读取队头

int front = q[hh];

读取前必须保证队列不为空。

判断队列是否为空

if (hh <= tt) {
  // 队列不为空
}

相应地，hh > tt 表示队列为空。

为什么普通队列不回收前面的空间

元素出队后只移动 hh，不会把剩余元素整体向前搬移。这样每次出队仍然是 $O(1)$，但数组前部的空间不会再次使用。

对于 AcWing 829 这类总入队次数不超过 $m$ 的题目，只要数组容量至少为 $m$，就不会越界。如果题目要求长期复用固定大小的存储空间，则应改用循环队列。

正确性说明

初始化时 hh > tt，有效区间为空。入队时，新元素被添加到有效区间末尾，不会改变已有元素的先后顺序；出队时，只从有效区间开头移除元素。因此，任何时刻队头都是尚未出队的最早入队元素，满足先进先出的性质。

AcWing 829：模拟队列

题意

维护一个初始为空的队列，支持以下操作：

• push x：将 x 插入队尾；
• pop：弹出队头元素；
• empty：判断队列是否为空；
• query：输出队头元素。

题目保证执行 pop 和 query 时队列不为空。

完整代码

#include <iostream>
#include <string>
 
using namespace std;
 
const int N = 100010;
 
int q[N], hh, tt = -1;
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
 
  int m;
  cin >> m;
 
  while (m--) {
    string op;
    cin >> op;
 
    if (op == "push") {
      int x;
      cin >> x;
      q[++tt] = x;
    } else if (op == "pop") {
      hh++;
    } else if (op == "empty") {
      cout << (hh > tt ? "YES" : "NO") << '\n';
    } else {
      cout << q[hh] << '\n';
    }
  }
 
  return 0;
}

复杂度分析

• 入队、出队、读取队头和判空都只访问常数个变量，时间复杂度均为 $O(1)$；
• 执行 $m$ 次操作的总时间复杂度为 $O(m)$；
• 数组最多保存 $m$ 个入队元素，空间复杂度为 $O(m)$。

常见错误

• 栈顶下标初始化错误：当前模板使用 1-based 下标，所以 tt 应初始化为 0，第一次入栈使用 stk[++tt]。
• 队尾下标初始化错误：hh = 0 时应让 tt = -1，这样空队列满足 hh > tt。
• 自增顺序错误：入栈和入队都要先移动下标再写入，即 stk[++tt] 和 q[++tt]。
• 判空条件写反：栈非空是 tt > 0；队列非空是 hh <= tt。
• 空结构上执行操作：读取或删除元素前必须确保结构不为空；本题虽然保证操作合法，编写通用模板时仍要检查。
• 队列出队时移动全部元素：只需执行 hh++，整体搬移会把单次操作变成 $O(n)$。
• 数组容量不足：普通队列不会复用已经出队的位置，数组容量应按照总入队次数确定。
• 混淆队头和队尾：普通队列从 q[hh] 读取和删除，从 q[tt] 一端插入。

参考资料

• AcWing：数据结构（一）—— 单链表、双链表、栈、队列，作者：yxc（非商业转载请注明出处）。