栈与队列怎么玩（下）|算法篇

结束了针对栈结构的定点轰炸，我们现在开始要缓缓过渡到队列的世界了。

关于队列，在算法面试中大家需要掌握以下重点：

栈向队列的转化
双端队列
优先队列

以上考点中，1 属于基础难度， 2 对一部分同学来说已经有点吃力，3 的区分度最高——优先队列属于高级数据结构，其本质是二叉堆结构，考虑到相关题目具有较强的综合性，我们把它放在小册二叉树和堆相关的专题来展开。在本节，我们集中火力向前两个命题点开炮。

# 为什么一道题可以成为高频面试题

30 秒速记

高频题的价值在于同时考数据结构约束、状态不变量、复杂度分析和边界处理，而不是题面出现次数
“用栈实现队列”要求只通过栈顶操作恢复 FIFO，核心是两个栈分担输入与输出顺序
回答时先给操作契约，再解释为何顺序正确，最后给均摊复杂度，避免只背代码

一道题能成为高频面试题，通常是因为它既考经典知识，又能用较短时间检验候选人的综合基本功。 “用栈实现队列”同时涉及栈和队列两种结构，知识点集中、实现量适中，也比较容易看出编码是否扎实。它的深度和复杂度不算高，但这对务实的前端算法面试未必是缺点，面试官通常更关注基础是否可靠，而不是刻意炫技。

如何用栈实现队列？这个问题在近几年的算法面试中热度非常高。

所谓“热度”从何而来？这里就引出了一个非常有趣的话题：（在前端算法面试中）什么样的题目是好题？

首先，不能剑走偏锋：好的面试题，它考察的大多是算法/数据结构中最经典、最关键的一部分内容，这样才能体现公平；其次，它的知识点要尽可能密集、题目本身要尽可能具备综合性，这样才能一箭双雕甚至一箭N雕，进而体现区分度、最大化面试过程的效率。

能够同时在这两个方面占尽优势的考题其实并不是很多，“用栈实现队列”这样的问题算是其中的佼佼者：一方面，它考察的确实是数据结构中的经典内容；另一方面，它又覆盖了两个大的知识点、足以检验出候选人编码基本功的扎实程度。唯一的 BUG 可能就是深度和复杂度不够，换句话说就是不够难。

这个特点，在普通算法面试中可能是 BUG，但在前端算法面试中，实在未必。大家要知道，你是前端，你的面试官也是前端，前端行业普遍的算法水平是啥样他心里还没个数吗… 实际上大多数前端算法面试题的风格都是非常务实的，需要你炫技的实属特殊情况。

面试官追问

追问 1候选人认为“用栈实现队列”太简单，要求换成一道冷门高难题才能拉开差距；作为前端面试官，你会接受这个判断吗？

参考回答

不会仅凭难度换题，因为冷门技巧可能放大知识偶然性，反而削弱公平性。“用栈实现队列”同时覆盖栈、队列和基本编码能力，知识点经典且密集；它的短板是深度有限，需要靠追问补充分辨能力。

追问 2一场前端技术面只剩 15 分钟，候选人还要完成编码和复杂度说明，你为什么可能保留“用栈实现队列”而不是考复杂动态规划？

参考回答

这类题能在有限时间内同时检查数据结构理解、顺序转换和代码完整性，适合压缩面试成本。复杂动态规划可能把时间消耗在建模上，无法稳定观察基本功；若岗位确实要求更强算法能力，则仍需增加更深的独立题目。

追问 3招聘的是偏业务交付的前端工程师，却有人主张所有候选人都必须现场解决高难算法题，你会如何调整题目约束？

参考回答

我会优先选择经典、务实且综合度较高的题，再按岗位要求逐步增加复杂度。前端算法面试通常不以炫技为主要目标，但这不等于取消区分度，可以通过复杂度、边界条件和替代方案追问继续分层；岗位职责更偏算法时应另设标准。

追问 4同一道“用栈实现队列”连续几轮都无法区分候选人，有人秒写模板，有人只会背代码，你会先排查题目还是评分方式？

参考回答

先排查评分维度和追问设计，而不是直接认定题目失效。应观察候选人能否解释两次逆序为何恢复 FIFO、何时转移元素以及如何保证操作正确；若所有考点仍集中在模板复现，题目深度不足，需要追加约束或更换后续题。

# 如何用栈实现一个队列？

30 秒速记

inStack 只负责入队，outStack 只负责出队。
只有 outStack 为空时才把 inStack 全部倒过去，不能每次出队都搬运。
每个元素最多被压入、转移、弹出各一次：单次最坏 O(n)，均摊 O(1)。
empty 同时检查两个栈，peek 与 pop 应共用转移函数。

用两个栈就能实现队列：stack1 负责接收入队元素，stack2 负责提供出队元素。 因为元素从一个栈转移到另一个栈会再逆序一次，所以 stack2 的栈顶正好对应最早入队的元素。只有 stack2 为空时，才把 stack1 中的元素全部转过去；否则继续从 stack2 取值，避免破坏已有顺序。pop 和 peek 都遵守这套转移规则，empty 则要确认两个栈同时为空。

