栈与队列基础#

1
class MyQueue:
2
    def __init__(self):
3
        self.stack1 = []  # 负责入队
4
        self.stack2 = []  # 负责出队
5

6
    def push(self, x: int) -> None:
7
        self.stack1.append(x)
8

9
    def pop(self) -> int:
10
        if self.empty():
11
            return None
12
        if self.stack2:
13
            return self.stack2.pop()
14
        else:
15
            # 只有在 stack2 为空时，才将 stack1 所有元素倒入 stack2
16
            while self.stack1:
17
                self.stack2.append(self.stack1.pop())
18
            return self.stack2.pop()
19

20
    def peek(self) -> int:
21
        # 先执行出队操作但不真正移除，再将值放回 stack2 中
22
        res = self.pop()
23
        self.stack2.append(res)
24
        return res
25

26
    def empty(self) -> bool:
27
        return not (self.stack1 or self.stack2)

1
from collections import deque
2

3
class MyStack:
4

5
    def __init__(self):
6
        self.q1 = deque()  # 主队列
7
        self.q2 = deque()  # 辅助队列
8

9
    def push(self, x: int) -> None:
10
        self.q1.append(x)
11

12
    def pop(self) -> int:
13
        # 将 q1 中前 n-1 个元素转移到 q2，保留最后一个
14
        while len(self.q1) > 1:
15
            self.q2.append(self.q1.popleft())
16
        res = self.q1.popleft()
17
        # 交换 q1 和 q2 的角色
18
        self.q1, self.q2 = self.q2, self.q1
19
        return res
20

21
    def top(self) -> int:
22
        res = self.pop()
23
        self.q1.append(res)
24
        return res
25

26
    def empty(self) -> bool:
27
        return len(self.q1) == 0

1
class Solution:
2
    def isValid(self, s: str) -> bool:
3
        stack = []
4
        for char in s:
5
            if char in "({[":
6
                stack.append(char)
7
            elif stack:
8
                top = stack.pop()
9
                if char == ')' and top != '(':
10
                    return False
11
                if char == '}' and top != '{':
12
                    return False
13
                if char == ']' and top != '[':
14
                    return False
15
            else:
16
                # 栈为空但遇到右括号，说明无效
17
                return False
18
        return len(stack) == 0

1
class Solution:
2
    def removeDuplicates(self, s: str) -> str:
3
        stack = []
4
        for char in s:
5
            if not stack:
6
                stack.append(char)
7
            else:
8
                top = stack.pop()
9
                if char != top:
10
                    stack.append(top)
11
                    stack.append(char)
12
        return ''.join(stack)