数据结构—栈(Stack)的原理以及Java实现以及后缀表达

发表于

「这是我参与11月更文挑战的第14天，活动详情查看：2021最后一次更文挑战」。

详细介绍了栈这种数据结构的基本概念，并且介绍了Java的两种不同的实现栈的方式，最后介绍了栈的应用，包括方法的递归调用和四则表达式的运算。

1 栈的概述

栈也是一种数据呈线性排列的数据结构，不过在这种结构中，我们只能访问最新添加的数据。常见的例子就是手枪弹夹，后放进弹夹的子弹将会最先被打出去。

定义中说是在线性表的表尾进行插入和删除操作，这里表尾是指栈顶，而不是栈底。

我们把允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom），不含任何数据元素的栈称为空栈。栈又称为后进先出（Last In First Out）的线性表，简称LIFO结构。

栈的插入操作，叫作进栈，也称压栈、入栈；栈的删除操作，叫作出栈，也有的叫作弹栈。

由于栈本身就是一个线性表，那么对于线性表的顺序存储和链式存储，对于栈来说，也是同样适用的。

在这里插入图片描述

在这里插入图片描述

2 入栈和出栈的关系

对于一系列元素，即使规定了入栈的顺序，它们的出栈的顺序也不一定是压栈顺序的倒序。

举例来说，如果我们现在是有3个整型数字元素1、2、3依次进栈，会有哪些出栈次序呢？

  1. 第一种：1、2、3进，再3、2、1出。出栈次序为321。
  2. 第二种：1进，1出，2进，2出，3进，3出。出栈次序为123。
  3. 第三种：1进，2进，2出，1出，3进，3出。出栈次序为213。
  4. 第四种：1进，1出，2进，3进，3出，2出。出栈次序为132。
  5. 第五种：1进，2进，2出，3进，3出，1出。出栈次序为231。

从这个简单的例子就能看出，只是3个元素，就有5种可能的出栈次序，如果元素数量多，其实出栈的变化将会更多的。

3 栈的顺序存储结构及实现

3.1 栈的顺序存储结构概述

栈的顺序存储其实也是线性表顺序存储的简化，我们简称为顺序栈。 顺序存储结构一般都是使用的数组来实现，栈也不例外。只是，这里需要考虑，用数组的哪一端来作为栈顶和栈底比较好？

当然是数组的起点，即0索引处作为栈底比较好。后续的元素入栈操作就很自然的顺序向后存储，不需要移动元素位置，而栈顶自然选在最大元素索引处，这样元素的出栈也不需要移动其他元素的位置，这样，入栈和出栈的时间复杂度都是O(1)，非常快捷。

Java的JVM就是采用的栈空间结构来进行运行时方法的调用的，方法的入栈和出栈类似于元素的入栈和出栈，只有栈顶的方法才算有效方法。Java的递归的调用，也依赖于栈空间的实现。

3.2 栈的顺序存储结构简单实现

我们的JDK中已经有了栈的实现类，那就是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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
java复制代码/**
 * 栈的顺序存储实现,为了方便,这里底层数组设计为不可扩展
 */
public class MyArrayStack<E> {

    /**
     * 底层使用数组来存储数据
     */
    private final Object[] elements;

    /**
     * 当前栈存储的元素个数
     */
    private int size;


    /**
     * 栈的总容量,数组长度
     */
    private final int capcity;

    /**
     * 构造器中初始化数组
     *
     * @param capcity
     */
    public MyArrayStack(int capcity) {
        this.capcity = capcity;
        elements = new Object[capcity];
    }


    /**
     * 入栈,从0索引处开始存放
     *
     * @param element 添加的元素
     * @return 添加成功返回true，添加失败返回false
     */
    public boolean push(E element) {
        //线性表是否容量已满
        if (size == capcity) {
            // 添加失败返回false
            return false;
        }
        //添加元素到size索引，并且size自增1
        elements[size++] = element;
        //返回true，添加成功
        return true;
    }


