栈与队列
中等 约 30 分钟
你将构建什么
一个以数组为底、支持 push/pop/peek 的 Stack 类,以及一个使用 head/tail 指针对实现 O(1) 入队出队的 Queue 类。
学习目标
- 理解 LIFO(栈)与 FIFO(队列)的顺序差异
- 以正确的复杂度实现核心操作
- 使用数组作为内部存储
- 将栈应用于括号匹配检测
前置要求
- 数组与数组方法
- 类或构造函数
- if/else 条件语句
步骤
- 1
实现栈
栈是后进先出:最后压入的元素最先弹出。使用数组并在末尾 push/pop 即可实现 O(1) 操作。
代码class Stack { constructor() { this.items = []; } push(value) { this.items.push(value); return this; } pop() { return this.items.pop(); } peek() { return this.items[this.items.length - 1]; } isEmpty() { return this.items.length === 0; } size() { return this.items.length; } }预期结果
push(1).push(2).push(3); pop() 返回 3; peek() 返回 2。
- 2
测试栈
压入三个值再依次弹出,验证 LIFO 行为——弹出顺序应与压入顺序相反。
代码const s = new Stack(); s.push(1).push(2).push(3); console.log(s.pop()); // 3 console.log(s.pop()); // 2 console.log(s.pop()); // 1 console.log(s.isEmpty()); // true预期结果
输出:3、2、1、true。
- 3
实现队列
队列是先进先出。使用数组,push 用于入队,shift 用于出队。(注意:shift 为 O(n);生产环境队列会使用链表或 head/tail 指针。)
代码class Queue { constructor() { this.items = []; } enqueue(value) { this.items.push(value); return this; } dequeue() { return this.items.shift(); } front() { return this.items[0]; } isEmpty() { return this.items.length === 0; } size() { return this.items.length; } }预期结果
enqueue(1).enqueue(2).enqueue(3); dequeue() 返回 1。
- 4
测试队列
入队三个值再依次出队,验证 FIFO 行为——出队顺序应与入队顺序相同。
代码const q = new Queue(); q.enqueue('a').enqueue('b').enqueue('c'); console.log(q.dequeue()); // a console.log(q.dequeue()); // b console.log(q.dequeue()); // c预期结果
输出:a、b、c——与插入顺序相同。
- 5
应用:括号匹配检测
用栈检查一串括号是否平衡。遇到开括号压栈,遇到闭括号弹栈并验证是否匹配。
代码function isBalanced(str) { const stack = new Stack(); const pairs = { ')': '(', ']': '[', '}': '{' }; for (const ch of str) { if ('([{'.includes(ch)) stack.push(ch); else if (')]}'.includes(ch)) { if (stack.pop() !== pairs[ch]) return false; } } return stack.isEmpty(); } console.log(isBalanced('([{}])')); // true console.log(isBalanced('([)]')); // false预期结果
([{}]) 返回 true; ([)] 返回 false。
自己动手试试
起始代码
class Stack { constructor() { this.items = []; } /* TODO */ }
class Queue { constructor() { this.items = []; } /* TODO */ }解决方案代码
class Stack {
constructor() { this.items = []; }
push(v) { this.items.push(v); return this; }
pop() { return this.items.pop(); }
peek() { return this.items[this.items.length - 1]; }
isEmpty() { return this.items.length === 0; }
}
class Queue {
constructor() { this.items = []; }
enqueue(v) { this.items.push(v); return this; }
dequeue() { return this.items.shift(); }
isEmpty() { return this.items.length === 0; }
}你学到了什么
你实现了两种最常用的线性数据结构,并将栈应用于经典解析问题——栈是函数调用、撤销系统和表达式求值的基础。
相关资源
相关术语
新手友好的术语表用大白话解释编程术语——变量、函数、DOM、Promise 等等。
解读错误信息
用大白话解释常见错误——什么意思、为什么发生、如何修复。