基础数据结构

栈与队列

「受限」才是重点

栈和队列不提供数组的随机访问，只能从固定的一端进出：

  • 栈：后进先出（LIFO），只能操作栈顶
  • 队列：先进先出（FIFO），一端进另一端出

⭐ 这些限制不是缺陷，是性质。正因为只能这么用，才能保证某些不变量 —— 单调栈和单调队列全靠这一点： 「只能从固定一端进出」恰好保证了「扔掉的元素不会再回来」。

用数组实现栈天然合适（push/pop 都在末尾，均摊 O(1)）。 用数组实现队列要小心 shift() 的 O(n)，办法见 环形数组。

括号匹配：栈最典型的用法

栈解决的一大类问题可以概括成一句话： 「最近一个还没被处理掉的东西」是什么。

括号匹配是最纯粹的形态 —— 遇到右括号时，要配的一定是最近那个还没配上的左括号：

function isValid(s) {
  const pairs = { ')': '(', ']': '[', '}': '{' };
  const st = [];
  for (const c of s) {
    if (c in pairs) {
      if (st.pop() !== pairs[c]) return false;   // 栈空时 pop() 得到 undefined，同样不等
    } else {
      st.push(c);
    }
  }
  return st.length === 0;                        // 🚨 这一行不能省
}

⭐ st.pop() 在空栈上返回 undefined，和任何括号都不相等 —— 于是「右括号来了但没有左括号」这种情况不用单独写分支。

🚨 最后那句 return st.length === 0 漏掉的话，"([{" 会被判成合法。

整体出错率取决于你怎么生成随机串（各 20 万个）：

长度 0~9、六种括号        13.2%
长度 1~20、六种括号        6.8%
长度 0~9、只用 ()         26.5%
长度恒为 8、六种括号        2.6%

⚠️ 但真正的坑不用统计也能断定：在本来就合法的串上，它一次都不会错。

⭐ 这不是「概率很小」，是逻辑上不可能 —— 漏掉最后那句只会让某些 false 被误判成 true，绝不可能把 true 判成 false。 上面四种生成方式下合法串的错误数全是 0，而这本来就是必然的。

📌 所以只拿「应该返回 true」的例子自测，这个 bug 一次都不会现形。 必须专门测左括号有剩余的串（"([{" 就够）。

最小栈：用另一个栈记住历史

要求 push/pop/top/getMin 全是 O(1)。难点在 getMin —— 弹出一个元素后，最小值可能要退回到之前的某个值，而那个值已经无处可查。

办法是再开一个栈，与主栈同步升降，第 i 格存「主栈前 i 个元素的最小值」：

class MinStack {
  constructor() { this.st = []; this.min = []; }
  push(x) {
    this.st.push(x);
    // ⭐ 每次都压，哪怕不是更小的 —— 压的是「此刻的最小值」
    this.min.push(this.min.length === 0 ? x : Math.min(x, this.min[this.min.length - 1]));
  }
  pop() { this.st.pop(); this.min.pop(); }       // 两个栈同进同出
  top() { return this.st[this.st.length - 1]; }
  getMin() { return this.min[this.min.length - 1]; }
}

🚨 常见的「优化」是只在 x 更小时才压辅助栈 —— 看起来省空间，实际是错的。

对拍 10 万轮随机操作序列（每轮 10 次 push/pop）。 ⚠️ 出错率完全由「值域」决定 —— 值域越窄重复值越多，这个 bug 越容易现形：

值域        同步压栈版        只在更小时才压
0~2         0 / 100000       52795 / 100000   52.8%
0~4         0 / 100000       35188 / 100000   35.2%
0~9         0 / 100000       19194 / 100000   19.2%
0~49        0 / 100000        4074 / 100000    4.1%
0~999       0 / 100000         212 / 100000    0.2%
元素两两不同  0 / 100000           0 / 100000    0.0%

