结束了针对栈结构的定点轰炸，我们现在开始要缓缓过渡到队列的世界了。
关于队列，在算法面试中大家需要掌握以下重点：
- 栈向队列的转化
- 双端队列
- 优先队列
以上考点中，1 属于基础难度， 2 对一部分同学来说已经有点吃力，3 的区分度最高——优先队列属于高级数据结构，其本质是二叉堆结构，考虑到相关题目具有较强的综合性，我们把它放在小册二叉树和堆相关的专题来展开。在本节，我们集中火力向前两个命题点开炮。
# 为什么一道题可以成为高频面试题
30 秒速记
- 好面试题两个条件：考的是经典核心知识（公平），知识点密集综合（有区分度）
- 「用栈实现队列」同时考栈、队列、顺序转换和编码基本功，难度适中
- 深度不算高，但前端算法面试偏务实，不追求炫技
- 区分度靠追问拉开：为什么两次逆序能恢复
FIFO、什么时候倒栈、均摊复杂度 - 回答顺序：操作契约 → 为什么顺序对 → 复杂度，别只背代码
一道题能成为高频题，通常是因为它考的是最经典的知识，同时又把好几个知识点压在一道题里，十几分钟就能看出基本功。 「用栈实现队列」就是这样：栈是后进先出、队列是先进先出，你得想到用两个栈倒一下，还得写对什么时候倒、怎么判空。它不难，但前端面试本来就不太考偏题，面试官更关心你基础牢不牢。真正拉开差距的是追问，比如能不能讲清均摊 O(1)。
如何用栈实现队列？这个问题在近几年的算法面试中热度非常高。
所谓“热度”从何而来？这里就引出了一个非常有趣的话题：（在前端算法面试中）什么样的题目是好题？
首先，不能剑走偏锋：好的面试题，它考察的大多是算法/数据结构中最经典、最关键的一部分内容，这样才能体现公平；其次，它的知识点要尽可能密集、题目本身要尽可能具备综合性，这样才能一箭双雕甚至一箭N雕，进而体现区分度、最大化面试过程的效率。
能够同时在这两个方面占尽优势的考题其实并不是很多，“用栈实现队列”这样的问题算是其中的佼佼者：一方面，它考察的确实是数据结构中的经典内容；另一方面，它又覆盖了两个大的知识点、足以检验出候选人编码基本功的扎实程度。唯一的 BUG 可能就是深度和复杂度不够，换句话说就是不够难。
这个特点，在普通算法面试中可能是 BUG，但在前端算法面试中，实在未必。大家要知道，你是前端，你的面试官也是前端，前端行业普遍的算法水平是啥样他心里还没个数吗… 实际上大多数前端算法面试题的风格都是非常务实的，需要你炫技的实属特殊情况。
面试官追问
追问 1这题太简单了，能区分出候选人吗？
题目本身区分度一般，区分度在追问里。能当场写对的人很多，能讲清为什么只在输出栈空时才倒、均摊复杂度怎么算的人就少了。
追问 2面试只剩 15 分钟，为什么考这种题而不是动态规划？
它短时间内能同时看数据结构理解、代码完整性和复杂度分析。动态规划可能光建模就用完时间，基本功反而看不到。
追问 3候选人秒写出模板代码，你接着问什么？
问「为什么不能每次 push 后都倒过去」「peek 和 pop 怎么复用逻辑」「单次 pop 最坏是多少、均摊是多少」。背模板的人一般在这里卡住。
追问 4准备面试时，这类经典题该怎么练？
别只练能 AC，要练能讲：用一两句说清思路，说清为什么对，给出复杂度，再准备一两个变体，比如反过来用队列实现栈。
# 如何用栈实现一个队列？
30 秒速记
- 栈后进先出、队列先进先出，倒两次栈顺序就正过来了
inStack只管入队，outStack只管出队- 只有
outStack空了才把inStack整个倒过去，非空时别动 - 每个元素最多进
inStack、倒一次、出outStack各一次 → 均摊O(1)，单次最坏O(n) empty两个栈都要看；pop和peek共用倒栈逻辑；只能用push/pop/ 看栈顶 / 判空
用两个栈实现队列，一个栈专门进，一个栈专门出，出栈那个空了才把进栈那个整个倒过去。 倒一次顺序就反过来了，进栈底下最早进来的元素到了出栈的栈顶，正好是队头。关键规则是出栈不空时绝对不倒，不然新元素会插到老元素前面。每个元素一辈子只被倒一次，所以虽然某次 pop 可能要倒 n 个，平均下来每次还是 O(1)。
class MyQueue {
constructor() { this.inStack = []; this.outStack = [] }
push(x) { this.inStack.push(x) }
move() {
if (!this.outStack.length)
while (this.inStack.length) this.outStack.push(this.inStack.pop())
}
pop() { this.move(); return this.outStack.pop() }
peek() { this.move(); return this.outStack.at(-1) }
empty() { return !this.inStack.length && !this.outStack.length }
}
// push(1) push(2) peek() => 1，pop() => 1，empty() => false
回答参考：“两次 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