    /**
     * 出栈,从元素最大索引处开始出栈
     *
     * @return 返回出栈的元素或者返回null
     */
    public E pop() {
        //如果栈为空,则返回空
        if (size == 0) {
            return null;
        }
        //获取元素最大索引处的元素
        Object e = elements[size - 1];
        //出栈，元素最大索引处的位置置空，并且size自减1
        elements[--size] = null;
        return (E) e;
    }


    /**
     * 获取栈顶元素，但不出栈
     *
     * @return 返回出栈的元素或者返回null
     */
    public E peek() {
        //如果栈为空,则返回空
        if (size == 0) {
            return null;
        }
        //获取元素最大索引处的元素
        Object e = elements[size - 1];
        return (E) e;
    }

    /**
     * 清空栈
     */
    public void clear() {
        for (int i = 0; i < size; i++) {
            elements[i] = null;
        }
        size = 0;
    }


    /**
     * 重写了toString方法
     *
     * @return
     */
    @Override
    public String toString() {
        if (size == 0) {
            return "[ ]";
        }
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("[ ");
        for (int i = 0; i < size; i++) {
            stringBuilder.append(elements[i]);
            if (i != size - 1) {
                stringBuilder.append(", ");
            }
        }
        stringBuilder.append(" ]");
        return stringBuilder.toString();
    }
}

3.2.1 测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
java复制代码MyArrayStack<Object> objectMyArrayStack = new MyArrayStack<>(5);

System.out.println("入栈========>");
objectMyArrayStack.push(111);
System.out.println(objectMyArrayStack);

System.out.println("出栈========>");
Object pop = objectMyArrayStack.pop();
System.out.println(pop);
System.out.println(objectMyArrayStack);

System.out.println("入栈========>");
objectMyArrayStack.push(222);
objectMyArrayStack.push(333);


System.out.println("返回栈顶元素但是不出栈========>");
System.out.println(objectMyArrayStack.peek());
System.out.println(objectMyArrayStack);

4 栈的链式存储结构及实现

4.1 栈的链式存储结构概述

栈的链式存储结构，简称为链栈。

栈只是栈顶来做插入和删除操作，栈顶放在链表的头部还是尾部呢？当然是放在链表头部，因为链表通常只保存了头部的指针，如果栈顶放在链表尾部，那么在出栈和入栈时，还需要从链表头部开始遍历到链表的尾部进行操作，比较麻烦。而如果栈顶在链表头部，那么只需要更改链表头部指针就行了，非常轻松。

相比于顺序栈，对于链栈来说，基本不存在栈满的情况，除非内存已经没有可以使用的空间。

4.2 栈的链式存储结构的简单实现

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
java复制代码/**
 * 链栈的简单实现
 */
public class MyLinkedStack<E> {
    /**
     * 空构造器
     */
    public MyLinkedStack() {
    }


    /**
     * 元素个数
     */
    private int size;

    /**
     * 指向头结点的引用,同时也是指向栈顶的引用
     */
    private Node<E> first;

    /**
     * 链栈内部的节点
     */
    private static class Node<E> {
        //下一个结点的引用
        Node<E> next;
        //结点数据
        E data;

        //节点构造器
        public Node(E data, Node<E> next) {
            this.data = data;
            this.next = next;
        }
    }

    /**
     * 入栈,添加元素到链表头部
     *
     * @param element 添加的元素
     * @return 入栈成功返回true，入栈失败返回false
     */
    public boolean push(E element) {
        //改变头结点的
        first = new Node<>(element, first);
        size++;
        return true;
    }

    /**
     * 出栈,移除链表头部元素
     *
     * @return 被出栈的元素
     */
    public E pop() {
        //表示空栈
        if (first == null) {
            throw new NoSuchElementException();
        }
        //如果头结点不为空,表示栈里面有元素
        E e = first.data;
        //改变头结点的引用
        first = first.next;
        size--;
        return e;
    }

