总结
栈是「后进先出」的线性表,概念简单到几乎不用解释,但它的三种经典应用——括号匹配、表达式求值、函数调用——才是它在实际系统中的价值所在。术语对照表把顺序栈、链式栈、共享栈的说法对齐到英文,核心要点列出复杂度、溢出判断,以及「判断出栈序列是否合法」这一常考题型的解法。
| 中文术语 | 英文术语 | 说明 |
|---|---|---|
| 栈 | Stack | 后进先出的线性表 |
| 栈顶 | Top | 允许插入删除的一端 |
| 栈底 | Bottom | 栈的固定端 |
| 入栈 | Push | 在栈顶插入元素 |
| 出栈 | Pop | 删除栈顶元素 |
| 顺序栈 | Sequential Stack | 用数组实现的栈 |
| 链式栈 | Linked Stack | 用链表实现的栈 |
| 共享栈 | Shared Stack | 两个栈共享一个数组空间 |
| 后进先出 | LIFO | Last In First Out |
- 栈的所有基本操作(入栈、出栈、取栈顶)时间复杂度均为
- 顺序栈需防栈满溢出,链式栈不会栈满
- 括号匹配、表达式求值、函数调用是栈的三大经典应用
- 判断出栈序列合法性是常考题型,可用栈模拟验证
