Some applications about stack

极客时间版权所有: https://time.geekbang.org/column/article/41222

定义

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// 基于数组实现的顺序栈
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)

当涉及到动态内存申请,比如利用数组实现到顺序栈,当数组空间不够时,需要重新申请一块更大的内存,同时将原有的数据全部拷贝进去。每次进行 k-1 个插入时间复杂度为O(1)的动作,就需要进行一次需要进行k个数据搬移的插入动作,时间复杂度为O(k)。利用摊还分析的方法,k次插入动作的时间复杂度依然为O(1)。

应用

表达式求值

求 34+13*9+44-12/3

实际上,编译器通过两个栈来实现。其中一个是操作数栈,另外一个是运算符栈。从左到右遍历时,

  • 遇到数字就直接压入操作数栈;
  • 遇到运算符就与栈顶的运算符元素进行比较,分为两种情况讨论:
    • 如果比栈顶运算符的优先级低或者相同,取出栈顶运算符,同时从操作数栈的栈顶取两个操作数,进行计算,然后将结果入栈。
    • 如果运算符优先级高,直接入栈。

括号匹配

从左到右依次扫描字符串,用栈来保存没有匹配的左括号。扫描到左括号时,压栈;扫描到右括号时,检查与栈顶的左括号是否匹配,若匹配,左括号出栈,继续扫描,如果不匹配,字符串非法。

Donate article here