回答参考：“两次 LIFO 会恢复 FIFO。我采用懒转移：输出栈非空时继续消费，只有它空了才批量反转输入栈。”

题目描述：使用栈实现队列的下列操作：

push(x) – 将一个元素放入队列的尾部。
pop() – 从队列首部移除元素。
peek() – 返回队列首部的元素。
empty() – 返回队列是否为空。

示例:

MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // 返回 1
queue.pop(); // 返回 1
queue.empty(); // 返回 false

说明:

你只能使用标准的栈操作 – 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
假设所有操作都是有效的（例如，一个空的队列不会调用 pop 或者 peek 操作）。

思路分析

做这道题大家首先要在心里清楚一个事情：栈和队列的区别在哪里？

仔细想想，栈，后进先出；队列，先进先出。也就是说两者的进出顺序其实是反过来的。用栈实现队列，说白了就是用栈实现先进先出的效果，再说直接点，就是想办法让栈底的元素首先被取出，也就是让出栈序列被逆序。

乍一看有点头大：栈结构决定了栈底元素只能被死死地压在最底下，如何使它首先被取出呢？

一个栈做不到的事情，我们用两个栈来做：

首先，准备两个栈：

现在问题是，怎么把第一个栈底下的那个 1 给撬出来。仔细想想，阻碍我们接触到 1 的是啥？是不是它头上的 3 和 2？那么如何让 3 和 2 给 1 让路呢？实际上咱们完全可以把这三个元素按顺序从 stack1 中出栈、然后入栈到 stack 2 里去：

此时 1 变得触手可及。不仅如此，下一次我们试图出队 2 的时候，可以继续直接对 stack2 执行出栈操作——因为转移 2 和 3 的时候已经做过一次逆序了，此时 stack2 的出栈序列刚好就对应队列的出队序列。
有同学会问，那如果 stack1 里入栈新元素怎么办？比如这样：

你会发现这个4按照顺序应该在 1、2、3 后出栈。当 4 需要被出栈时，stack2 一定已经空掉了。当 stack2 为空、而 stack1 不为空时，我们需要继续把 stack1 中的元素转移到 stack2 中去，然后再从 stack2 里取元素。也就是说，所有的出队操作都只能依赖 stack2 来完成——只要我们坚持这个原则，就可以确保 stack1 里的元素都能够按照正确的顺序（逆序）出栈。

我们按照这个思路来写代码：

编码实现

/**
 * 初始化构造函数
 */
const MyQueue = function () {
  // 初始化两个栈
  this.stack1 = [];
  this.stack2 = [];
};

/**
* Push element x to the back of queue.
* @param {number} x
* @return {void}
*/
MyQueue.prototype.push = function (x) {
  // 直接调度数组的 push 方法
  this.stack1.push(x);
};

/**
* Removes the element from in front of queue and returns that element.
* @return {number}
*/
MyQueue.prototype.pop = function () {
  // 假如 stack2 为空，需要将 stack1 的元素转移进来
  if (this.stack2.length <= 0) {
    // 当 stack1 不为空时，出栈
    while (this.stack1.length !== 0) {
      // 将 stack1 出栈的元素推入 stack2
      this.stack2.push(this.stack1.pop());
    }
  }
  // 为了达到逆序的目的，我们只从 stack2 里出栈元素
  return this.stack2.pop();
};

/**
* Get the front element.
* @return {number}
* 这个方法和 pop 唯一的区别就是没有将定位到的值出栈
*/
MyQueue.prototype.peek = function () {
  if (this.stack2.length <= 0) {
    // 当 stack1 不为空时，出栈
    while (this.stack1.length != 0) {
      // 将 stack1 出栈的元素推入 stack2
      this.stack2.push(this.stack1.pop());
    }
  }
  // 缓存 stack2 的长度
  const stack2Len = this.stack2.length;
  return stack2Len && this.stack2[stack2Len - 1];
};

/**
* Returns whether the queue is empty.
* @return {boolean}
*/
MyQueue.prototype.empty = function () {
  // 若 stack1 和 stack2 均为空，那么队列空
  return !this.stack1.length && !this.stack2.length;
};

@前端进阶之旅: 代码已经复制到剪贴板

栈与队列怎么玩（下）|算法篇

结束了针对栈结构的定点轰炸，我们现在开始要缓缓过渡到队列的世界了。

关于队列，在算法面试中大家需要掌握以下重点：

栈向队列的转化
双端队列
优先队列

以上考点中，1 属于基础难度， 2 对一部分同学来说已经有点吃力，3 的区分度最高——优先队列属于高级数据结构，其本质是二叉堆结构，考虑到相关题目具有较强的综合性，我们把它放在小册二叉树和堆相关的专题来展开。在本节，我们集中火力向前两个命题点开炮。

# 为什么一道题可以成为高频面试题

30 秒速记

