栈与队列

发表于|更新于|数据结构
字数总计:6.6k|阅读时长:28分钟|阅读量:…
文章最后更新于 1400 天前，其中的信息可能已经过时。

本篇文章将详细讲述数据结构 栈与队列 章节的内容。

本教程编程语言采用 JAVA ,文章框架参考自 HUST数据结构PPT ,源码内容参考自 尚硅谷 JAVA 数据结构教程 。

栈与队列章节部分概念方面比较简单，将放在具体的代码实现过程中。

栈的定义与操作

定义与术语

栈的基本操作

  1. Initstack(s) // 置 s 为空栈
  2. Push(s,e) // 元素 e 进栈 s
  3. Pop(s,e // 元素 e 出栈 s
  4. Gettop(s,e) // 顶元素拷贝到 e
  5. Empty(s) // 判断是否为空栈

栈的应用场景：

  • 子程序的调用: 在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中。 如方法中调用方法。
  • 处理递归调用: 和子程序调用类似，只是除了存储下一个指令的地址外，也将参数、区域变量等数据存入堆栈中。
  • 表达式的转换（中缀表达式转后缀表达式）与求值（实际解决）
  • 二叉树的遍历
  • 图形的深度优先（depth-first）搜索法

栈的存储表示和操作实现

顺序栈（用数组来模拟栈）

  1. 实现思路

    1. 定义一个数组，来模拟栈。
    2. 定义一个top变量表示栈顶，初始化为-1。
    3. 入栈：stack[++top] = data
    4. 出栈：return stack[top--]

  2. 代码实现

    查看代码实现
    1. 编写ArrayStack类
    JAVA
    package DataStructure.Stack;
    

    public class ArrayStack {
     // 定义三个基本属性，堆栈，堆栈的大小，栈顶元素
     int[] stack;
     int maxSize;
     int top = -1;
    

     // 构造函数书写
     public ArrayStack(int maxSize) {
         this.maxSize = maxSize;
         stack = new int[maxSize];
     }
    

     // 判断堆栈是否已满，判断top是否到了最后一个元素
     public boolean isFull() {
         return top == maxSize - 1;
     }
    

     // 判断堆栈是否为空，即判断top的值是否等于-1
     public boolean isEmpty() {
         return top == -1;
     }
    

     // 入栈函数书写，先判断是否为满再入栈
     public void push(int element) {
         if (isFull()) {
             System.out.println("Stack full!");
             return;
         }
         stack[++top] = element;
     }
    

     // 出栈函数书写，先判断是否为空再出栈
     public int pop() {
         if (isEmpty()) {
             throw new RuntimeException("No data in stack!");
         }
         return stack[top--];
     }
    

     // 打印栈中元素
     public void print() {
         if (isEmpty()) {
             System.out.println("No data in stack!");
             return;
         }
         for (int i = top; i >= 0; i--) {
             System.out.printf("index=%d value=%d \n", i, stack[i]);
         }
     }
    }
    1. 编写测试函数
    JAVA
    package DataStructure.Stack;
    

    import org.junit.Test;
    

    public class ArrayStackTest {
     @Test
     public void pushTest() {
         ArrayStack stack = new ArrayStack(4);
         stack.push(1);
         stack.push(2);
         stack.push(3);
         stack.push(4);
         stack.print();
         stack.push(5);
     }
    

     @Test
     public void popTest() {
         ArrayStack stack = new ArrayStack(4);
         stack.push(1);
         stack.push(2);
         stack.print();
         System.out.println("pop data:" + stack.pop());
         stack.print();
         System.out.println("pop data:" + stack.pop());
         stack.print();
     }
    }
    1. 测试结果
    Terminal window
    pushTest:
    index=3 value=4
    index=2 value=3
    index=1 value=2
    index=0 value=1
    Stack full!
    

    popTest:
    index=1 value=2
    index=0 value=1
    pop data:2
    index=0 value=1
    pop data:1
    No data in stack!

链式栈（用链表来模拟栈）

  1. 实现思路

  2. 定义一个链表来模拟栈，成员变量有：

    • 最大存储量: maxSize
    • 栈中元素个数: size
    • 栈顶元素（同时作为表头）: top

  3. 入栈: Node temp = top; top = new Node(value); top.next = temp; size++;

  4. 出栈 Node temp = top; top = top.next size--; return temp.value;

  5. 代码实现

    查看代码实现
    1. 编写LinkedListStack类
    JAVA
    package DataStructure.Stack;
    

    public class LinkedListStack {
     // 构造三个基本属性
     int maxSize; // 栈中最多的元素
     int size; // 栈中现在具有的元素
     Node top; // 栈顶的元素
    

     // 构造函数
     public LinkedListStack(int maxSize) {
         this.maxSize = maxSize;
     }
    

     // 判断栈是否为满的元素
     public boolean isFull() {
         return size == maxSize;
     }
    

     // 判断栈是否为空的元素
     public boolean isEmpty() {
         return size == 0;
     }
    

     // 入栈函数，先判断是否为满，再将元素添加到链表的表头
     public void push(int value) {
         if (isFull()) {
             System.out.println("Stack full!");
             return;
         }
         // 储存top元素
         Node temp = top;
         // 更新top节点
         top = new Node(value);
         // 指向前一top节点
         top.next = temp;
         // 储存元素个数自增
         size++;
     }
    

     // 出栈函数书写
     public int pop() {
         if (isEmpty()) {
             throw new RuntimeException("Stack empty!");
         }
         Node temp = top;
         top = top.next; // 注意已经存在的变量加上int会新创建变量
         size--;
         return temp.value;
     }
    

     // 显示栈中的元素
     public void print() {
         if (isEmpty()) {
             System.out.println("Stack empty!");
             return;
         }
         Node cur = top;
         while (cur != null) {
             System.out.println(cur);
             cur = cur.next;
         }
     }
    }
    

    class Node {
     // 定义节点的两个基本属性
     int value;
     Node next;
    

     // 书写构造函数
     public Node(int value) {
         this.value = value;
     }
    

     // 重写toString函数
     @Override
     public String toString() {
         return "Node{" +
                 "value=" + value +
                 '}';
    

     }
    }
    1. 编写测试函数
    JAVA
    package DataStructure.Stack;
    

    import org.junit.Test;
    

    public class LinkedListStackTest {
     @Test
     public void pushTest() {
         LinkedListStack stack = new LinkedListStack(4);
         stack.push(1);
         stack.push(2);
         stack.push(3);
         stack.push(4);
         stack.print();
         stack.push(5);
     }
    

     @Test
     public void popTest() {
         LinkedListStack stack = new LinkedListStack(4);
         stack.push(1);
         stack.push(2);
         stack.print();
         System.out.println("pop data:" + stack.pop());
         stack.print();
         System.out.println("pop data:" + stack.pop());
         stack.print();
     }
    }
    1. 测试结果
    Terminal window
    pushTest；
    Node{value=4}
    Node{value=3}
    Node{value=2}
    Node{value=1}
    Stack full!
    

    popTest；
    Node{value=2}
    Node{value=1}
    pop data:2
    Node{value=1}
    pop data:1
    Stack empty!

栈的应用

栈的一个十分经典的应用就是计算机如何计算表达式。

中缀表达式

  1. 基本概念 中缀表达式是一个通用的 算术 或 逻辑公式表示方法 。 操作符 是以 中缀形式 处于操作数的 中间 （例： 3 + 4 ），中缀表达式是人们常用的算数表达方式。

    中缀表达式就是 常见的运算表达式，如 (3+4)x5-6。 中缀表达式的求值是人类最熟悉的，但是对于计算机来说却不好操作：

    • 需要计算运算符的优先级
    • 对于中括号来说，笔者想不出实现办法 因此，在计算结果时，往往会将 中缀表达式 转成其他表达式，一般转成后缀表达式。

  2. 思路分析

  3. 代码实现

    如上图，代码实现的基本思路为：

    1. 先扫描字符串，可以通过一个 index 变量来辅助扫描。
    2. 如果发现是一个 数字 ，直接入栈。
    3. 如果发现是一个 操作符 ，分一下情况：
    4. 当 当前操作符 的优先级 大于栈顶符号 ：将 当前操作符 入符号栈。
    5. 当 当前操作符 的优先级 小于或等于栈顶符号 ：
      1. 弹出数栈中的 2 个数值。
      2. 弹出符号栈顶的元素。
      3. 2 个数字与符号进行运算。
      4. 将计算结果压入数栈。
      5. 将当前操作符压入符号栈。
    6. 当扫描完毕时：
    7. 顺序地从数栈中弹出 2 个数。
    8. 从符号栈中弹出 1 个操作符。
    9. 将他们进行计算，然后把计算结果压入数栈中。
    10. 最后数栈中只会存在一个数值，那就是计算结果。
    查看代码实现
    1. 使用前面实现的数组栈来做我们的容器，只增加了一个查看栈顶元素的peek()方法。
    JAVA
    package DataStructure.Stack;
    

    public class ArrayStack {
     // 定义三个基本属性，堆栈，堆栈的大小，栈顶元素
     int[] stack;
     int maxSize;
     int top = -1;
    

     // 构造函数书写
     public ArrayStack(int maxSize) {
         this.maxSize = maxSize;
         stack = new int[maxSize];
     }
    

     // 判断堆栈是否已满，判断top是否到了最后一个元素
     public boolean isFull() {
         return top == maxSize - 1;
     }
    

     // 判断堆栈是否为空，即判断top的值是否等于-1
     public boolean isEmpty() {
         return top == -1;
     }
    

     // 入栈函数书写，先判断是否为满再入栈
     public void push(int element) {
         if (isFull()) {
             System.out.println("Stack full!");
             return;
         }
         stack[++top] = element;
     }
    

     // 出栈函数书写，先判断是否为空再出栈
     public int pop() {
         if (isEmpty()) {
             throw new RuntimeException("No data in stack!");
         }
         return stack[top--];
     }
    

     // 打印栈中元素
     public void print() {
         if (isEmpty()) {
             System.out.println("No data in stack!");
             return;
         }
         for (int i = top; i >= 0; i--) {
             System.out.printf("index=%d value=%d \n", i, stack[i]);
         }
     }
    

     // 添加显示栈顶元素的方法
     public int peek() {
         if (isEmpty()) {
             throw new RuntimeException("Stack empty!");
         }
         return stack[top];
     }
    }
    1. 计算器代码实现
    JAVA
    package DataStructure.Stack;
    

    /**
    * 计算器代码实现
    */
    public class Calculator {
     // 使用前面章节实现过的 数组模拟栈，来当我们 计算器中用来存储数据和符号的 容器
     private ArrayStack numStack = new ArrayStack(10); // 数组栈
     private ArrayStack operStack = new ArrayStack(10); // 符号栈
    

     public static void main(String[] args) {
         String expression = "30-2*4+2";
    

         Calculator calculator = new Calculator();
         // 扫描表达式
         calculator.scan(expression);
         // 剩余数据进行计算
         int res = calculator.nextCal();
         System.out.printf("%s = %d \n", expression, res);
     }
    

     public void scan(String expression) {
         int index = 0;
         String keepNum = ""; // 用来保存数字，有可能是 = "1" 或则 "123" 的多位数
         while (true) {
             if (index == expression.length()) {
                 break;
             }
             // 每次只截取一个数字
             // 要注意这里的 ch，使用 ch 做运算的时候要小心
             char ch = expression.substring(index, ++index).charAt(0);
             if (isOper(ch)) {
                 subScan(ch);
             } else {
                 // 是数字，直接入数栈
                 // ch 被当成 int 的使用的话，需要特别注意
                 // ASCII 码表中数字是从 48 开始的，这里的 ch 对应的数字是 ASCII 码表，所以要减掉 48
                 // 当然也可以使用字符串解析的方式 Integer.valueOf(字符串) 来得到数字
                 // numStack.push(ch - 48);
                 keepNum += ch;
                 // 已经是末尾了，则直接入栈
                 if (index == expression.length()) {
                     numStack.push(Integer.parseInt(keepNum));
                     continue;
                 }
                 // 需要往后多看一位,如果是符号，才能将当前的数入栈
                 char tempCh = expression.substring(index, index + 1).charAt(0);
                 if (isOper(tempCh)) {
                     numStack.push(Integer.parseInt(keepNum));
                     keepNum = "";
                 }
             }
         }
     }
    

     public void subScan(char ch) {
         // 当 当前操作符 的优先级 大于 栈顶符号：将 当前操作符入符号栈
         // 一定要大于，如果是同级的话，有可能前面一个也是 * 号，需要先在第一步进行计算
         if (operStack.isEmpty() || priority(ch) > priority((char) operStack.peek())) {
             operStack.push(ch);
             return;
         }
         // 小于栈顶操作符，则将栈顶符号取出，进行计算
         int num1 = numStack.pop();
         int num2 = numStack.pop();
         int oper = operStack.pop();
         int res = cal(num1, num2, oper);
         // 将结果入数栈
         numStack.push(res);
         // 递归调用
         subScan(ch);
     }
    

     /**
      * 第 2 步：从栈中取出来数据和符号，然后计算
      *
      * @return
      */
     private int nextCal() {
         System.out.println("符号栈中符号情况：");
         operStack.print();
         while (true) {
             // 当符号栈为空时，表示已经计算完了
             if (operStack.isEmpty()) {
                 break;
             }
             int num1 = numStack.pop();
             int num2 = numStack.pop();
             int oper = operStack.pop();
             int res = cal(num1, num2, oper);
             // 将结果入数栈
             numStack.push(res);
         }
         // 计算完成之后，数栈中只有一个数据了，就是结果
         System.out.println("栈中数据是否只有一个结果数字：");
         numStack.print();
         return numStack.pop();
     }
    

     /**
      * 计算
      *
      * @param num1 依次从栈顶弹出来的数据
      * @param num2
      * @param oper 操作符
      * @return
      */
     private int cal(int num1, int num2, int oper) {
         switch (oper) {
             case '+':
                 return num1 + num2;
             case '-':
                 // 注意顺序，在栈底的数据，是先进去的，如果是减法，则是前面的数字减后面的数字
                 return num2 - num1;
             case '*':
                 return num1 * num2;
             case '/':
                 return num2 / num1;
         }
         // 由于前面校验过操作符，不会走到这里来的
         return 0;
     }
    

     /**
      * 计算操作符号优先级，暂时只支持 + - * /
      *
      * @param ch
      * @return 优先级越高，数值越大
      */
     private int priority(char ch) {
         switch (ch) {
             case '+':
             case '-':
                 return 0;
             case '*':
             case '/':
                 return 1;
             default:
                 return -1;
         }
     }
    

     /**
      * 是否是操作符
      *
      * @param ch
      * @return
      */
     private boolean isOper(char ch) {
         switch (ch) {
             case '+':
             case '-':
             case '*':
             case '/':
                 return true;
         }
         return false;
     }
    }

后缀表达式

后缀表达式 又称为 逆波兰表达式 ，与前缀表达式类似，只是 运算符 位于 操作数 之后。

  1. 后缀表达式求值过程：

    1. 从 左到右 扫描表达式。
    2. 遇到 数字 时，将数字压入堆栈。
    3. 遇到 符号 时，将数字栈栈顶和次顶元素弹出，计算顺序为 次顶元素（符号）栈顶元素。
    4. 重复上述过程直至剩余最后一个结果。

  2. 中缀表达式转后缀表达式

    1. 初始化两个栈
    • 符号栈 s1
    • 中间结果栈 s2
    1. 从左到右扫描中缀表达式
    2. 遇到操作数直接压入 s2
    3. 遇到运算符时
      1. 若 s1 为空，或者栈顶元素符号位 ( ，则将其压入符号栈 s1
      2. 若优先级比栈顶运算符 高 ，也将其压入符号栈 s1
      3. 若优先级比栈顶运算符 低或者相等 ，则弹出 s1栈顶元素，将其压入 s2 中，然后继续循环步骤 4，直至当前符号压入 s1
    4. 遇到括号时
      1. 如果是左括号 (：直接压入 s1
      2. 如果是右括号 )： 则依次弹出 s1栈顶的运算符，并压入 s2 直到遇到 左括号 为止，此时将这一对括号 丢弃
    5. 重复步骤 2 到 5 ，直到表达式的最右端
    6. 将 s1 的运算符依次弹出并压入 s2 ，结果的 逆序 即为：中缀表达式转后缀表达式的结果

  3. 中缀表达式转后缀表达式的举例说明

    查看举例

    将中缀表达式：1+((2+3)*4)-5转化为后缀表达式

    扫描到的元素 s2（栈底->栈顶） s1（栈底->栈顶） 说明
    1 1 null 遇到操作数直接压入 s2
    + 1 + s1为空，直接压入
    ( 1 + ( 运算符为(，直接压入
    ( 1 + ( ( 运算符为(，直接压入
    2 1 2 + ( ( 遇到操作数直接压入 s2
    + 1 2 + ( ( + 栈顶元素为(，直接压入 s1
    3 1 2 3 + ( ( + 遇到操作数直接压入 s2
    ) 1 2 3 + + ( 遇到)时，依次弹出 s1栈顶的运算符，并压入 s2 直到遇到 左括号 为止，此时将这一对括号 丢弃
    * 1 2 3 + + ( * 栈顶元素为(，直接压入s1
    4 1 2 3 + 4 + ( * 遇到操作数直接压入 s2
    ) 1 2 3 + 4 * + 遇到)时，依次弹出 s1栈顶的运算符，并压入 s2 直到遇到 左括号 为止，此时将这一对括号 丢弃
    - 1 2 3 + 4 * + - 优先级比栈顶运算符 低或者相等 ，则弹出 s1栈顶元素，将其压入 s2 中，然后继续循环步骤 4，直至当前符号压入 s1
    5 1 2 3 + 4 * + 5 - 遇到操作数直接压入 s2
    null 1 2 3 + 4 * + 5 - null 将 s1 的运算符依次弹出并压入 s2 ，结果的 逆序 即为：中缀表达式转后缀表达式的结果

  4. 代码实现

    查看代码实现
    1. 逆波兰表达式的计算器

    实现思路：

    1. 先将后缀表达式转化为一个 List
    2. 对这个 List 进行遍历然后进行计算
    JAVA
    package DataStructure.Stack;
    

    import java.util.Arrays;
    import java.util.List;
    import java.util.Stack;
    

    public class ReversePolishCalculator {
     public static void main(String[] args) {
         ReversePolishCalculator calculator = new ReversePolishCalculator();
    

         // (3+4)*5-6 => 对应的后缀表达式 `3 4 + 5 * 6 -`
         String postfixExpression = "3 4 + 5 * 6 -";
         System.out.println("(3+4)*5-6 = " + calculator.cal(postfixExpression));
    

         // (30+4)*5-6 => 对应的后缀表达式 `30 4 + 5 * 6 -`
         postfixExpression = "30 4 + 5 * 6 -";
         System.out.println("(30+4)*5-6 = " + calculator.cal(postfixExpression));
    

         // 4*5-8+60+8/2 => 对应的后缀表达式 `4 5 * 8 - 60 + 8 2 / +`
         postfixExpression = "4 5 * 8 - 60 + 8 2 / +";
         System.out.println("4*5-8+60+8/2 = " + calculator.cal(postfixExpression));
    

         // (3+4)-(3-4)*10，对应后缀表达式为：3 4 + 10 3 4 - * -
         postfixExpression = "3 4 + 10 3 4 - * -";
         System.out.println("(3+4)-(3-4)*10 = " + calculator.cal(postfixExpression));
     }
    

     /**
      * 计算一个后缀表达式的值
      *
      * @param postfixExpression
      * @return
      */
     public int cal(String postfixExpression) {
         return start(convert(postfixExpression));
     }
    

     /**
      * 将后缀表达式转换成 list
      *
      * @param postfixExpression 表达式中的每个元素都用空格隔开，是为了方便；这里重点不在于怎么去解析出每一个元素了
      * @return
      */
     private List<String> convert(String postfixExpression) {
         return Arrays.asList(postfixExpression.split(" "));
     }
    

     /**
      * 计算
      *
      * @param postfixElements
      * @return
      */
     private int start(List<String> postfixElements) {
         /*
          * 比如：`(3+4)x5-6` 对应的后缀表达式 `3 4 + 5 x 6 -`
          * 1. 从左到右扫描，将 3、4 压入堆栈
          * 2. 扫描到 `+` 运算符时
          * 将弹出 4 和 3，计算 `3 + 4 = 7`，将 7 压入栈
          * 3. 将 5 入栈
          * 4. 扫描到 `x` 运算符时
          * 将弹出 5 和 7 ，计算 `7 x 5 = 35`，将 35 入栈
          * 5. 将 6 入栈
          * 6. 扫描到 `-` 运算符时
          * 将弹出 6 和 35，计算 `35 - 6 = 29`，将 29 压入栈
          * 7. 扫描表达式结束，29 是表达式的值
          */
         Stack<Integer> stack = new Stack<>();
         for (String el : postfixElements) {
             // 如果是数字则入栈
             if (el.matches("\\d+")) {
                 stack.push(Integer.parseInt(el));
                 continue;
             }
             // 是运算符，则弹出两个数
             Integer num2 = stack.pop();
             Integer num1 = stack.pop();
             int res = cal(num1, num2, el.charAt(0));
             stack.push(res);
         }
         return stack.pop();
     }
    

     /**
      * 计算
      *
      * @param num1
      * @param num2
      * @param oper 操作符
      * @return
      */
     private int cal(int num1, int num2, char oper) {
         switch (oper) {
             case '+':
                 return num1 + num2;
             case '-':
                 return num1 - num2;
             case '*':
                 return num1 * num2;
             case '/':
                 return num1 / num2;
         }
         throw new IllegalArgumentException("不支持的运算符：" + oper);
     }
    

    }
    1. 中缀表达式转后缀表达式代码实现
    JAVA
    package DataStructure.Stack;
    

    import java.util.ArrayList;
    import java.util.List;
    import java.util.Stack;
    

    /**
    * 中缀表达式转后缀表达式
    */
    public class InfixToSuffix {
     public static void main(String[] args) {
         InfixToSuffix infixToSuffix = new InfixToSuffix();
         // 目标：1+((2+3)*4)-5 转为 1 2 3 + 4 * + 5 -
         // 1. 将中缀表达式转成 List，方便在后续操作中获取数据
         String infixExpression = "1+((2+3)*4)-5";
         List<String> infixList = infixToSuffix.infix2List(infixExpression);
         System.out.println(infixList); // [1, +, (, (, 2, +, 3, ), *, 4, ), -, 5]
         // 2. 将中缀表达式转成后缀表达式
         ArrayList<String> suffixList = infixToSuffix.infixList2SuffixList(infixList);
         System.out.println(suffixList); // [1, 2, 3, +, 4, *, +, 5, -]
     }
    

     /**
      * 将中缀表达式解析成单个元素的 List，
      *
      * @param infixExpression
      * @return 1+((2+3)*4)-5 -> [1,+,(,(,2,+,3,),*,4,),5]
      */
     public List<String> infix2List(String infixExpression) {
         ArrayList<String> res = new ArrayList<>();
         // 扫描并解析
         int index = 0;
         char ch = 0;
         String tempNum = ""; // 支持多位数
         while (index < infixExpression.length()) {
             ch = infixExpression.charAt(index++);
             // 如果不是数字，就是符号，直接添加到容器中
             // 0 = 48, 9 = 57
             if (!(ch >= 48 && ch <= 57)) {
                 // 如果拼接的多位数还有值，则添加到容器中
                 if (!tempNum.isEmpty()) {
                     res.add(tempNum);
                     tempNum = "";
                 }
                 res.add(ch + "");
                 continue;
             }
             // 如果是数字，则考虑处理多位数
             tempNum += ch;
             // 如果已经是最后一个字符了，则将这个多位数添加到容器中
             if (index == infixExpression.length()) {
                 res.add(tempNum);
                 tempNum = "";
             }
         }
         return res;
     }
    

     /**
      * 中缀表达式 List 转为后缀表达式 List
      *
      * @param infixList
      * @return
      */
     private ArrayList<String> infixList2SuffixList(List<String> infixList) {
         // 符号栈
         Stack<String> s1 = new Stack<>();
         // 思路是使用栈来存储表达式元素
         // 仔细观察他的解析步骤，会发现：只是在入栈，并未出现出栈操作
         // 而且，最后的结果还要逆序，所以这里使用 list，直接顺序读取出来就是最后的结果了
         ArrayList<String> s2 = new ArrayList<>();
    

         for (String item : infixList) {
             // 如果是数字，则加入 s2
             if (item.matches("\\d+")) {
                 s2.add(item);
             }
             // 如果是左括号，直接压入 s1
             else if (item.equals("(")) {
                 s1.push(item);
             }
             // 如果是右括号
             // 则依次弹出 s1 栈顶的运算符，并压入 s2，直到遇到 左括号 为止，此时将这一对括号 丢弃
             else if (item.equals(")")) {
                 // 如果不是左括号，则取出 s1 中的符号，添加到 s2 中
                 while (!s1.peek().equals("(")) {
                     s2.add(s1.pop());
                 }
                 // 上面循环完之后，那么就是遇到了左括号
                 // 则直接弹出这个左括号丢弃
                 s1.pop();
             }
             // 剩下的则是运算符
             else {
                 // 如果 s1 为空，或则栈顶运算符为 （，则压入符号栈 s1
                 // 如果优先级比栈顶运算符 高，则压入符号栈 s1,否则，否则将 s1 栈顶的运算符弹出，压入 s2 中
                 // 上面两句话，转换成下面的描述
                 // 上面如果 s1 栈顶符号优先级比 当前符号高，则弹出加入到 s2 中。
                 // 因为：如果栈顶符号是 （ 返回优先级为 -1.比当前符号低，则不会走该方法
                 while (!s1.isEmpty() && priority(s1.peek().charAt(0)) >= priority(item.charAt(0))) {
                     s2.add(s1.pop());
                 }
                 s1.push(item);
             }
         }
         // 将 s1 中的运算符依次弹出并加入 s2 中
         while (!s1.isEmpty()) {
             s2.add(s1.pop());
         }
         return s2;
     }
    

     /**
      * 计算操作符号优先级，暂时只支持 + - * /
      *
      * @param ch
      * @return 优先级越高，数值越大
      */
     private int priority(char ch) {
         switch (ch) {
             case '+':
             case '-':
                 return 0;
             case '*':
             case '/':
                 return 1;
             default:
                 return -1;
         }
     }
    }

前缀表达式

  1. 前缀表达式又称 波兰表达式 ，前缀表达式的 运算符位于操作数之前。

  2. 前缀表达式求值过程：

    1. 从 右到左 扫描表达式。
    2. 遇到 数字 将数字压入栈。
    3. 遇到 符号 弹出数字栈的两个元素，与运算符计算，顺序为： 先 弹出的 （符号） 后 弹出的。
    4. 重复上述过程直至剩余最后一个结果。

  3. 中缀表达式转前缀表达式

    查看思路

    (1) 初始化两个栈：运算符栈 S1 和储存中间结果的栈 S2； (2) 从右至左扫描中缀表达式； (3) 遇到操作数时，将其压入 S2； (4) 遇到运算符时，比较其与 S1 栈顶运算符的优先级： (4-1) 如果 S1 为空，或栈顶运算符为右括号“)”，则直接将此运算符入栈； (4-2) 否则，若优先级比栈顶运算符的较高或相等，也将运算符压入 S1； (4-3) 否则，将 S1 栈顶的运算符弹出并压入到 S2 中，再次转到(4-1)与 S1 中新的栈顶运算符相比较； (5) 遇到括号时： (5-1) 如果是右括号“)”，则直接压入 S1； (5-2) 如果是左括号“(”，则依次弹出 S1 栈顶的运算符，并压入 S2，直到遇到右括号为止，此时将这一对括号丢弃； (6) 重复步骤(2)至(5)，直到表达式的最左边； (7) 将 S1 中剩余的运算符依次弹出并压入 S2； (8) 依次弹出 S2 中的元素并输出，结果即为中缀表达式对应的前缀表达式。

    值得注意的是 s2 输出结果 不需要 逆序

    代码实现思路与后缀表达式类似，且使用情况较少，故不再详细讲述。

队列

基本概念

  1. 队列：是一个 有序列表 ，可以用 数组 或 链表 来实现。
  2. 特点：遵循 先入先出 的原则。 示意图示意图

数组模拟队列

声明 4 个变量：

  • arr：用来储存数据的数组
  • maxSize：该队列的最大容量
  • front：队首下标，随着数据输出而改变
  • rear：队尾下标，随着数据输入二改变

队列中常用操作分析，以 add ，把数据存入队列为例，思路分析：

  1. 存入数据后将尾指针往后移：rear + 1，前提是当 front == rear时，队列是空的
  2. 若尾指针rear < maxSize - 1：
    • 则将数据存入rear所指的数组元素中
    • 否则无法存入数据，rear = maxSize - 1表示队列满了
查看代码实现
JAVA
package DataStructure;


public class Queue {
    /*
     * 主函数：
     * 添加队列元素与展示队列元素
     */
    public static void main(String[] args) {
        ArrayQueue queue = new ArrayQueue(3);
        queue.add(1);
        queue.add(2);
        queue.add(3);
        System.out.println("查看队列中的数据：");
        queue.show();
        System.out.println("查看队列头数据：" + queue.head());
        System.out.println("查看队列尾数据：" + queue.tail());
        System.out.println("获取队列的数据：" + queue.get());
        System.out.println("查看队列中的数据：");
        queue.show();
    }
}


class ArrayQueue {
    // 确定队列的4个基本属性,使用private修饰符修饰成员变量
    private int maxSize;
    private int front;
    private int rear;
    private int arr[];


    // 创建队列，初始化成员变量,使用构造函数创建
    public ArrayQueue(int arrMaxSize) {
        maxSize = arrMaxSize;
        arr = new int[maxSize];
        front = -1;
        rear = -1;
    }


    // 取出队列的数据,同时使用isEmpty来判断队列是否为空
    public int get() {
        if (isEmpty()) {
            throw new RuntimeException("队列空");
        }
        return arr[++front];
    }


    // 往队列中放入数据，用isFull来判断队列是否已满
    public void add(int n) {
        if (isFull()) {
            System.out.println("队列已满！");
            return;
        }
        arr[++rear] = n;
    }


    // 显示队列中的数据,判断不为空之后采用循环遍历的方式显示数据
    public void show() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空");
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.printf("arr[%d]: %d\n", i, arr[i]);
        }
    }


    // 取出队头元素
    public int head() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空");
        }
        return arr[front + 1];
    }


    // 取出队尾元素
    public int tail() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空");
        }
        return arr[rear];
    }


    private boolean isFull() {
        return rear == maxSize - 1;
    }


    private boolean isEmpty() {
        return rear == front;
    }


}

循环队列

基本思路：

  1. front:队列的第一个元素
  2. rear:队列最后一个元素的下一个位置
  3. 队列 满 计算公式：(rear + 1) % maxSize == front
  4. 队列 空 计算公式：rear == front
  5. 队列中 有效元素个数 计算公式：(rear + maxSize -front) % maxSize
查看代码实现
JAVA
package DataStructure;


import java.util.Scanner;


public class CircleQueueDemo {
 // 写一个主函数内部写一个控制台输入的小程序
 public static void main(String[] args) {
     CircleQueue queue = new CircleQueue(3);


     Scanner scanner = new Scanner(System.in);
     boolean loop = true;
     char key = ' ';
     System.out.println("s(show): 显示队列");
     System.out.println("e(exit): 退出程序");
     System.out.println("a(add): 添加数据到队列");
     System.out.println("g(get): 从队列取出数据");
     System.out.println("h(head): 查看队列头的数据");
     System.out.println("t(tail): 查看队列尾的数据");
     System.out.println("p(isEmpty): 队列是否为空");
     while (loop) {
         key = scanner.next().charAt(0);
         switch (key) {
             case 's':
                 queue.show();
                 break;
             case 'e':
                 loop = false;
                 break;
             case 'a':
                 System.out.println("请输入要添加到队列中的整数：");
                 int value = scanner.nextInt();
                 queue.add(value);
                 break;
             case 'g':
                 try {
                     int res = queue.get();
                     System.out.printf("取出的数据是：%d\n", res);
                 } catch (Exception e) {
                     System.out.println(e.getMessage());
                 }
                 break;
             case 'h':
                 try {
                     int res = queue.head();
                     System.out.println("队头数据为：" + res);
                 } catch (Exception e) {
                     System.out.println(e.getMessage());
                 }
                 break;
             case 't':
                 try {
                     int res = queue.tail();
                     System.out.println("队尾数据为：" + res);
                 } catch (Exception e) {
                     System.out.println(e.getMessage());
                 }
                 break;
             case 'p':
                 System.out.printf("队列是否为空：%s", queue.isEmpty());
                 break;
         }
     }
 }
}


// 开始编写环形队列这个类
class CircleQueue {
 // 使用私有变量储存四个基本属性
 private int maxSize;
 private int front;
 private int rear;
 private int[] arr;


 // 初始化环形队列
 public CircleQueue(int arrMaxSize) {
     maxSize = arrMaxSize + 1; // 此处+1是因为需要给rear留出空的储存空间
     front = 0;
     rear = 0;
     arr = new int[maxSize];
 }


 // 取出队列的数据
 public int get() {
     if (isEmpty()) {
         throw new RuntimeException("队列空");
     }
     int value = arr[front];
     front = (front + 1) % maxSize;
     return value;
 }


 // 往队列中储存数据
 public void add(int n) {
     if (isFull()) {
         System.out.println("队列已满");
         return;
     }
     arr[rear] = n;
     rear = (rear + 1) % maxSize;
 }


 // 显示队列中的数据
 public void show() {
     if (isEmpty()) {
         System.out.println("队列为空");
         return;
     }
     for (int i = front; i < front + size(); i++) {
         int index = i % maxSize;
         System.out.printf("arr[%d] = %d\n", index, arr[index]);
     }
 }


 public int head() {
     if (isEmpty()) {
         throw new RuntimeException("队列空");
     }
     return arr[front];
 }


 public int tail() {
     if (isEmpty()) {
         throw new RuntimeException("队列空");
     }
     return rear - 1 < 0 ? arr[maxSize - 1] : arr[rear - 1];
 }


 private boolean isFull() {
     return (rear + 1) % maxSize == front;
 }


 public boolean isEmpty() {
     return rear == front;
 }


 public int size() {
     return (rear + maxSize - front) % maxSize;
 }
}
文章作者:
希亚的西红柿
版权声明:
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自希亚的西红柿のBlog！
数据结构栈队列

相关推荐

2024-03-03LeetCode 算法笔记 Part3 2024-02-26LeetCode 算法笔记 Part2 2024-02-25LeetCode 算法笔记 Part1 2023-12-11数据结构与算法笔记 2022-12-24线性表 2022-09-27数据结构绪论

评论

评论加载中…

站内搜索