08_栈（附数组及单链表的java代码实现）_输入什么会到栈中显示08

08_栈

一、问题引入

请输入一个表达式

计算式：[7x2x2-5+1-5+3-3]，点击计算（如图所示）

请问：计算机底层是如何运算得到结果的?注意不是简单的把算式列出运算,因为我们看这个算式7x2x2-5+1-5+3-3，但是计算机怎么理解这个算式的(对计算机而

言，它接收到的就是一个字符串)，我们讨论的就是这个问题 --> 栈

二、栈的介绍

​ 1）栈的英文为(stack)；

​ 2）栈是一个先入后出(FILO-First In Last Out)的有序列表；

​ 3）栈(stack)是限制线性表中元素的插入和删除，只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)；

​ 4）根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除。

​ 5）图解出栈与入栈的概念：

三、栈的应用场景

​ 1）子程序的调用:在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中。

​ 2）处理递归调用:和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆栈中。

​ 3）表达式的转换[中缀表达式转后缀表达式]与求值(实际解决)。

​ 4）二叉树的遍历。

​ 5）图形的深度优先(depth-first)搜索法。

四、数组模拟栈

4.1 思路分析

​ 1）使用数组来模拟栈

​ 2）定义一个top来表示栈顶，初始化为-1

​ 3）入栈的操作，当有数据加入到栈时，top++;stack[top]=data;

​ 4）出栈的操作，int value = stack[top];top–;return value;

数组模拟栈思路分析图

4.2 代码实现

public class ArrayStackDemo {
    public static void main(String[] args) {
        //验证数组模拟栈的正确性

        //先创建一个ArrayStack对象
        ArrayStack arrayStack = new ArrayStack(5);

        arrayStack.list();

        arrayStack.push(10);
        arrayStack.push(20);
        arrayStack.push(30);
        arrayStack.push(40);
        arrayStack.push(50);
        arrayStack.push(60);
        arrayStack.list();

        int value = arrayStack.pop();
        System.out.println(value);
        arrayStack.list();
    }
}

//定义一个ArrayStack类表示栈结构
class ArrayStack{
    private int maxSize;    //栈的大小
    private int[] stack;    //数组，数组模拟栈，数据就放在该数组中
    private int top = -1;   //top表示栈顶，初始化为-1

    //构造器
    public ArrayStack(int maxSize){
        this.maxSize = maxSize;
        stack = new int[this.maxSize];
    }

    //判断栈满
    public boolean isFull(){
        return top == maxSize - 1;
    }

    //判断栈空
    public boolean isEmpty(){
        return top == -1;
    }

    //入栈-push
    public void push(int value){
        //判断栈是否已满
        boolean flag = isFull();
        if (flag){
            System.out.println("该栈已满，无法插入数据！");
        }else{
            System.out.println("该栈未满，可以插入数据！");
            top++;
            stack[top] = value;
        }
    }

    //出栈-pop
    public int pop(){
        //判断栈是否为空栈
        boolean flag = isEmpty();
        if (flag){
            throw new RuntimeException("该栈已空，无法弹出数据！");
        }else {
            System.out.println("该栈未空，可以弹出数据！");
            int value = stack[top];
            top--;
            return value;
        }
    }

    //显示栈的所有元素--遍历栈（遍历时需要从栈顶开始显示数据）
    public void list(){
        //判断栈是否为空
        if (isEmpty()){
            System.out.println("该栈已空，无法弹出数据！");
            System.out.println("-------------------");
            return;
        }

        for (int i = top; i >= 0; i--) {
            System.out.println("stack["+ i + "] = " + stack[i] + "  ");
        }

        System.out.println("-------------------");
    }
}
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

五、链表模拟栈

5.1 代码实现

public class LinkedListStackDemo {
    public static void main(String[] args) {
        //验证单链表模拟栈的正确性

        //先创建一个LinkedListStack对象
        LinkedListStack linkedListStack = new LinkedListStack(new SingleLinkedList());

        linkedListStack.showStack();

        linkedListStack.push(10);
        linkedListStack.push(20);
        linkedListStack.push(30);

        linkedListStack.showStack();

        int value = linkedListStack.pop();
        System.out.println(value);
        linkedListStack.showStack();
    }
}

