数据结构の线性结构の栈 | Monster

数据结构の线性结构の栈

  • 栈(stack),是一个先入后出的有序列表;栈是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表,允许插入和删除的一端为变化的一端,成为栈顶,另一端为固定的一端,称为栈底

  • 根据栈的定义可知,最先放入栈中的元素在栈底,最后放入的元素在栈顶,而删除元素刚好相反,最后放入的元素最先删除,最先放入的元素最后删除

  • 入栈(push)、出栈(pop

  • 应用场景

    • 子程序调用:

      在眺往子程序前,会先将下个指令的地址存到堆栈中,直到子程序执行完后再讲地址取出,以回到原来的程序中

    • 处理递归调用:

      同子程序调用类似,知识除了保存下一个指令的地址外,还讲将参数、区域变量等数据存入堆栈中

    • 表达式的转换(中缀表达式转后缀表达式)与求值

    • 二叉树的遍历

    • 图形的深度优先搜索法(depth-first

使用数组模拟栈
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
public class ArrayStackDemo {
public static void main(String[] args) {
ArrayStack stack = new ArrayStack(5);
stack.push(88);
stack.push(99);
stack.push(101);
stack.list();
System.out.println("出栈前....................");
System.out.println(stack.pop());
System.out.println("出栈后.................... ");
stack.list();
}
}


/**
* 模拟栈结构
*/
class ArrayStack{

private int maxSize; //栈的大小

private int[] data; //数组 模拟栈的存储

private int top = -1; //栈顶


public ArrayStack(int maxSize) {
this.maxSize = maxSize;
data = new int[maxSize];
}


// 判断栈是否满了
public boolean isFull(){
// 当栈顶等于 栈的长度-1的时候 说明此栈已满
return top == maxSize-1;
}

// 判断栈是否空了
public boolean isEmpty(){
// 栈顶 等于 -1
return top == -1;
}

// 入栈
public void push(int value){
//判断是否已满
if(isFull()){
// TODO 栈满
return;
}
// 先将指针后移 然后将数据放入该位置 实现入栈
top++;
this.data[top] = value;
}

// 出栈
public int pop(){
// 将栈顶的数据取出
// 判断栈是否为空
if(isEmpty()){
//TODO 栈为空
throw new RuntimeException("is empty");
}

// 取出栈顶的数据
int num = this.data[top];
// 指针减一
top--;
return num;
}


//遍历栈 需要从 栈顶开始显示
public void list(){
if(isEmpty()){
//TODO 栈空
}
for (int i = top; i >= 0; i--) {
System.out.printf("stack[%d]=%d\n",i,this.data[i]);
}
}
}
使用链表模拟栈
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
public class LinkedListStackDemo {

public static void main(String[] args) {
LinkedList linkedList = new LinkedList();
linkedList.add(new Node(10));
linkedList.add(new Node(20));
linkedList.add(new Node(30));
linkedList.add(new Node(40));

linkedList.pop();
linkedList.pop();
linkedList.pop();
linkedList.pop();

}
}



class LinkedList{
private Node header = new Node(0);

public void add(Node node){
Node next = this.header.getNextNode();

if(next == null){
this.header.setNextNode(node);
return;
}

node.setNextNode(next);
this.header.setNextNode(node);

}

public void pop(){
System.out.println(header.getNextNode().getData());

header = header.getNextNode();
}
}


class Node{

private int data;

private Node nextNode;

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

public int getData() {
return data;
}

public void setData(int data) {
this.data = data;
}

public Node getNextNode() {
return nextNode;
}

public void setNextNode(Node nextNode) {
this.nextNode = nextNode;
}
}
根据表达式模拟计算器求值
  • 实现步骤

    1. 通过两个栈,一个数栈存储表达式中的数值,一个符号栈存储表达式中的运算符,通过一个索引遍历表达式
    2. 如果发现是一个数字,直接入数栈
    3. 如果发现是符号栈
      • 如果当前符号栈为空,则直接入符号栈
      • 如果符号栈中有值,就进行比较,如果当前操作符的优先级小于或等于栈中的操作符,则从数栈中pop两个数值,再从符号栈中pop出一个符号,进行运算得到结果;入数栈,然后将当前的操作符入符号栈;如果当前的操作符的优先级大于栈中的操作符,就直接入符号栈
    4. 当表达式扫描完毕,将顺序的从数栈和符号栈中pop出相应的数和符号,并运行
    5. 最后在数栈中只有一个数字,就是表达式

  • 实现

    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
    public class Calculator {
    public static void main(String[] args) {

    // 定义表达式
    String expression = "40+3*17-19";

    // 创建两个栈
    ArrayStack2 numStack = new ArrayStack2(10);
    ArrayStack2 operStack = new ArrayStack2(10);

    // 变量定义
    int index= 0; // 扫描表达式的指针

    int result = 0;

    for (int j = 0; j< expression.toCharArray().length;j++) {
    char c = expression.toCharArray()[j];
    if(operStack.isOper(c)){ // 如果是运算符
    //判断当前符号栈是否为空
    if(operStack.isEmpty()){
    // 符号栈为空 直接将该符号入栈
    operStack.push(c);
    }else{
    // TODO 符号栈不为空
    // TODO 如果当前的操作符的优先级小于或等于栈中的操作符,就需要从数栈中pop两个数
    char o = (char) operStack.peek();
    if(operStack.priority(c) <= operStack.priority(o)){
    // TODO pop两个数进行运算
    int num1 = numStack.pop();
    int num2 = numStack.pop();
    operStack.pop(); // 出队
    result = numStack.cal(num1,num2,o); // TODO 运算
    // TODO 将运算结果入数栈
    numStack.push(result);
    // TODO 将当前的操作符入符号栈
    operStack.push(c);
    }else{
    // TODO 如果当前的从操作符大于栈中的操作符 直接入符号栈
    operStack.push(c);
    }
    }
    }else{
    String str = String.valueOf(c);
    // 如果是数值 直接入数栈
    for (int i = j+1; i <expression.length() ; i++) {
    if(operStack.isOper(expression.toCharArray()[i])){
    break;
    }
    // 下一个不是符号 多位数情况
    str += expression.toCharArray()[i];
    j++; // 跳过下一数的遍历
    }
    numStack.push(Integer.parseInt(str)); // TODO 注意这里要做类型装换
    }
    }


    // TODO 表达式扫描完毕 按顺序计算栈中的值
    while(true){
    // TODO 如果符号栈为空 则计算到最后的结果 数栈中还有一个数字
    if(operStack.isEmpty()){
    break;
    }
    // TODO pop两个数进行运算
    int num1 = numStack.pop();
    int num2 = numStack.pop();
    char o = (char) operStack.pop();

    result = numStack.cal(num1,num2,o); // TODO 运算
    // TODO 将运算结果入数栈
    numStack.push(result);

    }

    System.out.println("结果:" + numStack.pop());
    }
    }


    class ArrayStack2{

    private int maxSize; //栈的大小

    private int[] data; //数组 模拟栈的存储

    private int top = -1; //栈顶


    public ArrayStack2(int maxSize) {
    this.maxSize = maxSize;
    data = new int[maxSize];
    }


    // 判断栈是否满了
    public boolean isFull(){
    // 当栈顶等于 栈的长度-1的时候 说明此栈已满
    return top == maxSize-1;
    }

    // 判断栈是否空了
    public boolean isEmpty(){
    // 栈顶 等于 -1
    return top == -1;
    }

    // 入栈
    public void push(int value){
    //判断是否已满
    if(isFull()){
    // TODO 栈满
    return;
    }
    // 先将指针后移 然后将数据放入该位置 实现入栈
    top++;
    this.data[top] = value;
    }

    // 出栈
    public int pop(){
    // 将栈顶的数据取出
    // 判断栈是否为空
    if(isEmpty()){
    //TODO 栈为空
    throw new RuntimeException("is empty");
    }

    // 取出栈顶的数据
    int num = this.data[top];
    // 指针减一
    top--;
    return num;
    }


    //遍历栈 需要从 栈顶开始显示
    public void list(){
    if(isEmpty()){
    //TODO 栈空
    }
    for (int i = top; i >= 0; i--) {
    System.out.printf("stack[%d]=%d\n",i,this.data[i]);
    }
    }

    // 返回运算符的优先级 优先级用数字表示 数字越大 优先级越高
    public int priority(char oper){
    if(oper == '*' || oper == '/'){
    return 1;
    }else if(oper == '+' || oper == '-'){
    return 0;
    }else {
    // 暂只考虑 加减乘除
    return -1;
    }
    }


    // 判断是不是一个运算符
    public boolean isOper(char value){
    return value == '+' || value == '-' || value == '*' || value == '/';
    }

    // 计算结果
    public int cal(int num1, int num2, char oper){
    int num = 0;
    switch (oper){
    case '+':
    num = num1 + num2;
    break;
    case '-':
    num = num2 - num1;
    break;
    case '*':
    num = num1 * num2;
    break;
    case '/':
    num = num2 / num1;
    break;
    default:
    break;
    }
    return num;
    }


    // 得到栈顶的数据
    public int peek(){
    return this.data[top];
    }
    }
表达式
  • 前缀表达式(波兰表达式)

    • 前缀表达式的运算符位于操作数之前

    • 前缀表达式的计算机求值

      从右至左扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对他们做相应的计算(栈顶元素和次顶元素),并将结果入栈;重复上述过程直到表达式最左端,最后运算得出的值即为表达式的结果

      例:(2+8)*7-2

      • 前缀表达式 :【- * + 2 8 7 2】
      • 从右至左扫描,讲2、7、8、2压入堆栈
      • 遇到+,弹出2、8,运算结果得到10,入栈【10、7、2】
      • 然后再向左扫描,遇到*,弹出10,7,运算结果得到70,入栈【70、2】
      • 最后扫描到-,计算70-2得到结果68,由此得出结果
  • 中缀表达式

    • 中缀表达式就是常见的运算表达式
    • 中缀表达式的求值使我们人最熟悉的,但是对计算机来说却不好操作,因此,在计算结果时,往往会将中缀表达式转成其他表达式来操作(一般转成后缀表达式)
  • 后缀表达式(逆波兰表达式)

    • 后缀表达式又称为逆波兰表达式,与前缀表达式相似,只是运算符位于操作符之后

    • 例:(2+8)*7-2

      • 后缀表达式:【2 8 + 7 * 2 -】

      • | 正常的表达式 | 逆波兰表达式 |
        | ————— | ————- |
        | a + b | a b + |
        | a + (b - c) | a b c - + |
        | a + (b - c) d | a b c - d + |
        | a + d( b - c) | a d b c - + |
        | a = 1 + 3 | a 1 3 + = |

    • 后缀表达式的计算机求值

      从左至右扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对他们做相应的计算(次顶元素和栈顶元素),并将结果入栈;重复上述过程直到表达式最右端,最后运算得出的值即为表达式的结果

      • 从左至有扫描,将2、8、7、2压入堆栈
      • 遇到+号,弹出 2、8运算,将10压栈【10、7、2】
      • 遇到*号,弹出10、7运算,将70压栈【70、2】
      • 遇到-号,弹出70、2运算,结果68
  • 中缀表达式转后缀表达式

    • 后缀表达式适合计算机式进行运算,但是人却不太容易写出来,尤其是表达式很长的情况,因此在开发中,我们需要将中缀表达式转成后缀表达式
      1. 初始化两个栈:运算符栈s1和存储中间结果栈s2;
      2. 从左至右扫描中缀表达式
      3. 遇到数值时,将其压栈s2
      4. 遇到运算符时,比较其与s1栈顶运算符的优先级:
        • 如果s1为空,或栈顶运算符为左括号(,则直接将此运算符入栈;
        • 否则,若优先级比栈顶运算符的高,也将运算符压入s1
        • 否则,将s1栈顶的运算符弹出并压入到s2中,再次转到
    • 中缀转后缀表达式

      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
          //  中缀表达式转后缀表达式
      public static String toConvertSuffix(String infix){
      String[] arr = infix.split(" ");
      List<String> strList = new ArrayList<>();
      for (String s : arr) {
      strList.add(s);
      }

      // TODO 符号栈
      Stack<String> s1 = new Stack<>();
      // TODO 中间结果栈
      Stack<String> s2 = new Stack<>();

      // TODO 扫描中缀表达式
      strList.forEach(item->{
      if(item.matches("\\d+")) { // 数值
      //TODO 压入中间结果栈
      s2.push(item);
      }else {
      // TODO 如果是括号
      if(Objects.equals("(",item) || Objects.equals(")",item)){
      if(Objects.equals("(",item)){
      // TODO 左括号 直接入s1
      s1.push(item);
      }else{
      // TODO 右括号 依次弹出s1栈顶的运算符 入s2 直到遇到左括号为止
      while (!Objects.equals(s1.peek(),"(")){
      s2.push(s1.pop()); // s1 入 s2
      }
      }
      }else{
      boolean flag = false;
      do{
      // TODO 如果是运算符
      if(s1.empty()){
      // TODO 如果s1为空 直接入s1
      s1.push(item);
      flag = false;
      }else{
      // 如果当前符号比s1栈顶运算符的优先级高
      if(comparePriority(item,s1.peek())){
      //TODO 运算符方 入 s1
      s1.push(item);
      flag = false;

      }else{
      // 否则,将s1栈顶的运算符弹出并压入到s2中,在此转到步骤(4-1)中比较
      s2.push(s1.pop());
      flag = true ; // 继续比较

      }
      }
      }while (flag);

      }

      }
      });

      // 扫描结束 s1中入栈s2
      while(!s1.empty()){
      s2.push(s1.pop());
      }

      // 反转
      while(!s2.empty()){
      s1.push(s2.pop());
      }

      String str = "";
      while(!s1.empty()){
      str += s1.pop()+" ";
      }

      return str.trim();
      }
  • 逆波兰表达式求值

    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
    public class PolandNotation {

    public static void main(String[] args) {

    // 为了方便遍历 将普通表达式转换

    String str = "4*5-8+70+12/3";
    String reg = "\\d+";
    String s1 = str.replaceAll(reg, " ");
    String reg2 = "\\D";
    String s2 = str.replaceAll(reg2, " ");
    String[] split1 = s1.trim().split(" ");
    String[] split2 = s2.trim().split(" ");

    System.out.println(split1.length);
    System.out.println(split2.length);


    String infix = "";
    for (int i = 0; i < split1.length; i++) {
    if(Objects.equals("(",split1[i] ) || Objects.equals(")",split1[i])){
    infix += split1[i] + " ";
    }else{
    infix += split2[i] + " " + split1[i] + " ";
    }
    }
    infix = infix + split2[split1.length];
    System.out.println(infix);


    // 转换后的中缀表达式转后缀 开始计算
    String st = infix;
    System.out.println(toConvertSuffix(st));

    // 定义一个逆波兰表达式
    // TODO (2+5)*6-9 --> 2 5 + 6 * 9 -
    // TODO 4*5-8+70+12/3 -->4 5 * 8 - 70 + 12 3 / +
    String express = toConvertSuffix(st);
    String[] arr = express.split(" ");

    List<String> expressList= new ArrayList<>();
    for (String s : arr) {
    expressList.add(s);
    }


    // 运算
    Stack<String> stack = new Stack<>();

    expressList.forEach(item->{
    if(item.matches("\\d+")){ // TODO 匹配多位数
    // 入栈
    stack.push(item);
    }else{
    // TODO pop出俩个数并运算 在运算
    int num1 = Integer.parseInt(stack.pop());
    int num2 = Integer.parseInt(stack.pop());
    int res = 0;
    if(Objects.equals("+",item)){
    res = num1 + num2;
    }else if(Objects.equals("-",item)){
    // 减法要用后入栈的数 减 先入栈的数
    res = num2 - num1;
    }else if(Objects.equals("*",item)){
    res = num1 * num2;
    }else if(Objects.equals("/",item)){
    // 除 将陷入栈的数作为被除数
    res = num2 / num1;
    }
    stack.push(String.valueOf(res));

    }
    });
    Arrays.asList();

    System.out.println(stack.pop());
    }


    // 比较优先级的方法
    public static boolean comparePriority(String symbol1,String symbol2){
    // 将层级划分为两级 +- 0 */ 1
    int symbol1Level = -1;
    int symbol2Level = -1;

    if(Objects.equals(symbol1,"+") || Objects.equals(symbol1,"-")){
    symbol1Level = 0;
    }else if(Objects.equals(symbol1,"*") || Objects.equals(symbol1,"/")){
    symbol1Level = 1;
    }

    if(Objects.equals(symbol2,"+") || Objects.equals(symbol2,"-")){
    symbol2Level = 0;
    }else if(Objects.equals(symbol2,"*") || Objects.equals(symbol2,"/")){
    symbol2Level = 1;
    }

    return symbol1Level > symbol2Level;

    }
    }
-------------本文结束感谢您的阅读-------------
既然来了就打个赏吧= =
0%