225. 用队列实现栈（Python）

题目

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

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

push(x) -- 元素 x 入栈
pop() -- 移除栈顶元素
top() -- 获取栈顶元素
empty() -- 返回栈是否为空

注意:

你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。

你所使用的语言也许不支持队列。你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。

解答

这里我们使用两个队列来实现栈。我们首先定义了一个队列类（Queue），具有入队（push）和出队（pop）两个方法，以及队列长度（length）和队列是否为空（is_empty）两个属性：

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

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

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

class Queue(object):
    def __init__(self):
        self.queue = []

    def push(self, x):
        self.queue.append(x)

    def pop(self):
        if self.is_empty:
            return None
        return self.queue.pop(0)

    @property
    def length(self):                   # 获取队列的当前长度
        return len(self.queue)

    @property                   
    def is_empty(self):                 # 获取队列的当前状态：是否为空
        return self.length == 0


class MyStack(object):
    def __init__(self):
        """
        Initialize your data structure here.
        """

        self.queue1 = Queue()                       # 一个基本队列
        self.queue2 = Queue()                       # 一个辅助队列

    def push(self, x):
        """
        Push element x onto stack.
        :type x: int
        :rtype: None
        """
        self.queue1.push(x)                         # 加入元素

    def pop(self):
        """
        Removes the element on top of the stack and returns that element.
        :rtype: int
        """

        while self.queue1.length > 1:               # 卡住最后一个要出队的数
            self.queue2.push(self.queue1.pop())     # 队头元素出队出队后马上进入辅助队列

        res = self.queue1.pop()                     # 最后一个准备出队的元素就是要弹出的栈顶元素

        while not self.queue2.is_empty:             # 只要辅助队列还有元素
            self.queue1.push(self.queue2.pop())     # 将辅助队列中的所有元素依次归还基本队列
        return res                                  # 返回结果

    def top(self):
        """
        Get the top element.
        :rtype: int
        """
        while self.queue1.length > 1:               # 卡住最后一个要出队的数
            self.queue2.push(self.queue1.pop())     # 队头元素出队出队后马上进入辅助队列

        res = self.queue1.pop()                     # 最后一个准备出队的元素就是要返回的栈顶元素
        self.queue2.push(res)

        while not self.queue2.is_empty:             # 只要辅助队列还有元素
            self.queue1.push(self.queue2.pop())     # 将辅助队列中的所有元素依次归还基本队列
        return res                                  # 返回结果

    def empty(self):
        """
        Returns whether the stack is empty.
        :rtype: bool
        """
        return self.queue1.is_empty

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

最后编辑于：2019.05.14 16:51:34