数据结构与算法之美-栈

概念及特点

一种“操作受限“的线性表数据结构，具有先进后出、后进先出的特点，只能在栈顶插入和删除元素。

实现方式

数组实现（顺序栈）

• 时间复杂度分析：根据均摊复杂度的定义，可以得到数组实现（自动扩容）符合大多数情况是O(1)级别复杂度，个别情况是O(n)级别复杂度，比如自动扩容，会进行全量数据的拷贝。
• 空间复杂度分析：在入栈和出栈的过程中，只需要一两个临时变量的存储空间，所以是O(1)级别。

链表实现（链式栈）

• 时间复杂度分析：入栈和出栈都是O(1)级别，对应单链表头节点的插入和删除操作。
• 空间复杂度分析：在入栈和出栈的过程中，只需要一两个临时变量的存储空间，所以是O(1)级别。

常见应用

在函数调用中的应用

操作系统给每个线程分配了一块独立的内存空间,这块内存被组织成“栈”这种结构,用来存储函数调用时的临时变量。每进入一个函数,就会将其中的临时变量作为栈帧入栈,当被调用函数执行完成,返回之后,将这个函数对应的栈帧出栈。

在表达式求值中的应用

利用两个栈,其中一个用来保存操作数,另一个用来保存运算符。我们从左向右遍历表达式,当遇到数字,我们就直接压入操作数栈;当遇到运算符,就与运算符栈的栈顶元素进行比较,若比运算符栈顶元素优先级高,就将当前运算符压入栈,若比运算符栈顶元素的优先级低或者相同,从运算符栈中取出栈顶运算符,从操作数栈顶取出2个操作数,然后进行计算,把计算完的结果压入操作数栈,继续比较。

在括号匹配中的应用

用栈保存为匹配的左括号,从左到右依次扫描字符串,当扫描到左括号时,则将其压入栈中;当扫描到右括号时,从栈顶取出一个左括号,如果能匹配上,则继续扫描剩下的字符串。如果扫描过程中,遇到不能配对的右括号,或者栈中没有数据,则说明为非法格式。当所有的括号都扫描完成之后,如果栈为空,则说明字符串为合法格式;否则,说明未匹配的左括号为非法格式。

实现浏览器的前进后退功能

我们使用两个栈X和Y,我们把首次浏览的页面依次压入栈X,当点击后退按钮时,再依次从栈X中出栈,并将出栈的数据依次放入Y栈。当点击前进按钮时,我们依次从栈Y中取出数据,放入栈X中。当栈X中没有数据时,说明没有页面可以继续后退浏览了。当Y栈没有数据,那就说明没有页面可以点击前进浏览了。

leetcode练习题