    /**
     * 获取栈顶元,素但不出栈
     *
     * @return 被出栈的元素
     */
    public E peek() {
        //表示空栈
        if (first == null) {
            throw new NoSuchElementException();
        }
        //返回栈顶元素
        return first.data;
    }


    /**
     * 清空栈,这里需要,遍历整个栈,一一清理
     */
    public void clear() {
        for (Node<E> x = first; x != null; ) {
            Node<E> next = x.next;
            x.next = null;
            x.data = null;
            x = next;
        }
        first = null;
        size = 0;
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        if (size > 0) {
            Node<E> f = first;
            stringBuilder.append("[ ");
            for (int i = 0; i < size; i++) {
                stringBuilder.append(f.data.toString());
                if (i != size - 1) {
                    stringBuilder.append(" , ");
                }
                f = f.next;
            }
            stringBuilder.append(" ]");
            return stringBuilder.toString();
        }
        return "[]";
    }
}

4.2.1 测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
java复制代码MyLinkedStack<Object> objectMyStack = new MyLinkedStack<>();

System.out.println("入栈========>");
objectMyStack.push(111);
System.out.println(objectMyStack);

System.out.println("出栈========>");
Object pop = objectMyStack.pop();
System.out.println(pop);
System.out.println(objectMyStack);

System.out.println("入栈========>");
objectMyStack.push(222);
objectMyStack.push(333);


System.out.println("返回栈顶元素但是不出栈========>");
System.out.println(objectMyStack.peek());
System.out.println(objectMyStack);

5 栈的应用-递归

5.1 递归的概述

栈有一个很重要的应用：那就是在程序设计语言中实现了递归。比如Java中的递归，就是通过栈来实现的。

方法定义中调用方法本身的现象，称做递归。把一个直接调用自己或通过一系列的调用语句间接地调用自己的方法，称做递归方法。

对于方法中调用方法本身，可以把它理解为在调另一个方法，只不过，这个方法和自己长得一样而已。

使用注意：

  1. 构造方法不能递归使用。
  2. 应该定义递归的结束条件，满足时递归不再进行，否则就是无限循环递归调用。
  3. 要避免内存溢出，递归深度太深容易造成栈内存溢出。

5.2 递归和栈的关系

我们以一个简单的例子，来讲解方法栈是如何实现递归调用方法的。

求一个数的阶乘：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
java复制代码public class Recursive {
    public static void main(String[] args) {
        //这里求5的阶乘    5*((5-1)*((5-1-1)*((5-1-1-1)*(5-1-1-1-1))))
        int factorial = factorial(5);
        System.out.println(factorial);
    }
    /**
     * 递归方法，求n的阶乘  n*((n-1)*((n-1-1)*((n-1-1-1)*…………)))
     *
     * @param n
     * @return
     */
    private static int factorial(int n) {
        //n大于1,则继续递归调用
        if (n > 1) {
            return n * factorial(n - 1);
        } else {
            //n小于等于1,则返回,结束递归
            return 1;
        }
    }
}

5.2.1 方法调用

由于栈的后进先出结构，方法也有入栈和出栈，调用该方法时，方法将会入栈，在栈空间顶部简历一个栈帧，方法执行完毕返回时将会出栈，栈帧被销毁。

在递归的方法中，第一层方法入栈之后，就是当前方法（栈顶的方法，JVM只有当前方法会被执行，只有当前方法是有效的）。

在这里插入图片描述

然后开始执行方法中的代码，当执行到调用第二层的方法时，JVM会将调用的方法入栈，同样压入栈顶，成为“当前方法”。同时第一层方法并没有结束，而是它的后续代码将被暂时“搁置”，直到内部调用的方法返回。

在这里插入图片描述

同理，在执行第二层方法调用时，又会执行到方法内部的第三层递归调用处，前几层方法都被冻结了，因为内部调用的方法都没有返回，而是继续调用了其他方法。

