232.用栈实现队列

https://leetcode-cn.com/problems/implement-queue-using-stacks/

思路:栈是先入后出,队列是先入先出,因此用栈实现队列,可以用“负负得正”的思想,用两个栈实现先入先出。 用栈s1记录入队顺序,只要有入队操作都进入s1 栈s2用于保持出队顺序,出队操作时s2出栈;当s2为空时,出队操作前先将s1全部出栈并入s2 队头元素:当s2非空,即为s2的栈顶;否则为s1的栈底

py的stack没有底层实现,直接用list,出栈为list.pop(),入栈为list.append(x),栈顶为list[-1],栈底为list[0],空栈为:

if list:	# 空列表的布尔值为False
	...

if len(list) == 0:
	...
class MyQueue:
    def __init__(self):
        self.s1 = []
        self.s2 = []
        
    def push(self, x: int) -> None:
        self.s1.append(x)

    def pop(self) -> int:
        if not self.s2:	#若s2为空,s1全部入填入s2
            while self.s1:
                x = self.s1.pop()
                self.s2.append(x)
        return(self.s2.pop())

    def peek(self) -> int:
        if self.s2:
            return self.s2[-1]
        else:
            return self.s1[0]

    def empty(self) -> bool:
        return not self.s1 and not self.s2

最后更新于