总结

栈是「后进先出」的线性表,概念简单到几乎不用解释,但它的三种经典应用——括号匹配、表达式求值、函数调用——才是它在实际系统中的价值所在。术语对照表把顺序栈、链式栈、共享栈的说法对齐到英文,核心要点列出复杂度、溢出判断,以及「判断出栈序列是否合法」这一常考题型的解法。

术语对照表

中文术语英文术语说明
栈Stack后进先出的线性表
栈顶Top允许插入删除的一端
栈底Bottom栈的固定端
入栈Push在栈顶插入元素
出栈Pop删除栈顶元素
顺序栈Sequential Stack用数组实现的栈
链式栈Linked Stack用链表实现的栈
共享栈Shared Stack两个栈共享一个数组空间
后进先出LIFOLast In First Out

核心要点

  • 栈的所有基本操作(入栈、出栈、取栈顶)时间复杂度均为 O(1)O(1)
  • 顺序栈需防栈满溢出,链式栈不会栈满
  • 括号匹配、表达式求值、函数调用是栈的三大经典应用
  • 判断出栈序列合法性是常考题型,可用栈模拟验证

发现内容有问题?

告诉我们哪里需要改进。