栈和队列深入
掌握栈(后进先出)和队列(先进先出):实现、应用和单调变体。
你将学到
- 后进先出与先进先出语义和用例
- 基于栈的算法:解析、回溯、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 等等。
动手做项目
通过引导式项目应用所学,含起始代码与解决方案。
解读错误信息
用大白话解释常见错误——什么意思、为什么发生、如何修复。