代码随想录算法训练营第10天 | 栈和队列 232.用栈实现队列 225.用队列实现栈

leetcode 232.用栈实现队列

题目

232.用栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false

解题思路

1、定义两个列表，列表1用于入栈，列表2用于出栈
2、push元素：直接使用list.append(s)向入栈列表中添加元素
3、empty:判断队列是否为空，如果入栈和出栈两个列表均为空，说明队列为空，返回True
4、pop元素：队列是先进先出
（1）如果队列为空，则pop弹出元素返回None
（2）如果队列不为空，判断出栈的列表是否为空
出栈列表不为空，直接使用pop函数从栈顶弹出元素
出栈列表为空，把入栈列表中的元素弹出到出栈列表中，再从出栈列表栈顶弹出元素
5、peek元素：
执行队列的pop操作，会把队列开头元素从出栈列表的栈顶弹出
再把弹出的元素放到出栈列表中，即可返回队列开头元素

实现代码

class MyQueue:
    def __init__(self):
        self.stack_in = []
        self.stack_out = []

    def push(self, x: int) -> None:
        self.stack_in.append(x)
    
    def pop(self) -> int:
        if self.empty():    # 如果队列为空，pop操作没有元素可以弹出，返回None
            return None
        
        if self.stack_out:  # 如果出栈中有元素，直接从栈的末尾弹出元素
            return self.stack_out.pop() # list.pop(index = -1) 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:
        res = self.pop()    # 从队列的开头移除并返回元素：入栈的元素全部弹出，插入到出栈中，再从出栈末尾依次弹出元素
        self.stack_out.append(res)  # 把从出栈栈顶弹出的元素再添加到出栈中
        return res  # 返回队列开头的元素

    def empty(self, x: int) -> bool:
        # 如果出栈和入栈都没有元素，则队列为空
        return not (self.stack_out or self.stack_in)    

leetcode 225.用队列实现栈

题目

225.用队列实现栈
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

解题思路

实现代码