栈是什么?
堆栈(英语:stack)又称为栈或堆叠,是计算机科学中的一种抽象数据类型,只允许在有序的线性数据集合的一端(称为堆栈顶端,英语:top)进行加入数据(英语:push)和移除数据(英语:pop)的运算。因而按照后进先出(LIFO, Last In First Out)的原理运作。
在这种数据结构中,数据像积木那样一层层堆起来,后面加入的数据就放在最上层。使用的时候,最上层的数据第一个被用掉,这就叫做"后进先出"。
堆栈使用两种基本操作:推入(压栈,push)和弹出(弹栈,pop):
推入:将数据放入堆栈顶端,堆栈顶端移到新放入的数据。
弹出:将堆栈顶端数据移除,堆栈顶端移到移除后的下一笔数据。
堆栈的基本特点:
先入后出,后入先出。
除头尾节点之外,每个元素有一个前驱,一个后继。
通俗来讲:我们平时放盘子的时候,都是从下往上一个一个放;取的时候,我们也是从上往下一个一个地依次取,不能从中间任意抽出。
堆栈的实现
堆栈可以用数组和链表两种方式实现,一般为一个堆栈预先分配一个大小固定且较合适的空间并非难事,所以较流行的做法是Stack结构下含一个数组。如果空间实在紧张,也可用链表实现,且去掉表头。
栈在表达式求值中的应用
利用栈(stack)计算加减乘除四则运算,比如34+13*9+44-12/3。
计算流程
新建x,y两个空栈,x存储数字,y存储运算符号
从左到右遍历表达式,遇到数字时,直接push到x栈;
遇到运算符,和y栈的栈顶元素进行比较。
如果y栈栈顶元素为空,直接压入栈,
如果比y栈栈顶元素的优先级高,直接压入栈,
如果比y栈栈顶低或者相同,从y栈取栈顶运算符,从x栈的栈顶取2个操作数,然后进行计算,把计算完的结果压入到x栈,继续比较。
栈在括号匹配中的应用
除了用栈来实现表达式求值,我们还可以借助栈来检查表达式中的括号是否匹配。
我们同样简化一下背景。我们假设表达式中只包含三种括号,圆括号 ()、方括号 [] 和花括号{},并且它们可以任意嵌套。如:
{[{}]}或 [{()}([])] 等都为合法格式
{[}()] 或 [({)] 为不合法的格式。
那我现在给你一个包含三种括号的表达式字符串,如何检查它是否合法呢?
使用栈解决方法:
新建一个空栈x,保存未匹配的左括号(包括 [{( )
从左到右依次扫描字符串,当扫描到左括号时,则压入x栈中
当扫描到右括号时,从x栈顶去除一个左括号,进行判断,如果能够匹配,比如“(”跟“)”匹配,“[”跟“]”匹配,“{”跟“}”匹配,则继续扫描剩下的字符串。
在扫描过程中,遇到不能配对的括号,或者是x栈中没有数据,那么该数据为非法数据。
字符串扫描结束后,如果栈为空,则说明字符串为合法字符串;否则,说明有未匹配的左括号,为非法格式。
如何实现浏览器的前进和后退功能?
新建两个栈,x和y;x 负责存储打开过的网址,后退的网址,y负责存储点击前进时浏览的网址。
当浏览器浏览的网址依次压入栈x,当点击后退按钮时,依次从栈x出栈,同时并将出栈的数据依次放入栈y.
当我们点击前进按钮时,依次从栈Y中取出数据,同时放入栈x中。
当栈x没有数据时,代表页面没有可以继续后退浏览
当栈Y没有数据时,代表页面没有可以点击前进按钮浏览
leetcode上关于栈的题目
20,155,232,844,224,682,496.
参考:
https://www.ruanyifeng.com/blog/2013/11/stack.html
https://zh.wikipedia.org/zh-hans/%E5%A0%86%E6%A0%88
https://time.geekbang.org/column/article/41222
发表于 2020-01-16 17:28:11 1楼
谢谢分享
发表于 2020-06-02 09:32:37 2楼
不错好想法,高手