LeetCode栈与队列实战：核心操作与高频题型解析

1. Leetcode栈与队列实战指南

作为一名刷过500+Leetcode题的老手，我深刻理解栈与队列这两个基础数据结构在算法面试中的核心地位。它们不仅是高频考点，更是解决复杂问题的关键工具。最近帮几个朋友做面试复盘时发现，80%的候选人都在栈队列类题目上栽过跟头——不是思路不对，而是对这两种数据结构的特性和应用场景理解不够透彻。

栈（Stack）是后进先出（LIFO）的线性结构，就像叠盘子——最后放上去的盘子总是最先被取走。队列（Queue）则是先进先出（FIFO），好比食堂排队——先来的人先打到饭。这两种结构在Leetcode中常以三种形式出现：纯数据结构操作题（如232用栈实现队列）、算法辅助工具（如20有效的括号）、以及特定问题解法（如239滑动窗口最大值）。

2. 栈与队列的核心操作与实现

2.1 栈的四种基本操作

栈的核心操作可以用四个方法概括：

python复制stack = []
stack.append(1)  # 入栈 push
top = stack[-1]  # 获取栈顶 peek
item = stack.pop()  # 出栈 pop
is_empty = len(stack) == 0  # 判空

C++中更规范的实现：

cpp复制#include <stack>
std::stack<int> s;
s.push(1);         // 入栈
int top = s.top(); // 获取栈顶
s.pop();           // 出栈（不返回元素）
bool e = s.empty();// 判空

关键细节：Python列表的pop()操作时间复杂度是O(1)，但insert(0, x)这种模拟栈底操作会变成O(n)。真正的栈应该只在同一端操作。

2.2 队列的两种实现方式

队列的标准实现需要支持：

java复制Queue<Integer> q = new LinkedList<>();
q.offer(1);   // 入队 add
q.poll();     // 出队 remove
q.peek();     // 查看队首 element
q.isEmpty();  // 判空

用栈实现队列是经典面试题（Leetcode 232）。核心思路是用两个栈形成"输入栈"和"输出栈"：

python复制class MyQueue:
    def __init__(self):
        self.in_stack = []
        self.out_stack = []

    def push(self, x):
        self.in_stack.append(x)

    def pop(self):
        if not self.out_stack:
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())
        return self.out_stack.pop()

3. 栈的六大经典应用场景

3.1 括号匹配问题（Leetcode 20）

判断括号是否有效是栈的招牌应用：

python复制def isValid(s: str) -> bool:
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}
    for char in s:
        if char in mapping.values():
            stack.append(char)
        elif not stack or mapping[char] != stack.pop():
            return False
    return not stack

避坑指南：遇到右括号时一定要先检查栈是否为空，否则pop()会报错。这是新手最常见的运行时错误。

3.2 单调栈解Next Greater Element

单调栈能在O(n)时间内解决一类特殊问题：

python复制def nextGreaterElements(nums):
    stack = []
    res = [-1] * len(nums)
    for i in range(len(nums)):
        while stack and nums[i] > nums[stack[-1]]:
            res[stack.pop()] = nums[i]
        stack.append(i)
    return res

这个模板稍加修改就能解决Leetcode 496、503、739等多道题目。关键在于维护栈内元素的单调性——以递减栈为例，遇到比栈顶大的元素时就不断弹出并记录结果。

4. 队列的三大高阶应用

4.1 二叉树的层序遍历（Leetcode 102）

队列是处理层级关系的利器：

python复制def levelOrder(root):
    if not root: return []
    queue = collections.deque([root])
    res = []
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left: queue.append(node.left)
            if node.right: queue.append(node.right)
        res.append(level)
    return res

4.2 滑动窗口最大值（Leetcode 239）

单调队列的经典应用：

