漫漫前端路之数据结构与算法基础IV——栈篇

语言: CN / TW / HK
时间 2022-04-09 03:16:15

线性表之栈

栈结构

后进者先出，先进者后出，这就是典型的“栈”结构。 image.png 栈是一种“操作受限”的线性表，只允许在一端插入和删除数据。

实现栈

数组实现的顺序栈

```java // 基于数组实现的顺序栈 public class ArrayStack { private String[] items; // 数组 private int count; // 栈中元素个数 private int n; //栈的大小

// 初始化数组，申请一个大小为n的数组空间 public ArrayStack(int n) { this.items = new String[n]; this.n = n; this.count = 0; }

// 入栈操作 public boolean push(String item) { // 数组空间不够了，直接返回false，入栈失败。 if (count == n) return false; // 将item放到下标为count的位置，并且count加一 items[count] = item; ++count; return true; }

// 出栈操作 public String pop() { // 栈为空，则直接返回null if (count == 0) return null; // 返回下标为count-1的数组元素，并且栈中元素个数count减一 String tmp = items[count-1]; --count; return tmp; } } ``` 数组的储存空间是必须的，无法省掉，入栈和出栈的空间与时间复杂度O(1)。

链表实现的链式栈

支持动态扩容的顺序栈

如果要实现一个支持动态扩容的栈，只需要底层依赖一个支持动态扩容的数组就可以了。当栈满了之后，就申请一个更大的数组，将原来的数据搬移到新数组中。 image.png 出栈的时间复杂度仍然是 O(1)。入栈时，当栈中有空闲空间时，入栈操作的时间复杂度为 O(1)。但当空间不够时，就需要重新申请内存和数据搬移，所以时间复杂度就变成了 O(n)。

改进：如果当前栈大小为 K，并且已满，当再有新的数据要入栈时，就需要重新申请 2 倍大小的内存，并且做 K 个数据的搬移操作，然后再入栈。但是，接下来的 K-1 次入栈操作，我们都不需要再重新申请内存和搬移数据，所以这 K-1 次入栈操作都只需要一个 simple-push 操作就可以完成。 image.png 因为在大部分情况下，入栈操作的时间复杂度 O 都是 O(1)，只有在个别时刻才会退化为 O(n)，所以把耗时多的入栈操作的时间均摊到其他入栈操作上，平均情况下的耗时就接近 O(1)。

栈应用

函数调用时

```c int main() { int a = 1; int ret = 0; int res = 0; ret = add(3, 5); res = a + ret; printf("%d", res); reuturn 0; }

int add(int x, int y) { int sum = 0; sum = x + y; return sum; } ``` image.png

表达式中

其中一个保存操作数的栈，另一个是保存运算符的栈。我们从左向右遍历表达式，当遇到数字，我们就直接压入操作数栈；当遇到运算符，就与运算符栈的栈顶元素进行比较。

如果比运算符栈顶元素的优先级高，就将当前运算符压入栈；如果比运算符栈顶元素的优先级低或者相同，从运算符栈中取栈顶运算符，从操作数栈的栈顶取 2 个操作数，然后进行计算，再把计算完的结果压入操作数栈，继续比较。 image.png

括号匹配时

我们用栈来保存未匹配的左括号，从左到右依次扫描字符串。当扫描到左括号时，则将其压入栈中；当扫描到右括号时，从栈顶取出一个左括号。如果能够匹配，比如“(”跟“)”匹配，“[”跟“]”匹配，“{”跟“}”匹配，则继续扫描剩下的字符串。如果扫描的过程中，遇到不能配对的右括号，或者栈中没有数据，则说明为非法格式。当所有的括号都扫描完成之后，如果栈为空，则说明字符串为合法格式；否则，说明有未匹配的左括号，为非法格式。

实现浏览器的后退、前进

我们使用两个栈，X 和 Y，我们把首次浏览的页面依次压入栈 X，当点击后退按钮时，再依次从栈 X 中出栈，并将出栈的数据依次放入栈 Y。当我们点击前进按钮时，我们依次从栈 Y 中取出数据，放入栈 X 中。当栈 X 中没有数据时，那就说明没有页面可以继续后退浏览了。当栈 Y 中没有数据，那就说明没有页面可以点击前进按钮浏览了。 - 实例： 1. 打开a,b,c三个页面 image.png 2. c后退到a页面 image.png 3. 前进到b页面 image.png

思考

在讲栈的应用时，讲到用函数调用栈来保存临时变量，为什么函数调用要用“栈”来保存临时变量呢？用其他数据结构不行吗？ - 因为函数调用的执行顺序符合后进者先出，先进者后出的特点。比如函数中的局部变量的生命周期的长短是先定义的生命周期长，后定义的生命周期短；还有函数中调用函数也是这样，先开始执行的函数只有等到内部调用的其他函数执行完毕，该函数才能执行结束。正是由于函数调用的这些特点，根据数据结构是特定应用场景的抽象的原则，我们优先考虑栈结构。

资料来源

https://time.geekbang.org/column/article/41222

「」