栈最为一种的常用的数据结构，用“桶”来形容最合适不过；今天我们就来学习一下
正文 一、栈的定义？
1.“后进先出，先进后出”的数据结构。
2.从操作特性来看，是一种“操作受限”的线性表，只可以在一端插入和删除数据。
二、为什么需要栈？
1.任何数据结构都是对特定应用场景的抽象，栈是一种操作受限的数据结构，其操作特性用数组和链表均可实现，但却暴露太多的操作接口，使用时容易出错；
2.当某个数据集合只涉及在一端插入和删除数据，且满足后进者先出，先进者后出的操作特性时，我们应该首选栈这种数据结构
三、如何实现栈？
栈可以用数组，链表来实现
1.以数组为例空间复杂度为O(1)
时间复杂度大多数为O（1），特殊情况自动扩容拷贝原数组时为O（n）；
均摊时间复杂度接近于O（1）；
// 基于数组实现的顺序栈 public class ArrayStack { private String[] items; // 数组 private int count; // 栈中元素个数 private int n; // 栈的大小 // 初始化数组，申请一个大小为 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 加一 items[count] = item; ++count; return true; } // 出栈操作 public String pop() { // 栈为空，则直接返回 null if (count == 0) return null; // 返回下标为 count-1 的数组元素，并且栈中元素个数 count 减一 String tmp = items[count-1]; --count; return tmp; } }