python复制def maxSlidingWindow(nums, k):
    q = collections.deque()
    res = []
    for i, num in enumerate(nums):
        while q and nums[q[-1]] <= num:
            q.pop()
        q.append(i)
        if q[0] == i - k:
            q.popleft()
        if i >= k - 1:
            res.append(nums[q[0]])
    return res

这个解法将O(nk)的暴力解优化到O(n)，关键在于双端队列维护了当前窗口内的递减序列。每次窗口滑动时，移除过期索引并保持队列单调性。

5. 常见错误与调试技巧

5.1 栈溢出问题

递归本质上就是函数调用栈的应用，当递归过深时会引发栈溢出。比如二叉树遍历的递归写法在极端情况下（如斜树）可能爆栈。迭代解法通常更安全：

python复制# 递归前序遍历
def preorder(root):
    if not root: return
    print(root.val)
    preorder(root.left)
    preorder(root.right)

# 改为迭代
def preorder(root):
    stack = [root]
    while stack:
        node = stack.pop()
        if node:
            print(node.val)
            stack.append(node.right)  # 右子节点先入栈
            stack.append(node.left)

5.2 边界条件处理

栈队列问题中90%的错误都出在边界条件上：

1. 操作空栈/空队列（特别是peek/pop时）
2. 循环终止条件判断（如while stack应该放在哪个位置）
3. 索引越界（滑动窗口问题时尤为常见）

一个实用的调试技巧是：在每次操作前后打印栈/队列状态。例如在实现最小栈时：

python复制class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, x):
        print(f"Before push - stack: {self.stack}, min_stack: {self.min_stack}")
        self.stack.append(x)
        if not self.min_stack or x <= self.min_stack[-1]:
            self.min_stack.append(x)
        print(f"After push - stack: {self.stack}, min_stack: {self.min_stack}")

6. 进阶挑战与扩展学习

6.1 用队列实现栈（Leetcode 225）

与栈实现队列不同，用队列实现栈有更巧妙的单队列解法：

python复制class MyStack:
    def __init__(self):
        self.q = collections.deque()

    def push(self, x):
        self.q.append(x)
        for _ in range(len(self.q) - 1):
            self.q.append(self.q.popleft())

    def pop(self):
        return self.q.popleft()

这个实现的关键在于每次push时都将新元素调整到队列前端，使得队列始终保持栈的顺序。虽然push操作变成O(n)，但符合题目要求。

6.2 表达式求值（Leetcode 224/227）

栈在处理表达式求值时展现出强大威力。以基本计算器II为例：

python复制def calculate(s):
    stack = []
    num = 0
    sign = '+'
    for i, c in enumerate(s):
        if c.isdigit():
            num = num * 10 + int(c)
        if (not c.isdigit() and c != ' ') or i == len(s) - 1:
            if sign == '+':
                stack.append(num)
            elif sign == '-':
                stack.append(-num)
            elif sign == '*':
                stack.append(stack.pop() * num)
            elif sign == '/':
                stack.append(int(stack.pop() / num))
            sign = c
            num = 0
    return sum(stack)

这个解法巧妙地处理了运算符优先级问题——遇到乘除立即计算，加减则暂存栈中。类似的思路还可以扩展到处理括号和更多运算符。

7. 面试实战建议

根据我参与过的50+场面试经验，栈队列类题目通常作为中等难度出现。面试官最关注的三个维度：

1. 能否快速识别题目本质（如括号匹配→栈，滑动窗口→队列）
2. 对边界条件的处理是否严谨（空输入、极端用例等）
3. 代码实现的简洁性和可读性

建议在面试前重点练习：

• 栈：20, 155, 394, 739
• 队列：225, 622, 641
• 综合应用：84, 239, 316

最后分享一个真实案例：某次面试中，候选人用O(n^2)暴力法解滑动窗口问题后，我提示"能用线性时间解决吗？"。他立即反应过来："可以用单调队列！"——这种快速建立问题与数据结构关联的能力，正是面试官最看重的。