05.栈

1.基础概念

一句话总结:先进者后出，后进者先出。
深层理解：是一种操作受限的线性结构，只能在一端插入和删除数据。
特定的数据结构是对特定场景的抽象。其功能数组和链表也可以实现，不过问题是对外暴露的接口越多，越容易出错。

2.实现

用数组实现

public class ArrayStack {
    private String[] items;// 数组
    private int count;// 元素个数
    private int size;// 容量

    public ArrayStack(int size) {
        this.size = size;
        this.count = 0;
        this.items = new String[size];
    }

    // 入栈
    public boolean push(String item) {
        if (count == size) {
            return false;
        }
        items[count] = item;
        count++;
        return true;
    }

    // 出栈
    public String pop() {
        if (count == 0) {
            return null;
        }
        // 返回下标为count-1的元素
        String itemPop = items[count - 1];
        count--;
        return itemPop;

    }

    public static void main(String[] args) {
        ArrayStack arrayStack=new ArrayStack(10);
        arrayStack.push("hello");
        arrayStack.push("world");
        System.out.println(arrayStack.toString());
        System.out.println(arrayStack.pop());
        System.out.println(arrayStack.pop());
    
    }
}

时间复杂度:O(1)。
空间复杂度:O(1)。当我们说空间复杂度的时候，是指除了原本的数据存储空间外，算法运行还需要额外的存储空间。