43

数据结构与算法 -- 栈

 4 years ago
source link: https://www.tuicool.com/articles/FJ3YvaV
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
  1. 栈即可以用 数组 实现，也可以用 链表 实现
  2. 用 数组 实现的栈，称为 顺序栈 ，用 链表 实现的栈，称为 链式栈

顺序栈 

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. 假设 
    O(1)
  2. 当前栈大小为K，并且已满，再有新数据要入栈时，需要申请2倍大小的内存，做K个数据的搬移操作，再入栈
    • 但后续的K-1次入栈操作，均无需重新申请内存和搬移数据
    • 因此，K次入栈操作，总共涉及了K次数据搬移，和K次简单入栈
      • 均摊后，每次入栈操作包括一次数据搬移和一次简单入栈，这样时间复杂度依然为 O(1)
  3. 大部分情况下， 均摊时间复杂度 = 最好时间复杂度

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK