【Leetcode刷题Python】232. 用栈实现队列

1 题目

请你仅使用两个栈实现先入先出队列。

队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

void push(int x)将元素 x 推到队列的末尾 int pop() 从队列的开头移除并返回元素 int peek() 返回队列开头的元素 boolean empty()如果队列为空，返回 true ；否则，返回 false

2 解析

注意：peek()和pop()的区别是，peek()不出栈，pop()要出栈。 （1）入队（push） 一个队列是 先入先出的，但一个栈是 先入后出 的。这就意味着需要两个栈s1和s2来实现队列。 入队，即是将元素入栈s1 （2）出队（pop） 出队，即是将s1所有元素入s2，后再弹出s2栈顶。 （3）返回队首（peek） 返回队首，即是将s1所有元素入s2，后再返回s2栈顶。 （4）判断队是否为空 需要两个栈都为空，即为队列空。

3 python

class MyQueue:

    def __init__(self):
        self.stackIn = []
        self.stackOut = []


    def push(self, x: int) -> None:
        self.stackIn.append(x)

    def pop(self) -> int:
        if not self.stackOut:
            while self.stackIn:
                self.stackOut.append(self.stackIn.pop())
        return self.stackOut.pop()
        

    def peek(self) -> int:
        if not self.stackOut:
            while self.stackIn:
                self.stackOut.append(self.stackIn.pop())
        return self.stackOut[-1]

    def empty(self) -> bool:
        return not self.stackOut and not self.stackIn