【LeetCode 刷题】栈与队列-基础操作

此博客为《代码随想录》字符串章节的学习笔记，主要内容为栈与队列基础操作相关的题目解析。

文章目录

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

232. 用栈实现队列

题目链接

class MyQueue:

    def __init__(self):
        self.in_s, self.out_s = [], [] 
        
    def push(self, x: int) -> None:
        self.in_s.append(x)

    def pop(self) -> int:
        self.move()
        return self.out_s.pop()

    def peek(self) -> int:
        self.move()
        return self.out_s[-1]

    def empty(self) -> bool:
        return not self.in_s and not self.out_s

    def move(self):
        if not self.out_s:
            while self.in_s:
                self.out_s.append(self.in_s.pop())

• list.append(obj)：（参数为元素）在列表末尾添加新的对象
• list.pop([index=-1])：（参数为下标）移除列表中的一个元素（默认最后一个元素），并且返回该元素的值
• 特点：
  • 两个栈，一个作为输入，一个作为输出
  • peek 和 pop 操作会触发元素从 in_s 到 out_s 的转移
  • 当两个栈均为空时，表明模拟的队列为空

225. 用队列实现栈

题目链接

class MyStack:

    def __init__(self):
        self.main_q, self.sub_q = [], []

    def push(self, x: int) -> None:
        self.sub_q.append(x)
        while self.main_q:
            self.sub_q.append(self.main_q.pop(0))
        self.main_q, self.sub_q = self.sub_q, self.main_q

    def pop(self) -> int:
        return self.main_q.pop(0)

    def top(self) -> int:
        return self.main_q[0]

    def empty(self) -> bool:
        return not self.main_q

• 特点：
  • 两个队列，一个为主队列，另一个仅仅为辅助队列，类似于临时变量作用（因此一个队列也可求解）
  • push 操作会触发元素从 main_q 到 sub_q 的转移
  • 当主队列为空时，表明模拟的栈为空