栈(Stack) 是一种后进先出(LIFO)的数据结构，只能不断地往Stack中压入（push）元素，最后进去的必须最早弹（pop)出来。

Stack只有入栈和出栈的操作

  • 把元素压栈：push(E)
  • 把栈顶的元素弹出: pop()
  • 取栈顶元素但不弹出:peek()

在Java中，我们用Deque可以实现Stack的功能。
为什么Java集合类没有单独的Stack接口呢？
因为有个遗留类的名字就叫Stack，出于兼容性考虑，所以没办法创建Stack接口，只能用Deque接口来模拟一个Stack。
当我们把Deque作为Stack使用时，注意只调用push()、pop()、peek()方法，不要调用addFirst()、removeFirst()、peekFirst()方法，这样代码更加清晰。

Stack的作用

Stack在计算机中使用非常广泛，JVM在处理Java方法调用的时候就会通过栈这种数据结构维护方法调用的层次。

  1. static void main(String[] args) {
  2.     foo(123);
  3. }
  4. static String foo(x) {
  5.     return "F-" +bar(x +1);
  6. }
  8. static int bar(int x) {
  9.     return x << 2;
  10. }

JVM会创建方法调用栈，每调用一个方法时，先将参数压栈，然后执行对应的方法；
当方法返回时，返回值压栈，调用方法通过获得方法返回值。
方法调用栈有容量限制，嵌套调用过多会造成栈溢出，即引发StackOverflowError

我们再来看一个Stack的用途，对整数进行进制的转换可以利用栈。
例如，我们要把一个int整数12500转换成十六进制表示的字符串，如何实现这个功能呢？

首先我们准备一个空栈，然后计算12500 /16 = 781 … 4，余数是4，把余数4压栈。
然后计算781 / 16 = 48 … 13，余数是13，13的十六进制用字母D表示，把余数D压栈
48 / 16 = 3 …0 ,0 压栈，最后计算3 / 16 = 0 … 3 ，将余数3压栈，

当商是0的时候，计算结束，我们把栈的所有元素依次弹出，组成字符串30D4 ，这就是十进制整数12500的十六进制表示的字符串。

计算中缀表达式

在编写程序的时候，我们使用的带括号的数学表达式实际上是中缀表达式，即运算符在中间。 1 + 2 ( 9 - 5 )。
但是计算机执行表达式的时候，它并不能直接计算中缀表达式，而通过编译器把中缀表达式转换为后缀表达式，例如 1 2 9 5 - +
这个编译过程就会用到栈。先路过编译这一步（涉及运算优先级，代码比较复杂），看看如何通过栈计算后缀表达式。
计算后缀表达式不考虑优先级，直接从左到右依次计算，因此计算起来简单。

首先依次扫描后缀表达式1 2 9 5 - * +，并依次压栈。
接下来遇到减号时，弹出栈顶的两个元素，并计算9-5 = 4,把结果4压栈
接下来遇到*号时， 弹出栈顶的两个元素并计算2*4 = 8，把8压栈，最后遇到+号时，弹出栈顶两个元素，并计算1+8 = 9 把9压栈。
扫描结束后，没有更多的计算，弹出栈的唯一一个元素，得到计算结果9。

练习

利用Stack把一个给定的整数转换为十六进制

public class Main {
    public static void main(String[] args){
        String hex = toHex(12500);
        if(hex.equalsIgnoreCase("30D4")) {
            System.out.println("测试成功");
        } else { 
            System.out.println("测试失败");
        }
    }

    static String toHex(int n) {

        Deque<String> stack = new LinkedList<>();

       StringBuilder  sb  = new StringBuilder();
           while(n > 0) {

            stack.push(n % 16);
            n = n / 16;

        } 

        for(String s : stack) {
            sb.append(s);
        }
        return sb;

    }
}

还有俩练习，草，好难，不会写，先学下面的。

小结

栈Stack是一种后进先出LIFO的数据结构，操作栈的元素的方法有

  • 压栈，push()
  • 取栈顶但不删除，E peek()
  • 取栈顶元素并删除，E pop()