数据结构与算法-栈

后进者先出,先进者后出,这就是“栈”结构,支持的最基本操作是入栈push()和出栈pop()。示意图如下:

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

栈的实现

用数组实现的栈,叫做顺序栈,用链表实现的栈,叫做链式栈。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),时间复杂度是O(1)。

支持动态扩容的顺序栈

上面通过数组实现的栈,是一个固定大小的栈,即栈满之后,无法再添加数据,尽管链式栈的大小不受限,但是要存储next指针,内存消耗也更多。

要实现一个支持动态扩容的栈,只需要底层依赖一个支持动态扩容的数组就可以了。当栈满了之后,我们就申请一个更大的数组,将原来的数据搬移到新数组中,示意图如下:

支持动态扩容的栈,实际上平时开发中并不常用到。出栈的时间复杂度都是O(1),入栈的时间复杂度最好是o(1),最坏是O(n),均摊时间复杂度是O(1)。

均摊时间复杂度一般都等于最好情况时间复杂度。因为在大多数情况下,入栈的时间复杂度都是O(1),只有在个别时刻才会退化为O(n),所以把耗时多的入栈操作的时间均摊到其他入栈操作上,平均情况下的耗时就接近O(1)。

栈在函数调用中的应用

操作系统个每个线程分配了一块独立的内存空间,这块内存被组织成“栈”这种结构,用来存储函数调用时的临时变量。

栈在表达式求值中的应用

编译器通过两个栈来实现,其中一个保存操作数的栈,另一个保存运算符的栈。从左到右遍历表达式,遇到数字,就直接压入操作数栈;当遇到运算符,就与运算符栈的栈顶元素优先级进行比较:

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

栈在括号匹配中的应用

利用栈来检查表达式中的括号是否匹配。用栈来保存未匹配的左括号,从左到右依次扫描字符串,当扫描到左括号时,则将其压入栈中;当扫描到右括号时,从栈顶取出一个左括号,如果能够匹配:

  • ”(” 对应 “)”
  • ”{” 对应 “}”
  • “[” 对应 “]”

则继续扫描剩下的字符串,如果扫描过程中不匹配,或者栈中没有数据,则说明为非法格式。扫描完之后,查看栈是否为空,是空说明字符串合法,反之,不合法。

如何利用实现浏览器的前进和后退功能

利用两个栈,X和Y,把首次浏览的页面依次压入栈X,当点击后退按钮时,再依次从X中出栈,并将出栈的数据压入栈Y。当我们点击前进按钮时,依次从栈Y中取出数据,放入栈X中。当栈X中没有数据时,说明页面不可以继续后退了,当栈Y中没有数据时,说明不能继续前进了。如果没有点击后退按钮,而是进入其他新的页面,那么栈Y的元素需要清空,表示无法通过前进达到栈Y中的页面。

操作系统堆栈 VS 数据结构中的“栈”

内存中的堆栈和数据结构堆栈不是一个概念,可以说内存中的堆栈是真实存在的物理区,数据结构中的堆栈是抽象的数据存储结构。

内存空间在逻辑上分为三部分:代码区、静态数据区和动态数据区,动态数据区又分为栈区和堆区。

  • 代码区:存储方法体的二进制代码。高级调度(作业调度)、中级调度(内存调度)、低级调度(进程调度)控制代码区执行代码的切换
  • 静态数据区:存储全局变量、静态变量、常量,常量包括final修饰的常量和String常量。系统自动分配和回收
  • 栈区:存储运行方法的形参、局部变量、返回值。由系统自动分配和回收
  • 堆区:new一个对象的引用或地址存储在栈区,指向该对象存储在堆区中的真实数据

注:本文是《数据结构与算法之美》的读书笔记,配套代码地址GitHub。本文仅限个人学习,请勿用作商业用途,谢谢。

Note: Cover Picture