【Java基础】Stack基础

一.Java集合架构图

点击放大查看

二.栈的概念

1.什么是栈？

• 栈（Stack）是一种 后进先出（LIFO：Last In First Out）的数据结构。

• 什么是后进先出LIFO呢？
  最后进Stack的元素一定最先出Stack。如何做到这一点呢？只需要把队列的一端封死
  因此，Stack只能不断地往Stack中压入（push）元素，最后进去的必须最先出（pop）`来

类似于下面的甜甜圈面包,最先放的在最下面,最后吃, 最后放的在最前面,最先吃

2.栈的基本操作

Stack只有入栈和出栈的操作：

方法	描述
push(E)	把元素压栈
pop(E)	把栈顶的元素“弹出”
peek(E)	取栈顶元素但不弹出

在Java中，我们用Deque（双端队列）可以实现Stack的功能：

方法	描述
push(E)/addFirst	把元素压栈
pop(E)/removeFirst()	把栈顶的元素“弹出”
peek(E)/peekFirst()	取栈顶元素但不弹出

3.为什么Java的集合类没有单独的Stack接口呢？

• Java有个遗留类名字就叫Stack，出于兼容性考虑，所以没办法创建Stack接口， 只能用Deque接口来“模拟”一个Stack了。

• 当我们把Deque作为Stack使用时，注意只能调用 push()/pop()/peek() 方法，不要调用addFirst()/removeFirst()/peekFirst() 方法，这样代码可读性更强

三.Stack的作用

Stack在计算机中使用非常广泛，JVM在处理Java方法调用的时候就会通过栈维护方法调用的层次（顺序）

public static void main(String[] args) {
    foo(123);
}

static String foo(x) {
    return "F-" + bar(x + 1);
}

static int bar(int x) {
    return x * 2;
}

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

测试递归无限调用方法

public class Main {
    public static void main(String[] args) {
        increase(1);
    }

    static int increase(int x) {
        return increase(x) + 1;
    }
}

四.Stck小结

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

• 把元素压栈：push(E)
• 把栈顶的元素“弹出”：pop(E)
• 取栈顶元素但不弹出：peek(E)
• 在Java中我们可以用Deque可以实现Stack的功能，并且只调用push()/pop()/peek()方法，避免调用Deque的其他方法。

最后，不要使用遗留类Stack。