栈
概述
栈 是一种遵循 后进先出（LIFO） 原则 的线性数据结构，类似于现实中的一摞盘子或书籍。
提示
想象一下，我们把盘子从上到下依次摆放在桌子上，当我们要用到盘子时，就从最上面取走一个盘子， 放回盘子时，则是把盘子放在最上面。
核心特性
- 后进先出（LIFO）：最后添加的元素最先被移除
- 单端操作：所有操作（插入/删除/访问）仅在栈顶（Top）进行
时间复杂度
- 压栈（Push）: O(1)
- 弹栈（Pop）: O(1)
- 查看栈顶（Peek）: O(1)
栈的实现
使用数组模拟栈
class ArrayStack<T> {
private items: T[]
constructor() {
this.items = []
}
// 压栈
push(element: T): void {
this.items.push(element)
}
// 弹栈
pop(): T | undefined {
return this.items.pop()
}
// 查看栈顶元素
peek(): T | undefined {
return this.items[this.items.length - 1]
}
// 判断空栈
isEmpty(): boolean {
return this.items.length === 0
}
// 获取栈大小
size(): number {
return this.items.length
}
// 清空栈
clear(): void {
this.items = []
}
// 打印栈内容
print(): string {
return this.items.toString()
}
}使用链表模拟栈
class LinkedNode<T> {
constructor(
public value: T,
public next: LinkedNode<T> | null = null
) {}
}
class LinkedListStack<T> {
private top: LinkedNode<T> | null = null
private count: number = 0
push(element: T): void {
const newNode = new LinkedNode(element)
newNode.next = this.top
this.top = newNode
this.count++
}
pop(): T | undefined {
if (!this.top)
return undefined
const value = this.top.value
this.top = this.top.next
this.count--
return value
}
peek(): T | undefined {
return this.top?.value
}
isEmpty(): boolean {
return this.count === 0
}
size(): number {
return this.count
}
clear(): void {
this.top = null
this.count = 0
}
}应用场景
- 函数调用栈（程序执行上下文管理）
- 括号匹配校验（编译器语法检查）
- 撤销操作（Undo）（编辑器历史记录）
- 深度优先搜索（DFS）（图遍历算法）
- 表达式求值（中缀转后缀表达式）
- 浏览器历史记录（前进/后退功能）
重要
掌握 栈 的关键在于理解其 LIFO 特性 和 受限的操作方式， 这种特性使其在需要"撤销"或"回溯"的场景中具有天然优势。