受限制的线性表

先进后出

实现一个栈

数组实现叫顺序栈

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){
        //如果栈满了返回false，入栈失败
        if (count == n){
            return false;
        }
        //将item放到下标为count的位置，count +1
        items[count] = item;
        //栈中元素+1
        count++;
        return true;
    }

    //出栈操作
    public String pop(){
        //如果栈为空返回null
        if (count == 0){
            return null;
        }
        //返回下标第n-1个元素
        String temp = items[count - 1];
        //元素总数减1
        count--;
        return temp;
    }
}

支持动态扩容的顺序栈

分析时间复杂度
对于出栈来说时间复杂度还是O(1)
对于入栈来说如果栈空间足够时间复杂度为O(1)，如果栈空间不够用需要扩容那么时间复杂度为O(n)

链表实现叫链式栈

性能分析

不论是顺序栈还是链栈时间复杂度和空间复杂度都是O(1)

现实应用

函数调用栈

栈帧

表达式求值

两个栈实现

括号是否匹配