用栈实现队列python(leetcode232)

#232. 用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(pushpoppeekempty):

python中数组的pop默认是针对数组中的最后一个元素,数组的pop就是栈的pop操作

class MyQueue(object):
    # 使用两个栈进行模拟队列

    def __init__(self):
        self.stack_in = [] # 输入栈
        self.stack_out = [] # 输出栈

    def push(self, x):
        """
        :type x: int
        :rtype: None
        """
        self.stack_in.append(x)
        
    def pop(self):
        """
        :rtype: int
        """
        # 数组的pop默认是针对数组中的最后一个元素,数组的pop就是栈的pop操作
        # 当输出栈空时,将输入栈的元素全部先pop弹出,再用数组的append压入stack_out,
        # pop弹出的是最后进入stack_in的元素,append压入后为变为数组的第一个元素,再用pop弹出时是最后被弹出
        # 所以stack_in中的第一个进入的元素,进入stack_out后为最后一个元素,pop弹出时为第一个
        if self.stack_out:
            return self.stack_out.pop()
        else:
            for i in range(len(self.stack_in)):
                self.stack_out.append(self.stack_in.pop())
        return self.stack_out.pop()

    def peek(self):
        """
        :rtype: int
        """
        # 返回队列开头的元素
        # 利用刚实现的pop操作
        # pop会删除元素,
        res = self.pop()
        # 假设连续调用两次peek,队列开头的元素就变了,因为上一个开头被pop删除,也会影响其他操作
        # 将刚被pop的元素加入stack_out,首先不会影响队列的pop操作,
        # 其次,下次调用peek之前还会调用pop操作,pop会先弹stack_out的元素,此时stack_out中元素还是开头
        self.stack_out.append(res)
        return res

    def empty(self):
        """
        :rtype: bool
        """
        # 当输出栈和输入栈同时为空才为空
        if self.stack_in or self.stack_out:
            return False 
        else:
            return True 

# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()

上一篇:856_括号的分数


下一篇:栈实现综合计算器(中缀表达式)