转载

Java版-数据结构-栈

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

特点

只能从栈顶添加元素或者删除元素
后进先出的数据结构，Last In First Out（LIFO）

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

入栈操作示意图

出栈操作示意图（后进的元素先出）

栈的基本操作

向栈中添加一个元素（入栈）

void push(E e)
复制代码

从栈中删除一个元素（出栈）

E pop()
复制代码

查看栈顶元素

E peek()
复制代码

查看栈中元素个数

int getSize()
复制代码

判断栈是否为空

boolean isEmpty()
复制代码

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

接口定义：Stack

public interface Stack<E> {

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

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

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

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

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

}
复制代码

LinkedListStack 类实现接口Stack

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 +
                '}';
    }
}
复制代码

测试类：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);
}
复制代码

运行结果

入栈操作：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方法执行本方法业务逻辑。

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

同理，当程序执行到 B() 方法中第二行时，此时程序也会中断 B() 方法开始调用 C() 方法，然后同样地会在虚拟机栈中生成调用 C() 方法的栈帧并记录，我这里暂且称之为 B2 ，示意图如下：

当程序开始执行到 C() 方法时，直到执行完 C() 方法时，这时候，程序该如何执行呢？

此时就要查看一下虚拟机栈了，发现虚拟机栈，栈中栈顶的元素是 B2 ，我们的程序就知道了，它是执行到 B() 方法的 B2 位置就中断了，去执行 C() 方法了；现在 C() 方法执行完成之后，它就可以跳回到 B2 的位置继续执行了，当 B() 方法执行完之后，虚拟机栈中的 B2 栈帧也就可以出栈了，依次类推....