栈

发表于 更新于 分类于 阅读次数： Valine：

栈的介绍

栈的英文为stack，栈是一个先入后出的有序链表，栈是限制线性表中元素的插入和删除只能在线性表的同一段进行的一种特殊的线性表。允许插入和删除的一端称为栈顶，另外一端称为栈底

image-20220608155318037

应用场景

  1. 子程序的调用，在跳往下一个程序的时候，将其数据暂时保存在栈中，递归就是这种情况https://moonshuo.cn/posts/28724.html
  2. 表达式的转换（中缀表达式转后缀表达式）与求值
  3. 二叉树的遍历
  4. 图形的深度优先

栈的入门

数组模拟栈

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
package 数据结构和算法.栈;

/**
 * @author 21050
 */
public class ArrayStack {
    public static void main(String[] args) {
        Stack stack=new Stack(5);
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
        stack.push(6);
        stack.show();

        System.out.println("开始出栈");
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());

    }


}

class Stack {
    //定义size的大小
    private int size;
    //定义数据
    private int[] stack;
    //默认情况下top为-1
    private int top = -1;

    //定义构造函数定义一个栈
    public Stack(int size) {
        this.size = size;
        stack = new int[size];
    }

    //判断栈是否为空
    public boolean isNull() {
        return top == -1;
    }

    //判断栈是否为满
    public boolean isFull() {
        return top == size - 1;
    }

    //入栈操作
    public void push(int value) {
        if (isFull()) {
            System.out.println("栈为满");
        } else {
           stack[++top]=value;
        }
    }

    //出栈操作
    public int pop(){
        if (isNull()){
            throw new RuntimeException("栈为空");

        }else {
            return stack[top--];
        }
    }

    //遍历栈，从top开始
    public void show(){
        if (isNull()){
            System.out.println("为空");
        }else {
            for (int i=top;i>-1;i--){
                System.out.println(stack[i]);
            }
        }
    }
}

image-20220608163306074

链表模拟栈

类结构有一点瑕疵，先不调整了

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
package 数据结构和算法.栈;

/**
 * @author 21050
 */
public class LinkedNode {


    public static void main(String[] args) {

        //建立一个头节点
        Node head=new Node(0);
        Node node1=new Node(1);
        Node node2=new Node(2);
        Node node3=new Node(3);
        Node node4=new Node(4);
        head.push(node1,head);
        head.push(node2,head);
        head.push(node3,head);
        head.push(node4,head);

        head.show(head);

        head.pop(head);
        head.pop(head);
        head.show(head);
    }

}
class Node{
    private int data;
    Node next;

    public Node(int data) {
        this.data = data;
    }

    public boolean isEmpty(Node head){
        return head.next==null;
    }
    //设置插入方法，考虑到栈的遍历方法，我们这里使用头插法
    public void push(Node node,Node head){
        if (isEmpty(head)){
            head.next=node;
        }else {
            node.next= head.next;
            head.next=node;
        }
    }

    //设置出栈方法，这里的出栈都是将head.next删除
    public int pop(Node head){
        if (isEmpty(head)){
            throw new RuntimeException("栈为空，无法完成操作");
        }
        else {
            int popData=head.next.data;
            head.next=head.next.next;
            return popData;
        }
    }

    public void show(Node head){
        Node temp=head;
        while (temp.next!=null){
            temp=temp.next;
            System.out.println(temp);
        }
    }

    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                '}';
    }
}

image-20220608165437129

表达式

前缀表达式

前缀表达式又称波兰表达式，前缀表达式的运算符位于操作数之前，例如（3+4）*5-6的前缀表达式时是- * + 3456

这个扫描的方法是从右向左依次进行扫描，在遇到第一个运算符之前，数字栈的空间如下

image-20220609145117365

当遇到一个运算符的时候，取出栈顶和次栈顶元素，与运算符进行运算

image-20220609145228092

模拟（这里偷懒，使用系统提供的栈）：

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
package 数据结构和算法.栈;

import java.util.Stack;

