Python力扣刷题09-用栈实现队列&用队列实现栈

秒速五厘米 2023-09-28 23:23 1阅读 0赞

#### 目录 ####

*   *   *  232.用栈实现队列
         *  225. 用队列实现栈

#### 232.用栈实现队列 ####

**题目链接**：https://leetcode.cn/problems/implement-queue-using-stacks/

题目描述：使用栈实现队列的下列操作：

push(x) – 将一个元素放入队列的尾部。  
pop() – 从队列首部移除元素。  
peek() – 返回队列首部的元素。  
empty() – 返回队列是否为空。

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（`push`、`pop`、`peek`、`empty`）：

**案例**：

输入：
    ["MyQueue", "push", "push", "peek", "pop", "empty"]
    [[], [1], [2], [], [], []]
    输出：
    [null, null, null, 1, 1, false]
    
    解释：
    MyQueue myQueue = new MyQueue();
    myQueue.push(1); // queue is: [1]
    myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
    myQueue.peek(); // return 1
    myQueue.pop(); // return 1, queue is [2]
    myQueue.empty(); // return false

**说明**:

*  你只能使用标准的栈操作 – 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
 *  你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
 *  假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）

**实现**：

class MyQueue:
    
        def __init__(self):
            # in负责push，out负责pop
            self.stack_in = []
            self.stack_out = []
    
        def push(self, x: int) -> None:
            # 新元素进入，向in里面push
            self.stack_in.append(x)
    
        def pop(self) -> int:
            # 从队列开头移除并返回元素
            if self.empty():
                return None
            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) -> int:
            # 功能同pop函数
            ans = self.pop()
            self.stack_out.append(ans)
            return ans
    
        def empty(self) -> bool:
            # 只要in或out有元素，说明队列不为空
            return not (self.stack_in or self.stack_out)
    
    
    
    # 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()

#### 225. 用队列实现栈 ####

**题目链接**：https://leetcode.cn/problems/implement-stack-using-queues/

**题目描述**：使用队列实现栈的下列操作：

*  push(x) – 元素 x 入栈
 *  pop() – 移除栈顶元素
 *  top() – 获取栈顶元素
 *  empty() – 返回栈是否为空

**注意**:

*  你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
 *  你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
 *  你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。

**案例**：

输入：
    ["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

**实现**：

通过两个队列来实现

from collections import deque
    
    class MyStack:
    
        def __init__(self):
            """
            Python普通的Queue或SimpleQueue没有类似于peek的功能
            也无法用索引访问，在实现top的时候较为困难。
    
            用list可以，但是在使用pop(0)的时候时间复杂度为O(n)
            因此这里使用双向队列，我们保证只执行popleft()和append()，因为deque可以用索引访问，可以实现和peek相似的功能
    
            in - 存所有数据
            out - 仅在pop的时候会用到
            """
            self.queue_in = deque()
            self.queue_out = deque()
    
        def push(self, x: int) -> None:
            """
            直接append即可
            """
            self.queue_in.append(x)
    
    
        def pop(self) -> int:
            """
            1. 首先确认不空
            2. 因为队列的特殊性，FIFO，所以我们只有在pop()的时候才会使用queue_out
            3. 先把queue_in中的所有元素（除了最后一个），依次出列放进queue_out
            4. 交换in和out，此时out里只有一个元素
            5. 把out中的pop出来，即是原队列的最后一个
            
            tip：这不能像栈实现队列一样，因为另一个queue也是FIFO，如果执行pop()它不能像
            stack一样从另一个pop()，所以干脆in只用来存数据，pop()的时候两个进行交换
            """
            if self.empty():
                return None
    
            for i in range(len(self.queue_in) - 1):
                self.queue_out.append(self.queue_in.popleft())
            
            self.queue_in, self.queue_out = self.queue_out, self.queue_in    # 交换in和out，这也是为啥in只用来存
            return self.queue_out.popleft()
    
        def top(self) -> int:
            """
            1. 首先确认不空
            2. 我们仅有in会存放数据，所以返回第一个即可
            """
            if self.empty():
                return None
            
            return self.queue_in[-1]
    
    
        def empty(self) -> bool:
            """
            因为只有in存了数据，只要判断in是不是有数即可
            """
            return len(self.queue_in) == 0
    
    
    
    # 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()

优化：通过一个队列来实现

一个队列在模拟栈弹出元素的时候只要将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部，此时在去弹出元素就是栈的顺序了

class MyStack:
    
        def __init__(self):
            self.que = deque()
    
        def push(self, x: int) -> None:
            self.que.append(x)
    
        def pop(self) -> int:
            if self.empty():
                return None
            for i in range(len(self.que)-1):
                self.que.append(self.que.popleft())
            return self.que.popleft()
    
        def top(self) -> int:
            if self.empty():
                return None
            return self.que[-1]
    
        def empty(self) -> bool:
            return not self.que