//定义一个LinkedListStack类表示栈结构
class LinkedListStack{
    private SingleLinkedList list;

    public LinkedListStack(SingleLinkedList list) {
        this.list = list;
    }

    //判断栈空
    public boolean isEmpty(){
        return list.getLength() == 0;
    }

    //入栈-push
    public void push(int value){
        Node node = new Node(value,null);
        list.add(node);
    }

    //出栈-pop
    public int pop(){
        //判断栈是否为空栈
        boolean flag = isEmpty();
        if (flag){
            throw new RuntimeException("该栈已空，无法弹出数据！");
        }else {
            System.out.println("该栈未空，可以弹出数据！");
            return list.delete();
        }
    }

    //显示栈的所有元素--遍历栈（遍历时需要从栈顶开始显示数据）
    public void showStack(){
        //判断栈是否为空
        if (isEmpty()){
            System.out.println("该栈为空栈！");
            System.out.println("-------------------");
            return;
        }

        list.reversePrint(list.getHead());
    }
}

//定义SingleLinkedList来管理节点
class SingleLinkedList{
    //先初始化一个头结点（一般不存放具体数据）
    private Node head = new Node(null,null);

    public Node getHead() {
        return head;
    }

    public SingleLinkedList() {
    }

    public SingleLinkedList(Node head) {
        this.head = head;
    }

    /*
            添加节点到单链表
            当不考虑编号顺序时
                1.找到当前链表的最后节点
                2.将尾结点的next指向新节点
        */
    public void add(Node node){
        //因为head节点不能动，所以创建一个辅助遍历的节点temp
        Node temp = head;
        //遍历链表，寻找尾结点
        while (true){
            //该节点已经是尾结点及跳出循环
            if (temp.next == null){
                break;
            }
            //若仍不是尾结点则继续遍历
            temp = temp.next;
        }

        //退出while循环时，temp就指向了链表的尾结点
        //将尾结点的next指向要插入的新节点
        temp.next = node;
    }

    //删除尾节点思路：当temp.next.next == null时，删除该节点
    public int delete(){
        Node temp = head;
        while (true){
            if (temp.next.next == null){
                //已经到链表的最后
                break;
            }

            temp = temp.next;
        }
        int value = temp.next.value;
        //删除尾节点
        temp.next = null;
        return value;
    }


    //显示链表（遍历）
    public void showList(){
        //判断链表是否为空
        if (head.next == null){
            System.out.println("该链表为空链表！");
            return;
        }

        //因为头节点不能动，所以使用一个辅助节点进行遍历
        Node temp = head.next;
        while (true){
            if (temp.next == null){
                System.out.println(temp);
                break;
            }

            System.out.println(temp);
            temp = temp.next;
        }
    }

    //显示链表长度(遍历)
    public int getLength(){
        int length = 0;

        //判断链表是否为空
        if (head.next == null){
            return length;
        }

        //因为头节点不能动，所以使用一个辅助节点进行遍历
        Node temp = head.next;
        while (true){
            if (temp.next == null){
                break;
            }
            length++;
            temp = temp.next;
        }

        return length;
    }

    //可以使用栈将各个节点压入到栈中，然后利用栈的先进后出的特点，实现逆序打印
    public void reversePrint(Node head){
        //创建一个栈stack，将各个节点压入栈
        Stack<Node> stack = new Stack<>();
        Node cur = head.next;
        while (cur != null){
            stack.push(cur);
            cur = cur.next;
        }

        //将栈中的节点pop出栈并打印
        while (stack.size() > 0){
            System.out.println(stack.pop());
        }
    }
}

//定义一个Node类，每个Node对象就是栈中的一个节点
class Node{
    public Integer value;
    public Node next;   //指向下一个节点

    //构造方法
    public Node(Integer value, Node next) {
        this.value = value;
        this.next = next;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }
}
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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201