数据结构与算法(5)-栈

  1. 1. 对栈的理解
  2. 2. 支持动态扩容的顺序栈
  3. 3. 栈的应用

大家都常用Chrome浏览器,你会发现在你做后退或者前进按钮时,浏览器的加载速度非常快,这里实际上是用的栈这个数据结构来进行处理的。

1. 对栈的理解

  • 先进后出
  • 操作受限的线性表,只允许在一端插入和删除数据
  • 实质上栈的功能一定是可以被数组(顺序栈)或者链表(链式栈)来替代的,因为有拿第一个和最后一个的接口,或者说方式
  • 用栈的好处是操作上的简单,更不容易出错一些
  • 功能操作受限的线性表,栈可以通过数组或者链表来进行实现

2. 支持动态扩容的顺序栈

  • 动态扩容 - load factor
  • 顺序栈 - 数组

fig1.jpg

  • 注意动态扩容的顺序栈,出栈过程依然可以实现O(1)的时间复杂度,但是在入栈过程当中,如果空间不够了的话,那就需要实现整体的迁移,时间复杂度就变成了O(n)
// 基于数组实现的顺序栈
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;
  }
}

3. 栈的应用

  • 函数调用栈
    • 操作系统给每个线程分配一块独立的内存空间,这块内存被组织成栈这种结构,用来存储函数调用时的临时变量
  • 表达式求值
    • 计算机会用两个栈来实现
    • 一个用来保存操作数
    • 一个用来保存运算符
      实际上,编译器就是通过两个栈来实现的。其中一个保存操作数的栈,另一个是保存运算符的栈。我们从左向右遍历表达式,当遇到数字,我们就直接压入操作数栈;当遇到运算符,就与运算符栈的栈顶元素进行比较。如果比运算符栈顶元素的优先级高,就将当前运算符压入栈;如果比运算符栈顶元素的优先级低或者相同,从运算符栈中取栈顶运算符,从操作数栈的栈顶取 2 个操作数,然后进行计算,再把计算完的结果压入操作数栈,继续比较。
      fig2.jpg

转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 stone2paul@gmail.com

文章标题:数据结构与算法(5)-栈

文章字数:715

本文作者:Leilei Chen

发布时间:2020-02-10, 01:44:43

最后更新:2020-02-10, 01:45:06

原始链接:https://www.llchen60.com/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95-5-%E6%A0%88/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

目录
×

喜欢就点赞,疼爱就打赏