栈是什么?

堆栈(英语:stack)又称为栈或堆叠,是计算机科学中的一种抽象数据类型,只允许在有序的线性数据集合的一端(称为堆栈顶端,英语:top)进行加入数据(英语:push)和移除数据(英语:pop)的运算。因而按照后进先出(LIFO, Last In First Out)的原理运作。

bg2013112901.png

在这种数据结构中,数据像积木那样一层层堆起来,后面加入的数据就放在最上层。使用的时候,最上层的数据第一个被用掉,这就叫做"后进先出"。

堆栈使用两种基本操作:推入(压栈,push)和弹出(弹栈,pop):

推入:将数据放入堆栈顶端,堆栈顶端移到新放入的数据。

弹出:将堆栈顶端数据移除,堆栈顶端移到移除后的下一笔数据。

堆栈的基本特点:

  • 先入后出,后入先出

  • 除头尾节点之外,每个元素有一个前驱,一个后继。

通俗来讲:我们平时放盘子的时候,都是从下往上一个一个放;取的时候,我们也是从上往下一个一个地依次取,不能从中间任意抽出。

堆栈的实现

堆栈可以用数组和链表两种方式实现,一般为一个堆栈预先分配一个大小固定且较合适的空间并非难事,所以较流行的做法是Stack结构下含一个数组。如果空间实在紧张,也可用链表实现,且去掉表头。

栈在表达式求值中的应用

利用栈(stack)计算加减乘除四则运算,比如34+13*9+44-12/3。

计算流程

  • 新建x,y两个空栈,x存储数字,y存储运算符号

  • 从左到右遍历表达式,遇到数字时,直接push到x栈;

  • 遇到运算符,和y栈的栈顶元素进行比较。

    • 如果y栈栈顶元素为空,直接压入栈,

    • 如果比y栈栈顶元素的优先级高,直接压入栈,

    • 如果比y栈栈顶低或者相同,从y栈取栈顶运算符,从x栈的栈顶取2个操作数,然后进行计算,把计算完的结果压入到x栈,继续比较。

download.jpg

栈在括号匹配中的应用

除了用栈来实现表达式求值,我们还可以借助栈来检查表达式中的括号是否匹配。

我们同样简化一下背景。我们假设表达式中只包含三种括号,圆括号 ()、方括号 [] 和花括号{},并且它们可以任意嵌套。如:

  • {[{}]}或 [{()}([])] 等都为合法格式

  • {[}()] 或 [({)] 为不合法的格式。

那我现在给你一个包含三种括号的表达式字符串,如何检查它是否合法呢?

使用栈解决方法:

  •  新建一个空栈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

本文地址: http://chenxm.cc/article/965.html
版权声明: 本文为原创文章,版权归  陈新明  所有,欢迎分享本文,转载请保留出处!
上一篇: python2安装gunicorn提示ERROR: Package 'gunicorn' requires a different Python: 2.7.12 not in '>=3.4'
下一篇: 谷歌验证码 reCAPTCHA 识别
发表评论
  1. python
    python  @回复

    谢谢分享

  2. 缝纫机
    缝纫机  @回复

    不错好想法,高手