栈与队列 | 希亚的西红柿のBlog

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

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

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

栈的定义与操作

定义与术语

栈的基本操作

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

栈的应用场景：

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

栈的存储表示和操作实现

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

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

代码实现

查看代码实现

编写ArrayStack类

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]);
        }
    }
}

编写测试函数

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();
    }
}

测试结果

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!

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

实现思路
定义一个链表来模拟栈，成员变量有：
- 最大存储量: maxSize
- 栈中元素个数: size
- 栈顶元素（同时作为表头）: top
入栈:
Node temp = top;
top = new Node(value);
top.next = temp;
size++;
出栈
Node temp = top;
top = top.next
size--;
return temp.value;

代码实现

查看代码实现

编写LinkedListStack类

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 +
                '}';

    }
}

编写测试函数

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();
    }
}

测试结果

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!

栈的应用

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

中缀表达式

基本概念
中缀表达式是一个通用的算术或 逻辑公式表示方法 。 操作符 是以 中缀形式 处于操作数的中间（例： 3 + 4 ），中缀表达式是人们常用的算数表达方式。
中缀表达式就是常见的运算表达式，如 (3+4)x5-6。
中缀表达式的求值是人类最熟悉的，但是对于计算机来说却不好操作：
- 需要计算运算符的优先级
- 对于中括号来说，笔者想不出实现办法
  因此，在计算结果时，往往会将中缀表达式转成其他表达式，一般转成后缀表达式。
思路分析

代码实现

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

先扫描字符串，可以通过一个 index 变量来辅助扫描。
如果发现是一个数字，直接入栈。
如果发现是一个 操作符 ，分一下情况：
1. 当 当前操作符 的优先级 大于栈顶符号 ：将 当前操作符 入符号栈。
2. 当 当前操作符 的优先级 小于或等于栈顶符号 ：
  1. 弹出数栈中的 2 个数值。
  2. 弹出符号栈顶的元素。
  3. 2 个数字与符号进行运算。
  4. 将计算结果压入数栈。
  5. 将当前操作符压入符号栈。
当扫描完毕时：
1. 顺序地从数栈中弹出 2 个数。
2. 从符号栈中弹出 1 个操作符。
3. 将他们进行计算，然后把计算结果压入数栈中。
最后数栈中只会存在一个数值，那就是计算结果。

查看代码实现

使用前面实现的数组栈来做我们的容器，只增加了一个查看栈顶元素的peek()方法。

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];
    }
}

计算器代码实现

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. 从 左到右 扫描表达式。
2. 遇到数字时，将数字压入堆栈。
3. 遇到符号时，将数字栈栈顶和次顶元素弹出，计算顺序为次顶元素（符号）栈顶元素。
4. 重复上述过程直至剩余最后一个结果。
中缀表达式转后缀表达式
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 ，结果的逆序即为：中缀表达式转后缀表达式的结果

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

查看举例

将中缀表达式：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 ，结果的逆序即为：中缀表达式转后缀表达式的结果

代码实现

查看代码实现

逆波兰表达式的计算器
实现思路：
1. 先将后缀表达式转化为一个 List
2. 对这个 List 进行遍历然后进行计算

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);
    }

}

中缀表达式转后缀表达式代码实现

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. 遇到数字将数字压入栈。
3. 遇到符号弹出数字栈的两个元素，与运算符计算，顺序为：先弹出的（符号）后弹出的。
4. 重复上述过程直至剩余最后一个结果。
中缀表达式转前缀表达式

查看思路

(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 输出结果不需要逆序

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

队列

基本概念

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

数组模拟队列

声明 4 个变量：

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

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

存入数据后将尾指针往后移：rear + 1，前提是当 front == rear时，队列是空的
若尾指针rear < maxSize - 1：
- 则将数据存入rear所指的数组元素中
- 否则无法存入数据，rear = maxSize - 1表示队列满了

查看代码实现

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;
    }

}

循环队列

基本思路：

front:队列的第一个元素
rear:队列最后一个元素的下一个位置
队列满计算公式：(rear + 1) % maxSize == front
队列空计算公式：rear == front
队列中 有效元素个数 计算公式：(rear + maxSize -front) % maxSize

查看代码实现

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;
    }
}