public class StackExercise {
    public static void main(String[] args) {
        Stack<Integer> numSatck=new Stack<>();
        //首先从右向左扫描，入栈6543
        numSatck.add(6);
        numSatck.add(5);
        numSatck.add(4);
        numSatck.add(3);

        //扫描到+,出栈头元素个次头元素
        int head=numSatck.pop();
        int second=numSatck.pop();
        //将得到的结果压入栈
        numSatck.add(head+second);
        //扫描到*，将结果压入栈
         head=numSatck.pop();
         second=numSatck.pop();
        numSatck.add(head*second);
        //-运算符，压入栈
        head=numSatck.pop();
        second=numSatck.pop();
        numSatck.add(head-second);
        System.out.println("最终的值为"+numSatck.pop());
    }


}

image-20220609150314475

中缀表达式

是我们最常见的运算表达式（3+4）*5-6

后缀表达式

（3+4）*5-6这个的后缀表达式为

1
2
//在这个过程中从左向右扫描，遇到第一个数字压入数字栈，遇到运算符，将符号压入符号栈，同时取出栈顶元素与次栈顶元素进行计算，结果压入栈中
3 4 + 5 * 6 -

在运算后缀表达式的时候，遇到第一个运算符之前，数字栈空间如下

image-20220609144805019

而当遇到第一个之后

image-20220609144844278

剩下的依次类推得出相应的结果

这里就不模拟了

中缀转后缀表达式

我们知道中缀表达式中存在（），在转换后缀表达式的时候需要进行转换

比如5+（（3+4）*5）-6这个在转化的时候，会扫描这个表达式，我们现在要将这个表达式转化为后缀表达式

此时我们开始扫描，遇到操作数直接将其压入栈中，左边s1为运算符栈

image-20220609155308517

遇到运算符与将其与运算符栈顶比较，此时为空，直接压入s1栈，此时遇到两个左括号，压入s1栈

image-20220609160833950

继续扫描，遇到3+4，3直接压入栈中，而+与s1栈顶元素（比较优先级，优先级大，直接压入s1栈

image-20220609161130061

此时再一次扫描遇到右括号，扫描s1栈，直到遇到左括号，并将中间扫描的全部移动到s2栈，括号去掉

image-20220609161327780

我们继续扫描，将*进入到s1栈中，5进入s2栈，此时我们再一次扫描到右括号，将这里的值调到s2中，去掉括号，

image-20220609161553473

接下来我们扫描到-，-与栈顶+的优先级相同，+出栈到s2，-入栈到s1,并且扫描到6

image-20220609161819577

将s1栈中值移动过去，得最终结果534+5*+6-

image-20220609161900585

我们使用代码进行模拟

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
package 数据结构和算法.栈;

import java.util.Stack;

public class StackExercise {

    public boolean biggerPriority(char head, char operate) {
        //遇到左括号直接加
        if (head == '('||operate=='(') {
            //如果左括号，则优先级最小
            return true;
        }
        if (head == '+' || head == '-') {
            //只要operate不是(，+-，那么就可以判断operate优先级大
            return operate == '*' || operate == '/';
        }
        if (head == '*' || head == '/') {
            //如果head为*/，则默认优先级最大
            return false;
        } else {
            throw new RuntimeException("我们无法判断符号优先级，请检测符号是否正确");
        }

    }


    public static void main(String[] args) {
        StackExercise stackExercise = new StackExercise();
        Stack<Character> s1 = new Stack<>();
        Stack<Character> s2 = new Stack<>();
        String expression = "5+((3+4)*5)-6";
        for (int i = 0; i < expression.length(); i++) {
            char a = expression.charAt(i);
            //判断是否为数字
            if (Character.isDigit(a)) {
                s2.add(a);
                //等于右括号的时候，括号之间的元素出栈到s1，同时删除（）
            } else if (a==')') {
                char temp=s1.pop();
                while (temp!='('){
                    s2.add(temp);
                    temp=s1.pop();
                }
            } else {
                //如果为空，直接进入
                if (s1.isEmpty()) {
                    s1.add(a);
                    //如果不为空，则比较优先级的大小，
                } else {
                    //如果优先级大，直接插入s1
                    char temp = s1.pop();
                    if (stackExercise.biggerPriority(temp, a)) {
                        //记得将temp拿回去，此时并不能出栈
                        s1.add(temp);
                        s1.add(a);
                        //如果优先级小，temp到s2中，而a进入栈s1
                    } else {
                        s2.add(temp);
                        s1.add(a);
                    }

                }
            }
        }
        System.out.println(s2);
    }


}

image-20220609165819173