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

典型回答

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

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

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

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为队列中元素的个数。

原文: https://www.yuque.com/hollis666/xkm7k3/uz4sam5iyt87ngcn