栈_栈的时间复杂度

后进者先出，先进者后出，这就是典型的“栈”结构。
当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，我们就应该首选“栈”这种数据结构。
实际上，栈既可以用数组来实现，也可以用链表来实现。用数组实现的栈，我们叫作顺序栈，用链表实现的栈，我们叫作链式栈。

数组栈

public class ArrayStack {
   private String[] items; //数组
   private int count;  //栈元素个数
   private int n; //栈的大小
   
   //初始化栈空间
   public ArrayStack(int n){
       this.items = new String[n];
       this.n = n;
       this.count = 0;
   } 
   
   //入栈
    public boolean push(String item){
       //内存溢出
        if(count == n){
            return false;
        }
        items[count] = item;
        ++count;
        return true;
    }
    
    //出栈
    public String pop(){
       //栈为空
        if(count == 0){
            return null;
        }
        //
        String tmp = items[count-1];
        --count;
        return tmp;
    }
}

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
34
35
36

对于固定大小栈的出栈和入栈，时间复杂度为O(1)。
但是对于支持动态扩容的顺序栈：
出栈时间复杂度为O(1)。
入栈：如果有空闲空间，入栈复杂度为O(1)，空间不够时，时间复杂度为O(n)。

平均时间复杂度（摊还分析法）

均摊时间复杂度一般都等于最好情况时间复杂度。因为在大部分情况下，入栈操作的时间复杂度 O 都是 O(1)，只有在个别时刻才会退化为 O(n)，所以把耗时多的入栈操作的时间均摊到其他入栈操作上，平均情况下的耗时就接近 O(1)。

栈在函数调用中的应用

栈在表达式中的应用


实现浏览器的前进后退功能
如果跳到新的页面需要清空栈

为什么函数调用要用“栈”来保存临时变量呢？用其他数据结构不行吗？
其实，我们不一定非要用栈来保存临时变量，只不过如果这个函数调用符合后进先出的特性，用栈这种数据结构来实现，是最顺理成章的选择。
从调用函数进入被调用函数，对于数据来说，变化的是什么呢？是作用域。所以根本上，只要能保证每进入一个新的函数，都是一个新的作用域就可以。而要实现这个，用栈就非常方便。在进入被调用函数的时候，分配一段栈空间给这个函数的变量，在函数结束的时候，将栈顶复位，正好回到调用函数的作用域内。