数据结构与算法 -- 栈

实现

  1. 栈即可以用数组实现,也可以用链表实现
  2. 数组实现的栈,称为顺序栈,用链表实现的栈,称为链式栈

顺序栈

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
public class ArrayStack<T> {
private Object[] items;
@Getter
private int count;
@Getter
private int size;

public ArrayStack(int n) {
items = new Object[n];
count = 0;
size = n;
}

public boolean push(T t) {
if (count == size) {
return false;
}
items[count++] = t;
return true;
}

public T pop() {
if (count == 0) {
return null;
}
return (T) items[--count];
}
}

复杂度分析

  1. 不管是顺序栈还是链式栈,存储数据只需要大小为n的数组即可
    • 在入栈和出栈的过程中,只需要固定的临时变量存储空间,所以空间复杂度O(1)
    • n个空间是必须的,无法省掉,因此空间复杂度指的是除了原本的数据存储空间外,算法运行还需要额外的存储空间
  2. 不管是顺序栈还是链式栈,入栈和出栈只涉及个别数据的操作,所以时间复杂度O(1)

动态扩容

  1. 实现一个支持动态扩容的顺序栈,只需要底层依赖一个支持动态扩容的数组即可
  2. 出栈操作
    • 对于出栈操作来说,不会涉及到内存重新申请和数据搬移,所以出栈的时间复杂度依然为O(1)
  3. 入栈操作
    • 当空间不够时,需要重新申请内存和数据搬移,时间复杂度变成了O(n)
    • 因此,最好时间复杂度为O(1),最坏时间复杂度为O(n),而平均时间复杂度可以用摊还分析法来分析

摊还分析法

  1. 假设
    • 栈空间不够时,重新申请一个原来大小2倍的数组
    • 为了简化分析,只有入栈操作,没有出栈操作
    • 不涉及内存搬移的入栈操作,时间复杂度为O(1)
  2. 当前栈大小为K,并且已满,再有新数据要入栈时,需要申请2倍大小的内存,做K个数据的搬移操作,再入栈
    • 但后续的K-1次入栈操作,均无需重新申请内存和搬移数据
    • 因此,K次入栈操作,总共涉及了K次数据搬移,和K次简单入栈
      • 均摊后,每次入栈操作包括一次数据搬移和一次简单入栈,这样时间复杂度依然为O(1)
  3. 大部分情况下,均摊时间复杂度 = 最好时间复杂度
0%