+
+
Posts List
  1. 栈的概念
  2. 栈的实现
  3. 栈在函数调用中的应用
  4. 栈在表达式求值中的应用
  5. 栈在括号匹配中的应用
  6. 栈在浏览器前进后退按钮中的应用
  7. 课后思考

数据结构与算法之美:栈

栈的概念

后进者先出,先进者后出,这就是典型栈的结构。

从栈的操作特性上来看,栈是一种操作受限的线性表,只允许在一端插入和删除数据。

从表面开看,栈带给我们的只有限制,相比数组或链表没有任何优势,那栈的存在意义是什么呢?

的确,从功能上讲,数组和链表可以取代栈,但特定的数据结构是对特定的使用场景的抽象,而且,数组和链表暴露了太多的操作接口,使用时比较不可控。

当某个数据集合只涉及在一端插入和删除元素,并且满足LIFO的特性,栈就派上用场了。

栈的实现

用数组实现的栈叫做顺序栈,用链表实现的栈叫做链式栈。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//顺序栈
class ArrayStack{
this.items = [];
this.count = 0;

push(element){
this.items.push(element);
this.count++;
}

pop(){
return this.items.pop();
count--;
}

不管是顺序栈还是链式栈,存储数据只需要一个数组就够了,在入栈和出栈过程中,最多只需要一两个临时变量存储空间,所以空间复杂度是$O(1)$。

注意,我们说空间复杂度的时候,是指除了原本的数据存储外,算法运行还需要的额外的存储空间。

由于出入栈都只涉及栈顶元素,所以时间复杂度也为$O(1)$。

在C语言等在声明数组时需要确定数组容量的语言中,要实现一个支持动态扩容的栈,需要底层依赖一个支持动态扩容的数组。当栈满了后申请一个更大的数组,将原来的数据搬移到新的数组中。

对于出栈操作来说,动态扩容的栈的时间复杂度仍为$O(1)$,但入栈操作在空间不足时,由于涉及了内存申请和数据搬移,时间复杂度变为$O(n)$。利用摊还分析法,得到均摊时间复杂度仍为$O(1)$。

栈在函数调用中的应用

栈这个概念一个经典的应用场景就是函数调用栈。

操作系统给每个线程分配了一块独立的内存空间,这块内存被组织成栈这种结构,用来存储函数调用时的临时变量。每进入一个函数,就会将临时变量作为一个「栈帧」入栈。

以下面一段代码为例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int main() {
int a = 1;
int ret = 0;
int res = 0;
ret = add(3, 5);
res = a + ret;
printf("%d", res);
return 0;
}

int add(int x, int y) {
int sum = 0;
sum = x + y;
return sum;
}

我们在main函数里调用了add函数,函数调用栈如图:

栈在表达式求值中的应用

对于一个算数表达式,比如:$3+5\times8-6$,计算机是如何求解的呢?

实际上,计算机通过两个栈实现,其中一个保存操作数,一个保存运算符。计算机从左向右遍历表达式,当遇到数字,就压入操作数栈;当遇到运算符,就与运算符栈的栈顶运算符进行优先级比较。如果当前运算符比栈顶运算符优先级高,就将当前运算符压入栈;否则,取出栈顶运算符和操作数栈顶部的2个操作数进行计算,将结果压入操作数栈,再将运算符压入运算符栈。

栈在括号匹配中的应用

栈的另一个应用场景,就是检查表达式中的括号是否匹配。只需要用一个栈保存未匹配的左括号,当扫描到右括号时,pop出栈顶元素进行匹配检查,如果匹配则继续扫描,如果不匹配或栈中没有数据则表示表达式非法。

一次扫描下来,如果栈为空,表明字符串合法。

栈在浏览器前进后退按钮中的应用

使用两个栈XY,每浏览一个新页面时,就把前一个页面压入X,点击后退按钮时,将当前页面存入Y,并从X中pop出栈顶页面浏览。当点击前进按钮时,就将当前页面存入X,并从Y中pop出栈顶页面浏览。

XY中没有元素时,则表示没有页面可以前进/后退了。

王争老师在课程中没有对当前浏览页面作出区分,直接将当前浏览的页面压入了X,所以我将我所理解的前进后退压栈过程重绘了一遍。

草稿纸-205

草稿纸-206

草稿纸-207

草稿纸-208

草稿纸-209

草稿纸-210

课后思考

  1. 为什么函数调用要用「栈」来保存临时变量呢?其他数据结构不行吗?

    因为函数调用这个情景符合栈LIFO的特点,所以使用栈。也可以使用其他数据结构,但是就有杀鸡用牛刀的嫌疑了。

  2. JVM内存管理中有个「堆栈」的概念,栈内存用来存储局部变量和方法调用,堆内存用来存储Java中的对象。那Java中的「栈」和我们这里说的「栈」是一回事吗?

    不是一回事。内存中的栈是一段虚拟的内存空间,数据结构中的栈是一种抽象的数据类型,但是它们都符合LIFO的特性。

本文作者: rhinoc

本文链接: https://www.rhinoc.top/cid216_6/

版权声明: 本博客所有文章除特别声明外,均采用BY-NC-SA 4.0国际许可协议,转载请注明。

打赏
Love U 3000
  • Through WeChat
  • Through Alipay