Java数据结构之Java堆栈不得不知道的那些事

作者: 管彤Java架构师 | 来源:发表于2022-05-20 17:04 被阅读0次

Java数据结构之Java堆栈不得不知道的那些事
面试题汇总
Frida Hook
Java基础之集合类
文集总目录
Java基础常识（应该知道）
java 数据结构（collections）
jstack(Java Stack Trace)简介
Java数据结构算法（二）栈和队列
Java堆栈

介绍

栈是一种后进先出的线性表数据结构，分为栈顶和栈底两端，仅允许在表的一端插入元素，这一端被称为栈顶，另外一端称之为栈底。栈，只有两种操作，分为入栈(压栈)和出栈(退栈);向栈中添加元素的操作叫做入栈，相反从栈中删除元素叫做出栈。

特点

• 只能从栈顶添加元素或者删除元素

• 后进先出的数据结构，Last In First Out(LIFO)

为了大家更好的形象了解我们通过示意图来看一下栈的入栈和出栈操作

1. 入栈操作示意图

image.png

2. 出栈操作示意图(后进的元素先出)

image.png

栈的基本操作

• 向栈中添加一个元素(入栈)

void push(E e)

• 从栈中删除一个元素(出栈)

E pop()

• 查看栈顶元素

E peek()

• 查看栈中元素个数

int getSize()

• 判断栈是否为空

boolean isEmpty()

实现栈的方式，实际上底层有多种实现方式，比如：动态数组等，这里我们使用Java语言本身为我们提供的集合LinkedList

1. 接口定义：Stack<E>

public interface Stack<E> {

    /**
     * 向栈中添加元素
     *
     * @param e
     */
    void push(E e);

    /**
     * 从栈中删除元素
     */
    void pop();

    /**
     * 获取栈顶元素
     *
     * @return
     */
    E peek();

    /**
     * 获取栈中元素个数
     *
     * @return
     */
    int getSize();

    /**
     * 判断栈中是否为空
     *
     * @return
     */
    boolean isEmpty();

}

2. LinkedListStack<E> 类实现接口Stack<E>

public class LinkedListStack<E> implements Stack<E> {
    /**
     * 存放栈元素
     */
    LinkedList<E> list;

    /**
     * 构造栈结构
     */
    public LinkedListStack() {
        list = new LinkedList<>();
    }

    @Override
    public void push(E e) {
        list.addLast(e);
    }

    @Override
    public void pop() {
        list.removeLast();
    }

    @Override
    public E peek() {
        return list.getLast();
    }

    @Override
    public int getSize() {
        return list.size();
    }

    @Override
    public boolean isEmpty() {
        return list.isEmpty();
    }

    @Override
    public String toString() {
        return "LinkedListStack{" +
                "list=" + list +
                '}';
    }
}

3. 测试类：LinkedListStackTest

@Test
public void testLinkedListStack() {
    // 栈
    Stack<String> stack = new LinkedListStack<>();
    // 准备入栈元素
    List<String> prepareElements = Arrays.asList("A", "B", "C", "D", "E");
    // 入栈
    prepareElements.forEach(x -> {
        stack.push(x);
        System.out.println("入栈操作：" + stack);
    });
    // 出栈
    stack.pop();
    System.out.println("出栈操作：" + stack);
    // 获取栈顶元素
    String peekElement = stack.peek();
    System.out.println("栈顶元素：" + peekElement);
    // 获取栈中元素的个数
    int stackSize = stack.getSize();
    System.out.println("栈中元素个数：" + stackSize);
}

4. 运行结果

入栈操作：LinkedListStack{list=[A]}
入栈操作：LinkedListStack{list=[A, B]}
入栈操作：LinkedListStack{list=[A, B, C]}
入栈操作：LinkedListStack{list=[A, B, C, D]}
入栈操作：LinkedListStack{list=[A, B, C, D, E]}
出栈操作：LinkedListStack{list=[A, B, C, D]}
栈顶元素：D
栈中元素个数：4

栈的应用

虚拟机栈的入栈和出栈操作

在Java虚拟机运行时数据区有一块被称之为：虚拟机栈，它是线程私有的，声明周期与线程相同。

我们编写的每个Java方法，每个方法都会在执行的时候同时都会创建一个栈帧(Stack Frame)用于存储局部变量表、操作数栈、动态链接、方法出口等信息。每一个方法从调用直至执行完成的过程，就对应这一个栈帧在虚拟机栈中入栈到出栈的过程。

现在我们假设有A、B、C三个方法，在A方法中调用B方法(A->B)，在B方法中调用C方法(B->C)，C方法执行本方法业务逻辑。

image.png

当程序执行到A()方法的中的第二行时，此时程序会中断A()方法并开始调用B()方法，然后会在虚拟机栈中记录调用B()方法的栈帧，我这里暂且称之为A2(实际存储的并不是O(∩_∩)O哈!)示意图如下：

image.png

同理，当程序执行到B()方法中第二行时，此时程序也会中断B()方法开始调用C()方法，然后同样地会在虚拟机栈中生成调用C()方法的栈帧并记录，我这里暂且称之为B2，在此我向大家推荐一个架构学习交流圈。交流学习指导伪鑫：1253431195（里面有大量的面试题及答案）里面会分享一些资深架构师录制的视频录像：有Spring，MyBatis，Netty源码分析，高并发、高性能、分布式、微服务架构的原理，JVM性能优化、分布式架构等这些成为架构师必备的知识体系。还能领取免费的学习资源，目前受益良多
示意图如下：