高频题的价值在于同时考数据结构约束、状态不变量、复杂度分析和边界处理，而不是题面出现次数
“用栈实现队列”要求只通过栈顶操作恢复 FIFO，核心是两个栈分担输入与输出顺序
回答时先给操作契约，再解释为何顺序正确，最后给均摊复杂度，避免只背代码

如何用栈实现队列？这个问题在近几年的算法面试中热度非常高。

所谓“热度”从何而来？这里就引出了一个非常有趣的话题：（在前端算法面试中）什么样的题目是好题？

面试官追问

追问 1候选人认为“用栈实现队列”太简单，要求换成一道冷门高难题才能拉开差距；作为前端面试官，你会接受这个判断吗？

参考回答

追问 2一场前端技术面只剩 15 分钟，候选人还要完成编码和复杂度说明，你为什么可能保留“用栈实现队列”而不是考复杂动态规划？

参考回答

追问 3招聘的是偏业务交付的前端工程师，却有人主张所有候选人都必须现场解决高难算法题，你会如何调整题目约束？

参考回答

追问 4同一道“用栈实现队列”连续几轮都无法区分候选人，有人秒写模板，有人只会背代码，你会先排查题目还是评分方式？

参考回答

# 如何用栈实现一个队列？

30 秒速记

inStack 只负责入队，outStack 只负责出队。
只有 outStack 为空时才把 inStack 全部倒过去，不能每次出队都搬运。
每个元素最多被压入、转移、弹出各一次：单次最坏 O(n)，均摊 O(1)。
empty 同时检查两个栈，peek 与 pop 应共用转移函数。

回答参考：“两次 LIFO 会恢复 FIFO。我采用懒转移：输出栈非空时继续消费，只有它空了才批量反转输入栈。”

题目描述：使用栈实现队列的下列操作：

push(x) – 将一个元素放入队列的尾部。
pop() – 从队列首部移除元素。
peek() – 返回队列首部的元素。
empty() – 返回队列是否为空。

示例:

MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // 返回 1
queue.pop(); // 返回 1
queue.empty(); // 返回 false

说明:

你只能使用标准的栈操作 – 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
假设所有操作都是有效的（例如，一个空的队列不会调用 pop 或者 peek 操作）。

思路分析

做这道题大家首先要在心里清楚一个事情：栈和队列的区别在哪里？

乍一看有点头大：栈结构决定了栈底元素只能被死死地压在最底下，如何使它首先被取出呢？

一个栈做不到的事情，我们用两个栈来做：

首先，准备两个栈：

此时 1 变得触手可及。不仅如此，下一次我们试图出队 2 的时候，可以继续直接对 stack2 执行出栈操作——因为转移 2 和 3 的时候已经做过一次逆序了，此时 stack2 的出栈序列刚好就对应队列的出队序列。
有同学会问，那如果 stack1 里入栈新元素怎么办？比如这样：

你会发现这个4按照顺序应该在 1、2、3 后出栈。当 4 需要被出栈时，stack2 一定已经空掉了。当 stack2 为空、而 stack1 不为空时，我们需要继续把 stack1 中的元素转移到 stack2 中去，然后再从 stack2 里取元素。也就是说，所有的出队操作都只能依赖 stack2 来完成——只要我们坚持这个原则，就可以确保 stack1 里的元素都能够按照正确的顺序（逆序）出栈。

我们按照这个思路来写代码：

编码实现

/**
 * 初始化构造函数
 */
const MyQueue = function () {
  // 初始化两个栈
  this.stack1 = [];
  this.stack2 = [];
};

/**
* Push element x to the back of queue.
* @param {number} x
* @return {void}
*/
MyQueue.prototype.push = function (x) {
  // 直接调度数组的 push 方法
  this.stack1.push(x);
};

/**
* Removes the element from in front of queue and returns that element.
* @return {number}
*/
MyQueue.prototype.pop = function () {
  // 假如 stack2 为空，需要将 stack1 的元素转移进来
  if (this.stack2.length <= 0) {
    // 当 stack1 不为空时，出栈
    while (this.stack1.length !== 0) {
      // 将 stack1 出栈的元素推入 stack2
      this.stack2.push(this.stack1.pop());
    }
  }
  // 为了达到逆序的目的，我们只从 stack2 里出栈元素
  return this.stack2.pop();
};

/**
* Get the front element.
* @return {number}
* 这个方法和 pop 唯一的区别就是没有将定位到的值出栈
*/
MyQueue.prototype.peek = function () {
  if (this.stack2.length <= 0) {
    // 当 stack1 不为空时，出栈
    while (this.stack1.length != 0) {
      // 将 stack1 出栈的元素推入 stack2
      this.stack2.push(this.stack1.pop());
    }
  }
  // 缓存 stack2 的长度
  const stack2Len = this.stack2.length;
  return stack2Len && this.stack2[stack2Len - 1];
};

/**
* Returns whether the queue is empty.
* @return {boolean}
*/
MyQueue.prototype.empty = function () {
  // 若 stack1 和 stack2 均为空，那么队列空
  return !this.stack1.length && !this.stack2.length;
};

@前端进阶之旅: 代码已经复制到剪贴板