栈：如何实现浏览器的前进和后退功能？

栈这个数据结构，比较常见了，先进后出。压栈弹栈什么的。
从栈的操作特性上来看，栈是一种 操作受限 的线性表

那么既然有了数组和链表，栈存在的意义又是什么呢？

image

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

一、如何实现一个栈？

栈既可以用 数组 来实现，也可以用 链表 来实现。用数组实现的栈，叫做 顺序栈，用链表实现的栈，叫做 链式栈。

下面是一个基于数组的 顺序栈：

// 基于数组实现的顺序栈
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;
  }
}

上述代码实现的栈，入栈出栈的复杂度是多少呢？
不管入栈还是出栈，所消耗时间都是常量时间，所以时间复杂度为 ○(1)。
不管入栈还是出栈，只需要几个临时变量即可完成，所以空间复杂度为 ○(1)。

二、支持动态扩容的顺序栈

对于 一 中的栈，是一个固定大小的栈（在初始化栈时，需要事先指定栈的大小）。当栈满之后，无法继续添加数据。

那么如果使用链表来实现栈（链式栈），每个元素都需要多存储一个后继指针 next（若使用双向链表，则还要多存一个前驱指针 prev），这样内存的消耗会多一些。

如何实现一个基于数组的支持动态扩容的栈呢？当数组空间不够时，我们就重新申请一块更大的内存，将原来数组中数据 copy 过去（ArrayList的原理）即可。

image

这种栈实际中很少用到，主要是用来回顾一下，时间复杂度分析过程。
时间复杂度：

• 最好情况，不需要扩容，为 ○(1)
• 最坏情况，需要扩容，为 ○(n)
• 在求加权平均时间复杂度前，一定要先观察从最好情况到最坏情况是否符合摊还分析法的规律
• 可以发现，每次将数组填满（n 个 ○(1)）后，都会执行一次扩容 ○(n)
• 所以是符合摊还分析法的，那么就简单了，将 ○(n) 平摊到 ○(1) 上
• 那么最终，上述支持扩容的顺序栈的时间复杂度就为：○(1)

三、栈的一些应用场景

1. 在函数中的应用

一个比较经典的应用场景：函数调用栈（几年前我还没毕业，看毕向东老师的java视频中就画过这个应用场景，记忆犹新啊）

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

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

2. 栈在表达式求值中的应用

下面来看看编译器是如何利用栈来实现表达式求值的。
这里讲算术表达式简化为只含有加减乘除四则运算：34+13*9+44-12/3
编译器是通过两个栈来实现的。一个保持操作数的栈，另一个是保持运算符的栈。
从左向右遍历表达式，当遇到数字，就压入操作数栈，遇到运算符，就与运算符栈顶的元素进行比较：

• 比栈顶元素优先级高，就将当前运算符压入栈；
• 比栈顶元素优先级低或相同，从运算符栈中取出栈顶运算符，从操作数栈的栈顶开始，取两个元素配上运算符，进行计算，再将计算完的结果压入操作数栈。
• 继续遍历比较

image

3. 栈在括号匹配中的应用

image

4. 如何实现浏览器的前进、后退功能？

image

四、思考

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

用其他数据结构也可以，不一定非要用栈来保存临时变量。
但是因为函数调用符合先进后出的特性，用栈这种数据结构来实现是非常契合的。

从正在调用的函数a()中，调用了函数b()，对于数据来讲，只有作用域发生了变化（原来在a()中使用，变为了在b()中使用）。所以只要能保证数据每次进入一个新的函数，都是一个新的作用域就可以，要实现这个，用栈很方便。

在进入被调用函数 b() 的时候，分配一段栈空间给这个函数的变量，在函数结束时，将栈顶复位（弹出 b() 中的临时变量），此时正好回到 a() 函数的作用域内。

2. JVM 内存管理中有个 堆栈 的概念。栈内存用来存储局部变量和方法调用，堆内存用来存储 Java 中的对象。那 JVM 里面的 栈 跟我们这里说的 栈 是不是一回事呢？如果不是，那它为什么又叫做栈呢？

首先，内存中的堆栈和数据结构堆栈不是一个概念，内存中的堆栈是真实存在的物理区，数据结构中的堆栈是抽象的数据存储结构。（在内存中真实被划分出堆栈的区域）

内存空间在逻辑上分位三部分：代码区 静态数据区 动态数据区
动态数据区又被分位 栈区 堆区

• 静态数据区：存储 全局变量 静态变量 常量 常量 包括 final 修饰的常量和 String 常量。系统自动分配和回收。
• 栈区：存储运行方法的 形参 局部变量 返回值 。由系统自动分配和回收。
• 堆区：new 一个对象的引用或地址存储在栈区，指向该对象存储在堆区中的真实数据。