从上面的步骤可以看出来，方法在调用的时候总是从最外层方法开始一层层向里调用的。

那么，这个递归方法什么时候能够返回呢？

5.2.2 方法返回

我们注意到，每一次递归调用，方法参数n就减少1，这正是该递归方法能够正常结束的关键，当执行到第五层时，n参数变为1，根据代码，n不大于1，执行else逻辑，那么这个递归就可以返回了，并且返回1。

第五层方法由于返回而结束，这也导致第四层方法可以结束，第四层方法结束为：

return 2*(1)

第四层方法由于返回而结束，这也导致第三层方法可以结束，第三层方法结束为：

return 3*(2*1)

第三层方法由于返回而结束，这也导致第二层方法可以结束，第二层方法结束为：

return 4*(3*(2*1))

第二层方法由于返回而结束，这也导致第一层方法可以结束，第一层方法结束为：

return 5*(4*(3*(2*1)))

我们看最终返回的结果，正是第一层方法返回的结果，而这个结果正是5的阶乘。

从上面的步骤可以看出来，返回的时候总是从最底层的方法开始一层层向外返回的。

5.2.3 总结

看看了上面递归的步骤，我们知道递归利用的就是栈的特性，出栈和入栈都是操作栈顶的元素。在JVM中，规定栈顶的方法被称为当前方法，只有当前方法能够执行。关于Java中更多的递归案例可以看这篇文章：Java递归的原理以及各种案例演示。

在方法递归调用阶段：第一层方法调用第二层方法之后，第二层方法入栈，变成栈顶的当前方法，然后继续调用第三层方法入栈……先调用的方法则被渐渐的压入栈底：

在这里插入图片描述

在方法返回阶段：最顶部的方法先返回——即出栈，然后是上一层方法返回——出栈，最终是最外层的方法返回。这样就完成了方法的调用的全部逻辑！

在这里插入图片描述

6 栈的应用-四则表达式运算

6.1 后缀表达式

我们常见的标准四则运算的表达式，比如1+ 2 * 3 + (4 * 5 + 6) * 7，这样的表达式被称为中缀表达式，因为它的运算符号都在数字之间。

这样的表达式对我们人类来说是非常简单的和容易理解的，但是对于计算机来说，想要解析这样的表达式却是非常的困难，“先乘除后加减，右括号先算括号”这样的简单的口诀对于计算机就如同天书。

后来，20世纪50年代，波兰逻辑学家Jan·ukasiewicz发明了一种不需要括号的后缀表达式，也被称为逆波兰表达式。这种后缀表示法，是表达式的一种新的显示方式，非常巧妙地解决了程序实现四则运算的难题。

对于中缀表达式1+ 2 * 3 + (4 * 5 + 6) * 7，使用后缀表示法应该为：1 2 3 * + 4 5 * 6 + 7 * + 。这样的表达式称为后缀表达式，叫后缀的原因在于所有的符号都是在要运算数字的后面出现。这样的表达式，没有了括号，对于人类来说看起来比较麻烦，但是对于计算机来说则是非常简单了。

6.2 后缀表达式的计算

后缀表达式的计算规则为：从左到右遍历表达式的每个数字和符号，遇到是数字就进栈，遇到是符号，就将处于栈顶两个数字出栈，进行运算，运算结果进栈，一直到最终获得结果。

下面来计算上面的后缀表达式：1 2 3 * + 4 5 * 6 + 7 * +

后缀表达式中前三个都是数字，所以1、2、3进栈：

在这里插入图片描述

接下来是“*”，所以将栈中的3和2出栈，相乘，结果再入栈：

在这里插入图片描述

接下来是“+”，所以将栈中的6和1出栈，相加，结果再入栈：

在这里插入图片描述

接下来两个都是数字，所以4、5进栈：

在这里插入图片描述

接下来是“*”，所以将栈中的5和4出栈，相乘，结果再入栈：

在这里插入图片描述

