443_栈与队列面试题¶

# 栈：用 list 末尾模拟
stack = []
stack.append(x)    # 入栈
stack.pop()        # 出栈（取末尾）
stack[-1]          # 查栈顶

# 队列：用 collections.deque
from collections import deque
q = deque()
q.append(x)        # 入队（尾部）
q.popleft()        # 出队（头部），比 list.pop(0) 快 O(1)
q[0]               # 查队头

def is_valid(s: str) -> bool:
    """
    思路：遇到左括号入栈，遇到右括号和栈顶左括号配对
    最后栈为空说明全部匹配
    """
    stack = []
    # 右括号→对应左括号的映射表
    mapping = {')': '(', ']': '[', '}': '{'}

    for char in s:
        if char in mapping:                # 是右括号
            # 栈顶如果是对应的左括号，出栈配对；否则用'#'占位让后续判断失败
            top = stack.pop() if stack else '#'
            if mapping[char] != top:       # 不匹配
                return False
        else:                              # 是左括号，入栈
            stack.append(char)

    return not stack                       # 栈为空说明全部匹配

# 测试
print(is_valid("()[]{}"))  # True
print(is_valid("(]"))      # False
print(is_valid("([)]"))    # False
print(is_valid("{[]}"))    # True

def daily_temperatures(temperatures):
    """
    单调递减栈：栈里存下标，栈内对应温度始终递减
    当遇到比栈顶更高的温度，栈顶"等待结束"，计算等待天数

    比喻：栈里是"还在排队等暖和天气的人的位置"
    新来一个热天，所有比它冷的天都出队计算
    """
    n = len(temperatures)
    result = [0] * n                       # 初始化结果数组
    stack = []                             # 单调递减栈，存下标

    for i in range(n):
        # 当前温度比栈顶温度高，栈顶等到了更暖的天
        while stack and temperatures[i] > temperatures[stack[-1]]:
            idx = stack.pop()              # 出栈：等待结束的那天
            result[idx] = i - idx          # 等待天数 = 当前下标 - 出栈下标

        stack.append(i)                    # 当前天入栈，开始等待

    # 栈中剩余的都是没等到更暖天的，result已初始化为0

    return result

# 测试
temps = [73, 74, 75, 71, 69, 72, 76, 73]
print(daily_temperatures(temps))  # [1, 1, 4, 2, 1, 1, 0, 0]

class MyQueue:
    """
    两个栈模拟队列
    in_stack：接收新入队的元素
    out_stack：提供出队的元素

    当 out_stack 为空时，把 in_stack 全部倒入 out_stack
    （倒一次后顺序就正确了）
    """
    def __init__(self):
        self.in_stack = []                 # 入队用的栈
        self.out_stack = []                # 出队用的栈

    def push(self, x: int) -> None:
        self.in_stack.append(x)            # 直接压入 in_stack

    def pop(self) -> int:
        self._move_if_needed()             # 如果 out_stack 空，先转移
        return self.out_stack.pop()        # 从 out_stack 弹出

    def peek(self) -> int:
        self._move_if_needed()
        return self.out_stack[-1]          # 查看 out_stack 栈顶

    def empty(self) -> bool:
        return not self.in_stack and not self.out_stack

    def _move_if_needed(self):
        """out_stack 空时把 in_stack 全部倒入"""
        if not self.out_stack:
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())

# 测试
q = MyQueue()
q.push(1)
q.push(2)
print(q.peek())   # 1（先进先出）
print(q.pop())    # 1
print(q.empty())  # False

from collections import deque

# 栈（LIFO）
stack = []
stack.append(x)         # 入栈 O(1)
stack.pop()             # 出栈 O(1)
stack[-1]               # 查栈顶 O(1)

# 队列（FIFO）
q = deque()
q.append(x)             # 入队 O(1)
q.popleft()             # 出队 O(1)
q[0]                    # 查队头 O(1)

# 单调栈模板
stack = []
for i in range(n):
    while stack and condition(nums[stack[-1]], nums[i]):
        idx = stack.pop()
        # 处理出栈元素
    stack.append(i)

# BFS 模板（用队列）
from collections import deque
queue = deque([start])
visited = {start}
while queue:
    node = queue.popleft()
    for neighbor in graph[node]:
        if neighbor not in visited:
            visited.add(neighbor)
            queue.append(neighbor)