面试题9_用两个栈实现队列.md

面试题 9 ：用两个栈实现队列

---

leetcode-cn 题目地址

📗difficulty：Easy

🎯Tags：

• 栈
• 设计

---

1. 题目描述📃

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

样例 1：

• 输入： ["CQueue","appendTail","deleteHead","deleteHead"] [[],[3],[],[]]
• 输出：[null,null,3,-1]

即，创建一个队列，添加元素 3 ，再出队一个元素，再出队一个元素。

2. 解题思路💡

以上面这个例子作为演示。依次插入元素 a、b、c 之后，stack2 为空，此时需要删除队列头。可行的操作是：将 stack1 的元素全部 push 到 stack2 中，pop 掉 stack2 的栈顶元素即可。此时如果需要再删除队列头，stack2 非空，pop 出栈顶元素即可。

而添加元素，直接添加至 stack1 即可。

总结以上 2 个情况，编写代码。

class CQueue {

    Stack<Integer> stack_in;
    Stack<Integer> stack_out;

    public CQueue() {
        this.stack_in = new Stack<>();
        this.stack_out = new Stack<>();
    }

    public void appendTail(int value) {
        this.stack_in.push(value);
    }

    public int deleteHead() {
        if (this.stack_out.isEmpty()) {
            if (this.stack_in.isEmpty()) {
                // 均为空时，说明队列为空
                return -1;
            }
            while (!this.stack_in.isEmpty()) {
                this.stack_out.push(this.stack_in.pop());
            }
            return this.stack_out.pop();
        }
        return this.stack_out.pop();
    }
}

复杂度分析：

• 时间复杂度：O(n)

• 空间复杂度：O(n)

3. 总结🎯

思考题

使用 2 个队列，来实现 1 个栈。

对于压入数据到栈中，直接将元素入队到 queue1 中即可。

弹出栈顶元素则需要分情况讨论：

• 当 queue2 为空的情况下：

  • 如果 queue1 也为空，那么栈空。
  • 如果 queue1 的元素数量多余 1 个，那么就依次出队元素，并存入到 queue2 中。最后出队 queue1 的队头元素，完成“弹栈操作”。

• 在 queue2 不为空的情况下，此时的栈顶元素为 queue2 的队尾。将 queue2 中除队尾的元素依次出队，并存入到 queue1 中，最后出队 queue2 的队尾，完成“弹栈操作”。

public class StackImplementUsingQueue {
    Queue<Integer> queue_in;
    Queue<Integer> queue_out;

    public StackImplementUsingQueue() {
        this.queue_in = new LinkedList<>();
        this.queue_out = new LinkedList<>();
    }

    public void pushToStack(int value) {
        this.queue_in.add(value);
    }

    public int popFromStack() {
        if (this.queue_out.isEmpty()) {
            if (this.queue_in.isEmpty()) {
                // 2 个 queue 均空时，表示栈空，返回 -1
                return -1;
            }
            while (this.queue_in.size() != 1) {
                // 当 in 队列还有最后一个尾部元素时，将其余元素转移至 out 中
                // 相当于将”栈顶元素“挤到 in 的头元素位置
                // 最后删除 in 的头元素，即完成了“弹栈”操作
                this.queue_out.add(this.queue_in.remove());
            }
            return this.queue_in.remove();
        } else {
            // 当 out 中存在元素时，需要将 out 中的元素入队到 in 中
            // 将 out 的队尾，即“栈顶元素”挤到 out 的头元素位置
            // 再将 out 头元素出队，即完成了”弹栈“操作
            while (this.queue_out.size() != 1) {
                this.queue_in.add(this.queue_out.remove());
            }
            return this.queue_out.remove();
        }
    }

    public static void main(String[] args) {
        StackImplementUsingQueue stack = new StackImplementUsingQueue();
        stack.pushToStack(1);
        stack.pushToStack(2);
        stack.pushToStack(3);
        stack.pushToStack(4);
        System.out.println(stack.popFromStack());
        System.out.println(stack.popFromStack());
        stack.pushToStack(5);
        stack.pushToStack(6);
        System.out.println(stack.popFromStack());
        System.out.println(stack.popFromStack());
        stack.pushToStack(7);
        System.out.println(stack.popFromStack());
        System.out.println(stack.popFromStack());
        System.out.println(stack.popFromStack());
        System.out.println(stack.popFromStack());
        System.out.println(stack.popFromStack());
    }

输出为：

4
3
6
5
7
2
1
-1
-1

Process finished with exit code 0

复杂度分析：

• 时间复杂度：O(n)

• 空间复杂度：O(n)