栈与队列在LeetCode算法题中的核心应用解析-嵌云网-嵌入式AI开发资源站

栈与队列在LeetCode算法题中的核心应用解析

哈特瑞姆·2026-10-31·阅读 21 GEO检测（免费）

栈队列LeetCode

|难度：普通|阅读约 19 分钟

1. 栈与队列基础概念解析

在算法与数据结构的世界里，栈(Stack)和队列(Queue)是两种最基础也最重要的线性数据结构。它们看似简单，却在LeetCode题目和实际工程中有着广泛应用。理解它们的特性和差异，是算法入门的关键一步。

栈遵循LIFO(Last In First Out)原则，就像我们日常生活中叠放的盘子，最后放上去的盘子总是最先被取用。这种特性使得栈在解决需要"回退"或"撤销"操作的问题时特别有用，比如浏览器的后退功能、函数调用栈等。

队列则遵循FIFO(First In First Out)原则，类似于现实生活中的排队场景，先来的人先获得服务。这种特性让队列在处理需要按顺序执行的任务时非常高效，比如打印任务队列、消息队列等。

提示：虽然栈和队列的概念简单，但在实际应用中，它们的变体和组合能解决许多复杂问题。理解它们的本质特性比记忆具体实现更重要。

需要模型API调用？免费领10W Token，多模型网关一键接入 Claude、DeepSeek 等主流模型。

2. LeetCode中栈的典型应用场景

2.1 括号匹配问题

LeetCode第20题"有效的括号"是栈应用的经典案例。题目要求判断一个只包含括号字符的字符串是否有效，即各种括号是否能正确配对闭合。

解决思路很简单：遍历字符串，遇到左括号就压栈，遇到右括号就检查栈顶是否匹配。如果遍历结束后栈为空，说明所有括号都正确配对。这种解法的时间复杂度是O(n)，空间复杂度在最坏情况下也是O(n)。

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

2.2 单调栈的应用

单调栈是栈的一种特殊用法，它保持栈内元素单调递增或递减。这种结构在解决"下一个更大元素"这类问题时非常高效。

LeetCode第496题"下一个更大元素I"就是典型例子。我们需要为数组中的每个元素找到它右边第一个比它大的元素。使用单调递减栈可以在O(n)时间内解决这个问题：

python复制def nextGreaterElement(nums1, nums2):
    stack = []
    mapping = {}
    for num in nums2:
        while stack and num > stack[-1]:
            mapping[stack.pop()] = num
        stack.append(num)
    return [mapping.get(num, -1) for num in nums1]

3. 队列在算法题中的巧妙运用

3.1 滑动窗口问题

LeetCode第239题"滑动窗口最大值"展示了队列的高效应用。给定一个数组和滑动窗口的大小，需要找出每个窗口中的最大值。

暴力解法的时间复杂度是O(nk)，而使用双端队列(Deque)可以优化到O(n)。关键思路是维护一个可能成为窗口最大值的元素的索引队列：

python复制def maxSlidingWindow(nums, k):
    from collections import deque
    q = deque()
    result = []
    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:
            result.append(nums[q[0]])
    return result

3.2 广度优先搜索(BFS)

队列是广度优先搜索算法的核心数据结构。LeetCode中许多树和图的问题都需要使用BFS，比如第102题"二叉树的层序遍历"。

BFS使用队列来存储待访问的节点，确保按照层级顺序遍历：

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

4. 栈与队列的高级应用与变体

4.1 用栈实现队列和用队列实现栈

LeetCode第232题"用栈实现队列"和第225题"用队列实现栈"考察对这两种数据结构本质的理解。

用栈实现队列需要两个栈：一个用于输入，一个用于输出。当输出栈为空时，将输入栈的所有元素弹出并压入输出栈：

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

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

    def pop(self):
        self.peek()
        return self.out_stack.pop()

    def peek(self):
        if not self.out_stack:
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())
        return self.out_stack[-1]

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

用队列实现栈也有多种方法，最简单的是在每次push操作时重新排列队列元素：

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

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

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

    def top(self):
        return self.queue[0]

    def empty(self):
        return not self.queue

4.2 优先队列与堆