接下来是数字，6进栈：

在这里插入图片描述

接下来是“+”，所以将栈中的6和20出栈，相加，结果再入栈：

在这里插入图片描述

接下来是数字，7进栈：

在这里插入图片描述

接下来是“*”，所以将栈中的7和26出栈，相乘，结果再入栈：

在这里插入图片描述

最后一个是“+”，所以将栈中的162和7出栈，相加，结果再入栈：

在这里插入图片描述

最终189出栈，即位后缀表达式的计算结果。这个结果刚好和中缀表达式的计算结果一致。

6.3 中缀表达式转后缀表达式

中缀表达式转后缀表达式规则：从左到右遍历中缀表达式的每个数字和符号，若是数字就输出，即成为后缀表达式的一部分；若是符号，则判断其与栈顶符号的优先级，是右括号或优先级不高于栈顶符号（乘除优先加减）则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后缀表达式为止。

下面来看看中缀表达式1 + 2 * 3 + (4 * 5 + 6) * 7 如何转换为后缀表达式1 2 3 * + 4 5 * 6 + 7 * +

初始化一空栈，用来对符号进出栈使用：

在这里插入图片描述

第1个字符是数字1，输出1，第2个字符是符号“+”，进栈：

在这里插入图片描述

第3个字符是数字2，输出2，第4个字符是符号“*”，优先级高于栈顶的+，进栈：

在这里插入图片描述

第5个字符是数字3，输出3，第6个字符是符号“+”，优先级低于栈顶的*，栈内元素依次出栈，+入栈，此时后缀表达式为：1 2 3 * +

在这里插入图片描述

第7个字符是符号“(”，是左括号，进栈：

在这里插入图片描述

第8个字符是数字4，输出，第9个字符是符号“*”， 入栈。此时后缀表达式为：1 2 3 * + 4

在这里插入图片描述

第10个字符是数字5，输出，第11个字符是符号“+”， 优先级小于栈顶的*，栈顶元素依次出栈，直到匹配到(为止，但是括号符不出栈，+入栈。此时后缀表达式为：1 2 3 * + 4 5 *

在这里插入图片描述

第12字符是数字6，输出，第13个字符是符号“)”， 是右括号，栈顶元素依次出栈，直到匹配到(为止，+入栈，括号符全都出栈。此时后缀表达式为：1 2 3 * + 4 5 * 6 +

在这里插入图片描述

第16字符是符号“*”，优先级高于栈顶符号，入栈，第17个字符是数字7，输出：

在这里插入图片描述

由于所有的字符解析完毕，栈里面剩下的符号依次出栈、输出。最终后缀表达式为：1 2 3 * + 4 5 * 6 + 7 * + 。和前面的后缀表达式一致。

6.3 总结

要想让计算机具有处理我们通常的标准（中缀）表达式的能力，最重要的就是两步：

  1. 将中缀表达式转化为后缀表达式（栈用来进出运算的符号）。
  2. 将后缀表达式进行运算得出结果（栈用来进出运算的数字）。

整个过程，都充分利用了栈的后进先出特性来处理，理解好它其实也就理解好了栈这个数据结构。

7 总结

本次我们介绍了栈这种数据结构的基本概念，并且介绍了Java的两种不同的实现栈的方式，最后介绍了栈的应用，包括方法的递归调用和四则表达式的运算。

对于方法的递归调用可能还需要一定的JVM的只是，如果对Java的JVM的运行时栈结构不太了解，可以看这篇博客：Java的JVM运行时栈结构和方法调用详解。如果对于线性表这个基本概念还不是很熟悉的同学，可以看这篇博客：Java中的线性表数据结构详解以及实现案例。

相关文章：

  1. 《大话数据结构》
  2. 《深入理解Java虚拟机》
  3. 《算法图解》

如果有什么不懂或者需要交流，可以留言。另外希望点赞、收藏、关注，我将不间断更新各种Java学习博客！

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%