232.用栈实现队列

思路：栈是先入后出，队列是先入先出，因此用栈实现队列，可以用“负负得正”的思想，用两个栈实现先入先出。用栈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

上一页231.2的幂下一页234. 回文链表

最后更新于3年前