Java 数据结构 栈
    栈是一种非常有用的数据结构，它就像一摞盘子，第一个放在最下面，第二个放在第一个上面，第三个放在第二个上面，最后一个放在最上面。
    栈 - 图1
    对于这一摞盘子，可以做两件事情：

    • 在最上面放一个新盘子
    • 把顶部的盘子拿走

    这两件事情做起来很容易，但如果从中间或者底部抽出来一个盘子，就很难办到。如果想要拿到最下面的盘子，就必须把它上面的所有盘子都拿走，像这样的一个操作，称之为后进先出，也就是“Last In First Out”（简称LIFO）——最后的一个进的，最先出去。
    对于栈这样一个数据结构来说，它有两个常见的动作：

    • push，中文释义有很多种，或者叫它“压入”，非常形象。当要把一个元素放入栈的顶部，这个动作就叫做 push。
    • pop，同样的，可以叫它“弹出”，带有很强烈的动画效果，当要从栈中移除一个元素时，这个动作就叫做 pop。

    栈 - 图2
    对于上面这幅图来说，3 这个元素最后放进去，却是最先被移除的——遵循 LIFO 的原则。
    明白了栈的基本操作后，需要去深入地思考一下，栈是如何工作的。换句话说，为了使栈这个数据结构按照栈的方式去工作，它需要什么？
    1）栈需要有一个指针，称之为 TOP，用它来指向栈中最顶部的那个元素。
    2）当初始化一个栈的时候，把 TOP 的值设置为 -1，这样就可以通过 TOP == -1 来判断栈是否为空。
    3）当要在栈中压入一个元素的时候，把 TOP 的值加 1，然后把新压入的元素指向 TOP。
    4）当要从栈中弹出一个元素的时候，把 TOP 的值减 1，然后把保持在最顶部的那个元素指向 TOP。
    5）当压入一个元素的时候，需要检查栈是否已经满了。也就是说，需要有一个 isFull() 的方法来判断。
    6）当要弹出一个元素的时候，需要检查栈是否已经空了。也就是说，需要有一个 isEmpty() 的方法来判断。
    栈 - 图3
    空栈的时候，TOP 等于 -1；把元素 1 压入栈中的时候，stack[0] 为 1，TOP 加 1 变为 0；把元素 2 压入栈中的时候，stack[1] 为 2，TOP 加 1 变为 1；把元素 3 压入栈中的时候，stack[2] 为 3，TOP 加 1 变为 2；把元素 3 从栈中弹出后，返回元素 stack[2]，TOP 减 1 变为 1。
    假设栈中的元素是 int 类型，可以用 Java 语言来自定义一个最简单的栈。它需要 3 个字段：

    • int arr[]，一个 int 类型的数组，来存放数据
    • int top，一个 int 类型的标记
    • int capacity，一个 int 类型的容量
      1. class Stack {
      2.   private int arr[];
      3.   private int top;
      4.   private int capacity;
      5. }
      初始化栈：
      1. Stack(int size) {
      2.   arr = new int[size];
      3.   capacity = size;
      4.   top = -1;
      5. }
      往栈中压入元素：
      1. public void push(int x) {
      2.   if (isFull()) {
      3.       System.out.println("溢出\n程序终止\n");
      4.       System.exit(1);
      5.   }
      6.   System.out.println("压入 " + x);
      7.   arr[++top] = x;
      8. }
      从栈中弹出元素：
      public int pop() {
  if (isEmpty()) {
      System.out.println("栈是空的");
      System.exit(1);
  }
  return arr[top--];
}
      返回栈的大小：
      public int size() {
  return top + 1;
}
      检查栈是否为空：
      public Boolean isEmpty() {
  return top == -1;
}
      检查栈是否已经满了：
      public Boolean isFull() {
  return top == capacity - 1;
}
      通过 main() 方法直接测试下：
      public void printStack() {
  for (int i = 0; i <= top; i++) {
      System.out.println(arr[i]);
  }
}
public static void main(String[] args) {
  Stack stack = new Stack(5);
  stack.push(1);
  stack.push(2);
  stack.push(3);
  stack.push(4);
  stack.pop();
  System.out.println("\n弹出元素后");
  stack.printStack();
}
      打印结果如下所示：
      压入 1
压入 2
压入 3
压入 4
弹出元素后
1
2
3
      由于是通过数组来实现的栈，所以 push 和 pop 的时间复杂度就是 O(1)。
      尽管栈是一种非常简单的数据结构，通过上面的代码大家应该也能感受得出来，轻而易举地就实现了，但是栈却是一种非常强有力的数据结构，可以在很多场景中使用，比如说：
      1）反转一串字符：
      由于栈是 LIFO 的，所以反转一串字符很容易，按照正常的顺序把字符压入栈中，然后再弹出来就行了。
      2）用于计算器：
      要想计算一个复杂的表达式，比如说 2 + 5 / 3 * (6 - 2)，就需要一个栈来容纳这些数字和运算符，然后按照优先级弹出后进行计算。
      3）用于浏览器：
      浏览器的后退按钮会把访问的 URL 压入一个栈中，每次访问一个新的页面，新的 URL 就压入了栈的顶部，当点了后退按钮，最新的那个 URL 就从栈中移除，之前的那个 URL 就被访问到了。