⭐ 从 52.8% 一路掉到 0.2%，同一个 bug 差了两百多倍。 所以「我随机测了十万轮没问题」这句话，要看你的值域有多宽 —— 值域一宽就等于在测「元素两两不同」，而那正是它的盲区。

最小复现只要三步：push(2) → push(2) → pop()，之后 getMin() 返回 undefined。 两个 2 只压了一次，pop 却把它弹掉了。

📌 判据：凡是靠「值相等」做判断的代码（这里是 x < min 那个比较）， 测试数据必须故意造重复值。

用两个栈实现队列

经典题，也是「均摊分析」的好例子：

class MyQueue {
  constructor() { this.inS = []; this.outS = []; }

  push(x) { this.inS.push(x); }

  pop() {
    this.peek();                    // 保证 outS 非空
    return this.outS.pop();
  }

  peek() {
    // 🚨 只有 outS 空了才倒腾，不能每次都倒
    if (this.outS.length === 0) {
      while (this.inS.length > 0) this.outS.push(this.inS.pop());
    }
    return this.outS[this.outS.length - 1];
  }

  get empty() { return this.inS.length === 0 && this.outS.length === 0; }
}

⭐ 每个元素最多被搬运一次（从 inS 到 outS），此后再也不回去。 所以 n 次操作的总搬运量是 O(n)，均摊到每次是 O(1) —— 和动态数组扩容是同一种均摊。

数一下就知道这不是「大约」：10 万次 push + 10 万次 pop， 总搬运恰好 100000 次，每个元素不多不少一次。

🚨 if (this.outS.length === 0) 那个判断不能去掉，而且去掉之后不是变慢，是直接算错。

outS 里已经躺着一批倒序好的元素时，再把 inS 倒上去， 新来的会压在旧的上面 —— 而它们本该排在后面。顺序就此错乱：

push 1,2  → pop → 1        ✅
push 3,4  → pop pop pop
  有 if：  2, 3, 4          ✅
  无 if：  3, 4, 2          ❌

⚠️ 我一开始想当然地把它归成「结果对、只是慢」那一类（这个板块里确实有好几个那样的坑）， 实测才发现它是正确性 bug，而且是个很吵的 bug —— 20000 轮随机操作序列里 77.7% 会出错。

📌 判据：倒腾的前提是「目标栈是空的」 —— 只要 outS 还有货，就绝不能往上倒。

用队列实现栈

反过来的那道题，反而更简单也更笨：

class MyStack {
  constructor() { this.q = []; }
  push(x) {
    this.q.push(x);
    // 把前面的元素全部搬到后面去，让新元素跑到队头
    for (let i = 0; i < this.q.length - 1; i++) this.q.push(this.q.shift());
  }
  pop() { return this.q.shift(); }
  top() { return this.q[0]; }
}

⚠️ 这个 push 是 O(n)，没有均摊 O(1) 的写法。 n 次 push 的总轮转次数恰好是 n(n-1)/2：

n = 100    4950 次      n(n-1)/2 = 4950
n = 200   19900 次      n(n-1)/2 = 19900
n = 400   79800 次      n(n-1)/2 = 79800

⭐ 和上面那个「总搬运恰好 n 次」对比着看：两个栈做队列是线性总量， 一个队列做栈是平方总量。用两个栈做队列能均摊到 O(1)，反过来做不到 —— 因为栈能「暂存倒序」，队列不能。

📌 面试里这道题主要考「你能不能想到把元素轮转一圈」，不必纠结性能。

往后看

上面这些是栈和队列本身的用法，面试里占的比重其实不大。 真正高频的是它们的两个变形 —— 单调栈与单调队列， 下一篇整篇在讲。

练习

勾选记录做过哪些，0 / 6 道。进度只存在这台设备的浏览器里；同一道题在别篇勾过，这里也会显示已做。

⚖️ 这里只给题号、官方标题和链接，不复述题面 —— 平台的题面文字有版权。 「这题考什么」写的是它对应本篇的哪个点，那部分是本站自己的内容。