程序员面试金典 - 面试题 03.04. 化栈为队

题目难度: 简单

原题链接

今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~

题目描述

实现一个 MyQueue 类，该类用两个栈来实现一个队列。

示例：

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. 如何操作两个栈来模拟队列顺序?

解决方案

思路

• 使用两个栈: 一个作为 push 的输入栈, 存正常的元素插入顺序; 另一个作为队列的输出栈, 存元素插入顺序的逆序, 这样输出栈的顶就是队列的头
• push 时: 直接 push 到输入栈即可
• pop 和 peek 时: 如果输出栈还有元素, 则直接用它的顶; 否则将当前输入栈的元素倒入输出栈中, 然后再用输出栈的顶

复杂度

• 时间复杂度 O(1): 显然 push 和 empty 操作是 O(1), 而虽然 pop 和 peek 有可能涉及两个栈元素的移动, 但每个元素最多被操作两次 (一次是加入到输入栈, 一次是移动到输出栈), 所以均摊下来它们的时间复杂度也为 O(1)
• 空间复杂度 O(N): 使用了两个栈存 N 个元素

代码

class MyQueue:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        # 初始化输入栈和输出栈
        self.stackIn = []
        self.stackOut = []

    def push(self, x: int) -> None:
        """
        Push element x to the back of queue.
        """
        # 直接追加到输入栈
        self.stackIn.append(x)

    def pop(self) -> int:
        """
        Removes the element from in front of queue and returns that element.
        """
        if self.empty():
            # 没有元素, pop返回-1
            return -1
        res = self.peek()
        # 此时直接pop输出栈即可, peek的时候已经做好了栈的转移
        self.stackOut.pop()
        return res

    def peek(self) -> int:
        """
        Get the front element.
        """
        if self.empty():
            # 没有元素, peek返回-1
            return -1
        if self.stackOut:
            # 如果逆序的输出栈还有元素, 栈顶即为队列头
            return self.stackOut[-1]
        else:
            # 此时需要将输入栈的元素逆序倒入输出栈中, 然后仍返回输出栈的栈顶
            while self.stackIn:
                self.stackOut.append(self.stackIn.pop())
            return self.stackOut[-1]

    def empty(self) -> bool:
        """
        Returns whether the queue is empty.
        """
        # 如果两个栈都没有元素, 则队列为空
        return not self.stackIn and not self.stackOut

大家可以在下面这些地方找到我~😊

我的知乎专栏

我的头条号

我的 CSDN

我的 Leetcode

我的牛客网博客

我的公众号: 算法精选, 欢迎大家扫码关注~😊