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

数据结构与算法栈

创建时间:2020-02-10 01:44

字数:715 阅读:

评论:

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

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

1. 对栈的理解

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

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

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

注意动态扩容的顺序栈，出栈过程依然可以实现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 个操作数，然后进行计算，再把计算完的结果压入操作数栈，继续比较。

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