Skip to content

栈和队列深入

掌握栈(后进先出)和队列(先进先出):实现、应用和单调变体。

你将学到

  • 后进先出与先进先出语义和用例
  • 基于栈的算法:解析、回溯、DFS
  • 基于队列的算法:BFS、调度
  • 下一个更大元素的单调栈

概念讲解

栈和队列深入

栈和队列是两种最基本的线性数据结构,以移除顺序区分。

栈(后进先出)

栈移除最近添加的元素(后进先出)。想象一叠盘子。栈适用于:函数调用管理(调用栈)、表达式解析(匹配括号)、撤销/重做、回溯算法和深度优先搜索。

队列(先进先出)

队列移除最旧的元素(先进先出)。想象商店排队。队列适用于:广度优先搜索、任务调度、缓冲(生产者-消费者)和层序遍历。

实现

两者都可用数组或链表实现。基于数组的栈最简单(在末尾 push/pop)。基于数组的队列需要循环缓冲区以避免 O(n) 移动。

单调栈

单调栈按有序顺序维护元素,支持高效的下一个更大元素查询。对每个元素,弹出栈中更小的元素(它们找到了下一个更大),然后压入当前元素。这以 O(n) 解决朴素 O(n^2) 的问题。

双端队列

双端队列(deque)允许两端插入和移除。它推广了栈和队列,是滑动窗口算法的骨干。

示例代码

              // Stack: balanced parentheses checker
function isBalanced(s) {
  const stack = [];
  const pairs = {')': '(', ']': '[', '}': '{'};
  for (const ch of s) {
    if ('([{'.includes(ch)) stack.push(ch);
    else if (')]}'.includes(ch)) { if (stack.pop() !== pairs[ch]) return false; }
  }
  return stack.length === 0;
}
// Monotonic stack: next greater element
function nextGreater(arr) {
  const result = new Array(arr.length).fill(-1);
  const stack = [];
  for (let i = 0; i < arr.length; i++) {
    while (stack.length && arr[stack[stack.length-1]] < arr[i]) result[stack.pop()] = arr[i];
    stack.push(i);
  }
  return result;
}
console.log(isBalanced('{[()]}'));
console.log(isBalanced('{[(])}'));
console.log(nextGreater([2, 1, 3, 5, 4]));
            

基于栈的解析器压入开括号,遇闭括号时弹出并检查匹配。单调栈弹出值小于当前的索引。

动手试一试

  • Code Minifier

    代码解析使用栈进行括号匹配和运算符优先级——观察其运作。

常见错误

错误写法

在基于数组的队列上使用 shift(),导致每次操作 O(n)。

正确做法

Array shift() 移动每个元素。使用循环缓冲区索引或链表实现 O(1) 出队。

错误写法

忘记检查栈下溢。

正确做法

对空栈调用 pop() 返回 undefined。弹出前总是检查长度。

查阅不认识的术语

新手友好的术语表用大白话解释编程术语——变量、函数、DOM、Promise 等等。

查看术语表

动手做项目

通过引导式项目应用所学,含起始代码与解决方案。

查看项目

解读错误信息

用大白话解释常见错误——什么意思、为什么发生、如何修复。

查看错误