数据结构_栈和队列

前言

本文介绍栈、队列两种抽象数据类型。

栈

栈stack，又称堆栈，是一种抽象数据类型，每次只能访问栈顶元素top，可以进行压入push和推出pop操作。其元素先进后出 (FILO)。

队列

队列queue,是和栈相对的一种抽象数据类型，每次从后端rear插入，从前端front删除。其元素先进先出 (FIFO)。

用链表实现的队列可以自由扩充，不存在伪溢出问题，但是插入和读取比较耗时；

用数组实现的队列大小固定，可以使用循环队列解决伪溢出问题，即当尾端（前端也类似）指针指向超出数组大小时，可以指向数组开始位置，因为此时大小不超过数组的队列前端已经指向 0 之后的位置了，所以不会冲突。

优先级队列

和队列定义一致，只是在每次插入的时候都进行排序，以满足排序规则（如尾端→前端 小→大）。

中缀表达式与后缀表达式

中缀表达式，指运算符在操作数中间的，如1 + 2。

后缀表达式，指运算符在操作数后面的，如1 2 +。

中缀表达式 ↔ 后缀表达式：

中缀表达式：1 + 2 * ( 3 + 5 ) - 2 * 3 - 9 / 2
后缀表达式：1 2 3 5 + * + 2 3 * - 9 2 / -

转换规则：

设一个栈用于保存运算符，从左到右依次遍历中缀表达式，假设读取到的是x

1. 如果是操作数，则直接打印

2. 如果是运算符(，则压入栈中

3. 如果是运算符)，则推出栈中的元素，直到遇到(,推出(，继续读取下一个

4. 否则，读取栈顶元素top，如果是(，将x压入栈中；

   如果x优先于top，将x压入栈中；

   否则，将top推出，在此和新的top比较，直到遇到top是(或者优先级比x高，或者栈已经空了，将x插入栈中。

/**
 * 中缀表达式转化为后缀表达式
 * @param infix 中缀表达式 1+2
 * @return 后缀表达式 1 2 +
 */
public static String[] covertInfixToPostfix(String infix) {
    StringBuilder stringBuilder = new StringBuilder();
    OperatorStack operatorStack = new OperatorStack();
    for (char item : infix.toCharArray()) {
        // 数字
        if (item >= '0' && item <= '9') {
            stringBuilder.append(item + ",");
        } else if (item == '(') {
            operatorStack.insert(item);
        } else if (item == ')') {
            int size = operatorStack.size();
            for (int i = 0; i < size; i++) {
                try {
                    char pop = operatorStack.pop();
                    if (pop == '(') {
                        break;
                    } else {
                        stringBuilder.append(pop + ",");
                    }
                } catch (Exception e) {
                    System.out.println("栈为空");
                }
            }
        } else {
            try {
                char peek = operatorStack.peek();
                if (peek == '(') {
                    operatorStack.insert(item);
                } else if (isPre(item, peek) > 0) {
                    operatorStack.insert(item);
                } else {
                    int size = operatorStack.size();
                    for (int i = 0; i < size; i++) {
                        try {
                            char pop = operatorStack.peek();
                            if (pop == '(') {
                                break;
                            } else if (isPre(item, peek) > 0) {
                                break;
                            } else {
                                stringBuilder.append(pop + ",");
                                operatorStack.pop();
                            }
                        } catch (Exception e) {
                            break;
                        }
                    }
                    operatorStack.insert(item);
                }
            } catch (Exception e) {
                System.err.println("栈为空");
                operatorStack.insert(item);
            }
        }
    }

    int size = operatorStack.size();
    for (int i = 0; i < size; i++) {
        try {
            stringBuilder.append(operatorStack.pop() + ",");
        } catch (Exception e) {
            System.out.println("栈为空");
            break;
        }
    }

    String result = stringBuilder.toString();

    return result.split(",");
}

源码

👉点这里查看中缀表达式 → 后缀表达式源码

参考资料

堆栈——维基百科

队列——维基百科