232. 用栈实现队列（Python）

题目

难度：★★☆☆☆
类型：队列，栈

使用栈实现队列的下列操作：

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 操作）。

解答

这道题目是【题目225. 用队列实现栈】的逆过程，道理完全相同。这里我们使用两个栈来实现队列。我们首先定义了一个栈类（Queue），具有入栈（push）和出栈（pop）两个方法，以及栈长度（length）和栈是否为空（is_empty）两个属性：

push()：元素入栈成为栈顶，没有返回值；
pop()：栈顶元素出栈，返回值为出栈元素；
length：获得当前栈的长度；
is_empty：获得当前栈是否为空，如果为空返回True。

首先，我们实例化一个基本栈stack1和一个辅助栈stack2，每次操作后，基本栈中的元素就是队列中的元素，辅助栈用于暂存基本栈中的元素。队列的每一个方法这样实现：

push()：元素入队，直接在基本栈stack1中加入元素即可；
pop()：队头元素出队，将基本栈stack1中的每次元素出队并依次加入辅助栈stack2中，当只剩下一个元素res时，把这个元素拿出来，不加入stack2，然后把辅助栈stack2中的所有元素依次返还基本栈stack1，并返回之前被拿出来的元素res即可。
top()：获取队头元素，实现方法与pop十分相似，唯一只是res会被再加入到stack2中；
empty()：判断队列是否为空，队列的状态与基本栈queue1完全一致，因此直接返回queue1的is_empty方法即可。

class Stack(object):
    def __init__(self):
        self.stack = []

    def push(self, x):              # 入栈
        self.stack.append(x)

    def pop(self):                  # 出栈
        if self.is_empty:           # 注意特殊情况
            return None
        return self.stack.pop()

    @property
    def length(self):               # 获取栈中元素
        return len(self.stack)
    
    @property                      
    def is_empty(self):            # 获取栈的状态：是否为空
        return self.length == 0


class MyQueue(object):
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.stack1 = Stack()                           # 基本栈
        self.stack2 = Stack()                           # 辅助栈

    def push(self, x):
        """
        Push element x to the back of queue.
        :type x: int
        :rtype: None
        """
        self.stack1.push(x)                             # 入栈，即入队列

    def pop(self):
        """
        Removes the element from in front of queue and returns that element.
        :rtype: int
        """
        while self.stack1.length > 1:                   # 卡住要出栈的最后一个元素
            self.stack2.push(self.stack1.pop())         # 其他元素倒进辅助栈
        res = self.stack1.pop()                         # 那个被卡住的元素就是所需
        while not self.stack2.is_empty:                 # 只要辅助栈不为空
            self.stack1.push(self.stack2.pop())         # 辅助栈中的元素倒回基本栈
        return res                                      # 返回栈底元素即为出队队头

    def peek(self):
        """
        Get the front element.
        :rtype: int
        """
        while self.stack1.length > 1:                   # 卡住要出栈的最后一个元素
            self.stack2.push(self.stack1.pop())         # 其他元素倒进辅助栈
        res = self.stack1.pop()                         # 那个被卡住的元素就是所需
        self.stack2.push(res)                           # 记得把被卡住的元素放回
        while self.stack2.length > 0:                   # 只要辅助栈不为空
            self.stack1.push(self.stack2.pop())         # 辅助栈中的元素倒回基本栈
        return res                                      # 返回栈底元素即为出队队头

    def empty(self):
        """
        Returns whether the queue is empty.
        :rtype: bool
        """
        return self.stack1.is_empty                     # 队列的状态即为基本栈的状态

如有疑问或建议，欢迎评论区留言~

最后编辑于：2019.05.15 10:11:14