栈(stack)

理解”栈”

典型的栈结构

后进先出,先进后出。

栈是一种“操作受限”的线性表,只允许在一端插入和删除数据。

栈看起来可以使用数组或者链表替代,而且本身还有限制,那么使用栈的理由是什么呢?
因为自身的限制我们可以避免过分灵活带来的错误。

使用栈的条件

当某个数据集合只涉及在一端插入和删除数据,并且满足后进先出、先进后出的特性,我们就应该首选栈这种数据结构。

实现”栈”

  • 数组实现:顺序栈
  • 链表实现:链式栈

栈在函数中的应用

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

栈在表达式求值中的应用

使用两个栈:

  • 保存操作数的栈
  • 保存运算符的栈

从左到右遍历表达式,当遇到数字,我们直接压入操作数栈;
当遇到运算符,就与运算符栈的栈顶元素进行比较:

  • 如果比栈顶元素优先级高,就将运算符压入栈;
  • 如果比栈顶元素优先级低或者相同,则从运算符栈取出栈顶运算符,从操作数栈取两个操作数,然后进行计算,再把计算结果压入操作数栈,然后继续。

栈在括号匹配中的应用

比如,{[{}]}或 [{()}([])] 等都为合法格式,而{[}()] 或 [({)] 为不合法的格式。

用一个栈来保存未匹配的左括号
从左到右依次扫描字符串,当扫描到左括号时,则将其压入栈中;当扫描到右括号时,则从栈顶取出一个左括号。

非法的3种情况:

  • 如果过程中右括号无法匹配左括号
  • 或者栈中没有数据
  • 扫描完成后栈不为空

日常接触的典型栈结构

  • 浏览器的前进后退功能
  • 手机APP的页面和小程序的页面转场

在学习了栈结构之后,我尤其对括号匹配这个应用印象深刻,之前很难想到如何来实现这个功能,现在真的是一目了然了。

加载评论框需要科学上网