概念及特点
一种“操作受限“的线性表数据结构,具有先进后出、后进先出的特点,只能在栈顶插入和删除元素。
实现方式
数组实现(顺序栈)
- 时间复杂度分析:根据均摊复杂度的定义,可以得到数组实现(自动扩容)符合大多数情况是O(1)级别复杂度,个别情况是O(n)级别复杂度,比如自动扩容,会进行全量数据的拷贝。
- 空间复杂度分析:在入栈和出栈的过程中,只需要一两个临时变量的存储空间,所以是O(1)级别。
链表实现(链式栈)
- 时间复杂度分析:入栈和出栈都是O(1)级别,对应单链表头节点的插入和删除操作。
- 空间复杂度分析:在入栈和出栈的过程中,只需要一两个临时变量的存储空间,所以是O(1)级别。
常见应用
在函数调用中的应用
操作系统给每个线程分配了一块独立的内存空间,这块内存被组织成“栈”这种结构,用来存储函数调用时的临时变量。每进入一个函数,就会将其中的临时变量作为栈帧入栈,当被调用函数执行完成,返回之后,将这个函数对应的栈帧出栈。
在表达式求值中的应用
利用两个栈,其中一个用来保存操作数,另一个用来保存运算符。我们从左向右遍历表达式,当遇到数字,我们就直接压入操作数栈;当遇到运算符,就与运算符栈的栈顶元素进行比较,若比运算符栈顶元素优先级高,就将当前运算符压入栈,若比运算符栈顶元素的优先级低或者相同,从运算符栈中取出栈顶运算符,从操作数栈顶取出2个操作数,然后进行计算,把计算完的结果压入操作数栈,继续比较。
在括号匹配中的应用
用栈保存为匹配的左括号,从左到右依次扫描字符串,当扫描到左括号时,则将其压入栈中;当扫描到右括号时,从栈顶取出一个左括号,如果能匹配上,则继续扫描剩下的字符串。如果扫描过程中,遇到不能配对的右括号,或者栈中没有数据,则说明为非法格式。当所有的括号都扫描完成之后,如果栈为空,则说明字符串为合法格式;否则,说明未匹配的左括号为非法格式。
实现浏览器的前进后退功能
我们使用两个栈X和Y,我们把首次浏览的页面依次压入栈X,当点击后退按钮时,再依次从栈X中出栈,并将出栈的数据依次放入Y栈。当点击前进按钮时,我们依次从栈Y中取出数据,放入栈X中。当栈X中没有数据时,说明没有页面可以继续后退浏览了。当Y栈没有数据,那就说明没有页面可以点击前进浏览了。
leetcode练习题
题号 | 代码实现 |
---|---|
20 | 有效的括号 |
155 | 最小栈 |
232 | 用栈实现队列 |
844 | 比较含退格的字符串 |
224 | 基本计算器 |
682 | 棒球比赛 |
496 | 下一个更大元素 I |