用队列实现栈-LeetCode

用队列实现栈

🎯 问题描述（来源于LeetCode）

描述：
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

• void push(int x) 将元素 x 压入栈顶。

• int pop() 移除并返回栈顶元素。

• int top() 返回栈顶元素。

• boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
  说明：

示例：

• 示例 1：

输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]

解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

💻 解题思路

思路1：q存储数据+p为辅助队列

思路1：代码实现

import queue
class MyStack:

    def __init__(self):
        self.q=queue.Queue()
        self.p=queue.Queue()

    def push(self, x: int) -> None:
        self.q.put(x)


    def pop(self) -> int:
        while self.q.qsize()>1:
            self.p.put(self.q.get())
        a=self.q.get()
        while self.p.qsize()>0:
            self.q.put(self.p.get())
        return a

    def top(self) -> int:
        while self.q.qsize()>1:
            self.p.put(self.q.get())
        a=self.q.get()
        while self.p.qsize()>0:
            self.q.put(self.p.get())
        self.q.put(a)        
        return a

    def empty(self) -> bool:
        return self.q.empty()


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

思路1：📊 性能分析

提交结果

• 运行时间：0ms

击败100.00%

• 内存消耗：19.52MB

击败5.56%

复杂度验证

• 时间复杂度：$O(N)$
• 空间复杂度：$O(N)$

思考