Java版-数据结构-栈

原创
顾立剑
数据结构
0 ℃

介绍

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

特点

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

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

入栈操作示意图

image-20190311222134128

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

image-20190311222101553

栈的基本操作

  • 向栈中添加一个元素（入栈）
1
void push(E e)
  • 从栈中删除一个元素（出栈）
1
E pop()
  • 查看栈顶元素
1
E peek()
  • 查看栈中元素个数
1
int getSize()
  • 判断栈是否为空
1
boolean isEmpty()

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

接口定义：Stack
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public interface Stack<E> {

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

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

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

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

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

}
LinkedListStack 类实现接口Stack
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
@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);
}
运行结果
1
2
3
4
5
6
7
8
入栈操作：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-20190311230707333

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

image-20190311231917661

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

image-20190311232716815

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

image-20190311233500400

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

image-20190311234438000

如果一个方法，使用递归调用，若递归临界点判断有误，则方法就会一直的被进行入栈操作，如果超过虚拟机栈的默认容量大小，则会出现我们常见的 StackOverflowError 异常

完整版代码GitHub仓库地址：Java版数据结构-栈 欢迎大家【关注】和【Star】

本次我们完成的是基于Java自身自带的集合LinkedList来实现栈，有兴趣的童鞋，可以使用动态数组方式来实现；接下来，笔者还会一一的实现其它常见的数组结构。

  • 静态数组
  • 动态数组
  • 栈
  • 队列
  • 链表
  • 循环链表
  • 二分搜索树
  • 优先队列
  • 堆
  • 线段树
  • 字典树
  • AVL
  • 红黑树
  • 哈希表
  • ….

持续更新中，欢迎大家关注公众号：小白程序之路（whiteontheroad），第一时间获取最新信息！！！

数据结构