虽然严格来说优先队列(Priority Queue)不是基础队列，但它在LeetCode中经常出现。优先队列通常用堆(Heap)来实现，可以高效获取最大或最小元素。

LeetCode第23题"合并K个升序链表"就展示了优先队列的威力：

python复制def mergeKLists(lists):
    import heapq
    dummy = ListNode(0)
    curr = dummy
    heap = []
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))
    while heap:
        val, i, node = heapq.heappop(heap)
        curr.next = node
        curr = curr.next
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    return dummy.next

5. 栈与队列的常见错误与优化技巧

5.1 边界条件处理

在使用栈和队列时，最容易犯的错误是忽略边界条件。比如在弹出元素前没有检查栈/队列是否为空，或者在实现循环队列时没有正确处理满和空的判断条件。

注意：在实现任何栈或队列操作时，都要先考虑数据结构可能为空的情况，并做好相应处理。

5.2 空间复杂度优化

有些问题看似需要额外的栈或队列，但实际上可以通过巧妙的设计减少空间使用。例如，在判断回文链表时(LeetCode第234题)，可以只使用栈存储链表的前半部分：

python复制def isPalindrome(head):
    slow = fast = head
    stack = []
    while fast and fast.next:
        stack.append(slow.val)
        slow = slow.next
        fast = fast.next.next
    if fast:  # 链表长度为奇数
        slow = slow.next
    while slow:
        if slow.val != stack.pop():
            return False
        slow = slow.next
    return True

5.3 选择合适的数据结构

Python中list可以模拟栈和队列，但对于队列操作，list的pop(0)时间复杂度是O(n)。在需要高效队列操作时，应该使用collections.deque，它的popleft()和appendleft()操作都是O(1)时间复杂度。

同样，在需要优先队列时，Python的heapq模块比手动维护排序列表更高效。了解这些内置数据结构的特性可以显著提升代码性能。

6. 栈与队列的综合应用实例

6.1 表达式求值

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)

6.2 图的深度优先与广度优先遍历

虽然栈和队列在树遍历中的应用更为人熟知，但它们在图的遍历中同样重要。深度优先搜索(DFS)通常用栈实现(递归或显式栈)，而广度优先搜索(BFS)则用队列实现。

以LeetCode第133题"克隆图"为例，展示BFS和DFS两种实现：

python复制# BFS实现
def cloneGraph(node):
    from collections import deque
    if not node:
        return node
    visited = {}
    queue = deque([node])
    visited[node] = Node(node.val, [])
    while queue:
        n = queue.popleft()
        for neighbor in n.neighbors:
            if neighbor not in visited:
                visited[neighbor] = Node(neighbor.val, [])
                queue.append(neighbor)
            visited[n].neighbors.append(visited[neighbor])
    return visited[node]

# DFS实现(显式栈)
def cloneGraph(node):
    if not node:
        return node
    visited = {}
    stack = [node]
    visited[node] = Node(node.val, [])
    while stack:
        n = stack.pop()
        for neighbor in n.neighbors:
            if neighbor not in visited:
                visited[neighbor] = Node(neighbor.val, [])
                stack.append(neighbor)
            visited[n].neighbors.append(visited[neighbor])
    return visited[node]

7. 栈与队列的扩展学习建议

掌握了栈和队列的基础应用后，可以进一步学习以下高级主题：

双端队列(Deque)：结合了栈和队列的特性，两端都可以进行插入和删除操作。Python的collections.deque就是高效的双端队列实现。
单调队列：类似于单调栈，但可以从两端操作。在解决滑动窗口相关问题时特别有用。
循环队列：固定大小的队列，通过循环利用空间避免数据搬移。实现时需要注意判断队列满和空的条件。
多级反馈队列：操作系统调度算法中使用的复杂队列结构，结合了多种队列策略。
并发队列：线程安全的高效队列实现，如Python的queue.Queue，适用于多线程编程场景。

在实际工程中，栈和队列的应用远比算法题目中丰富。消息队列系统如Kafka、RabbitMQ，函数调用栈，浏览器历史记录管理，撤销操作实现等，都是这两种数据结构的典型应用场景。