面试速答（先看这里）

**一句话结论：**可以使用两个栈来实现一个队列，一个栈用来存储入队的元素，另一个栈用来存储出队的元素。

60秒标准回答：

可以使用两个栈来实现一个队列，一个栈用来存储入队的元素，另一个栈用来存储出队的元素

入队时，直接将元素压入入队栈中。出队时，如果出队栈为空，则将入队栈中的所有元素弹出并压入出队栈中，然后从出队栈中弹出元素；否则直接从出队栈中弹出元素

这样可以保证出队栈中的元素顺序和队列中的元素顺序相同

**答题顺序：**结论 → 原理/机制 → 关键流程 → 场景与取舍 → 易错点

回答主线：

**要点1：**入队时，直接将元素压入入队栈中。
**要点2：**这样可以保证出队栈中的元素顺序和队列中的元素顺序相同。
**要点3：**其中，enqueue方法用来入队，直接将元素压入stackIn栈中。
**要点4：**dequeue方法用来出队，如果stackOut栈为空，则先将stackIn栈中的元素倒入stackOut栈中，再从stackOut栈中弹出元素，即为队头元素。
**要点5：**这个实现的时间复杂度为O(1)，空间复杂度为O(n)，其中n为队列中元素的个数。

**记忆锚点：**stackOut → stackIn → 栈中的元素顺序和队列 → 方法用来判断队列 → enqueue → dequeue

加分表达：

出队时，如果出队栈为空，则将入队栈中的所有元素弹出并压入出队栈中，然后从出队栈中弹出元素；
dequeue方法用来出队，如果stackOut栈为空，则先将stackIn栈中的元素倒入stackOut栈中，再从stackOut栈中弹出元素，即为队头元素。
isEmpty方法用来判断队列是否为空，如果stackIn和stackOut都为空，则队列为空。

追问准备：

围绕「stackOut」：底层原理是什么？使用时有哪些边界和常见坑？
围绕「stackIn」：底层原理是什么？使用时有哪些边界和常见坑？
围绕「栈中的元素顺序和队列」：底层原理是什么？使用时有哪些边界和常见坑？
如果线上出现异常，你会如何定位、验证并规避？

典型回答

可以使用两个栈来实现一个队列，一个栈用来存储入队的元素，另一个栈用来存储出队的元素。

入队时，直接将元素压入入队栈中。出队时，如果出队栈为空，则将入队栈中的所有元素弹出并压入出队栈中，然后从出队栈中弹出元素；否则直接从出队栈中弹出元素。

这样可以保证出队栈中的元素顺序和队列中的元素顺序相同。

plain

import java.util.Stack;

public class MyQueue<T> {
    private Stack<T> stackIn;
    private Stack<T> stackOut;

    public MyQueue() {
        stackIn = new Stack<>();
        stackOut = new Stack<>();
    }

    public void enqueue(T element) {
        stackIn.push(element);
    }

    public T dequeue() {
        if (stackOut.isEmpty()) {
            while (!stackIn.isEmpty()) {
                stackOut.push(stackIn.pop());
            }
        }
        return stackOut.pop();
    }

    public boolean isEmpty() {
        return stackIn.isEmpty() && stackOut.isEmpty();
    }
}

其中，enqueue方法用来入队，直接将元素压入stackIn栈中。

dequeue方法用来出队，如果stackOut栈为空，则先将stackIn栈中的元素倒入stackOut栈中，再从stackOut栈中弹出元素，即为队头元素。

isEmpty方法用来判断队列是否为空，如果stackIn和stackOut都为空，则队列为空。

这个实现的时间复杂度为O(1)，空间复杂度为O(n)，其中n为队列中元素的个数。

典型回答 ​

典型回答