栈ADT实现及其应用

栈模型##

栈（Stack）是限制插入和删除只能在一个位子上进行的表，该位子是表的末端，叫做栈的顶（top）。对栈的基本操作有进栈（push）和出栈（pop），相当于表插入和删除最后一个元素。

栈的实现##

由于栈可以看作是一个表，因此任何实现表的方法都能实现栈。显然，在Java集合中，ArrayList和LinkedList都支持栈的操作，由于栈的操作都是栈顶元素，所以对于数组实现的ArrayList和链表实现的LinkedList来说都花费常数时间，因此他们并没有太大区别。但是对于代码实现来说，数组实现更加简洁，更易于理解，下面将给出栈的简单实现。

public class Stack<E> {

    //栈的默认大小为10
    private static final int DEFAULT_VALUE_SIZE = 10;
    //用一个数组来存储栈的元素
    private E[] elementData;
    //栈中元素的实际个数
    private int size;

    //构造器，调用doClear方法初始化
    public Stack() {
        doClear();
    }

    //进栈操作
    public E push(E element) {
        //存放栈元素的数组满了，则需要对elementData扩容
        if (elementData.length == size) {
            //扩容操作
            ensureCapacity(size + 1);
        }
        elementData[size++] = element;
        return element;
    }

    //出栈操作，若栈为空时出栈，则抛出数组越界异常
    public E pop() {
        if (size == 0) {
            throw new IndexOutOfBoundsException();
        }
        return elementData[--size];
    }

    //清空栈的操作
    public void clear() {
        doClear();
    }

    //清空栈的操作
    private void doClear() {
        size = 0;
        ensureCapacity(DEFAULT_VALUE_SIZE);
    }

    //保证在进栈的，存储栈元素的elementData数组有足够的空间
    private void ensureCapacity(int minCapacity) {
        if (size > minCapacity) {
            return;
        }

        E[] old = elementData;
        elementData = (E[]) new Object[minCapacity];

        for (int i = 0; i < size; i++) {
            elementData[i] = old[i];
        }
    }

    //返回栈的实际元素个数
    public int size() {
        return size;
    }

}

上面的代码实现了栈的基本操作，push/pop/clear。

栈的应用##

应用1 —— 平衡符号####

编译器检查程序的语法错误，但是常常由于缺少一个符号（如遗漏一个花括号）引起编译不能通过。在这种情况下，一个有用的工具就是检测是成对出现的东西。于是，一个右花括号、右方括号及右括号必然对其相应的左括号。比如[()]序列是合法的，[(])是不合法的。

通过栈，可以实现上述程序，思路如下：
做一个空栈，读取字符直到末尾。如果字符是一个开放符号（左边的符号），则将其推入栈内。如果字符是一个封闭符号（右边的符号），则当空栈是报错。否则，将栈元素弹出。如果弹出的开放符号不是当前封闭符号所对应的符号，则报错。在字符串末尾，若栈非空则报错。

代码实现######

public class StackApplication {

    // 申明一个栈，用来存放开放符号
    Stack<Character> lefts = new Stack<Character>();
    // 申明一个数组，用来存放封闭符号
    ArrayList<Character> rights = new ArrayList<Character>();
    // 用来存放从控制台读取的字符数组
    char[] characters;

    // 从控制台读取字符串，并转换成字符串
    private void readCharsFromConsole() {
        Scanner scanner = new Scanner(System.in);
        if (scanner.hasNext()) {
            // 给characters数组
            characters = scanner.next().toCharArray();
        }
    }

    // 检查开放符号和封闭符号是否匹配
    public boolean check() {
        readCharsFromConsole();

        // 开放符号进栈lefts，封闭符号添加到数组rights
        for (int i = 0; i < characters.length; i++) {
            char ch = characters[i];
            if (ch == '(') {
                lefts.push(ch);
            }
            if (ch == ')') {
                rights.add(ch);
            }
        }

        // 如果开放符号的个数不等于封闭符号的个数则报错
        if (lefts.size() != rights.size()) {
            return false;
        }

        // 遍历封闭符号，如果栈lefts弹出的元素不是当前封闭元素所对应的，则返回false
        for (int i = 0; i < rights.size(); i++) {

            if (rights.get(i).charValue() == ')') {
                if (lefts.pop().charValue() != '(') {
                    return false;
                }
            }
        }

        // 最后返回true
        return true;
    }

}

测试代码######

    public static void main(String[] args) {
        StackApplication stackApplication = new StackApplication();
        System.out.println(stackApplication.check());
    }

测试结果######

在控制台输入((()))，回车，结果如下图所示，返回true。

结果

在控制台输入((())，回车，结果如下图所示，返回false。

结果

应用二 —— 后缀表达式（逆波兰表达式）####

假设我们需要一个计算器来计算我们购物的花费，你的计算公式可能是这样的：2 * 2 + 3 * 3，如果你手上的计算器的普通计算器的话，答案为21。但是现在大多数时候我们希望使用科学计算器，它可以判定运算的优先级，科学计算器的结果为13。

我们简单地分析一下科学计算器计算上面例子的过程，首先判断优先级，乘法有限，所以依次计算2*2和#3*3并将其结果分别存储到两个临时变量A1和A2中，最后计算加法，将A1和A2求和。我们可以将这种操作写为：2 2 * 3 3 * +。这就是逆波兰表达式。

计算细节如下：

首先假设有一个空栈stack，遍历后缀表达式，将数字压入栈中，直到遇到一个操作符，这个操作符的操作数为连续两次出栈的结果。

• 第一步：stack=[2,2]，读到一个操作符为*，于是操作数连续两次出栈的结果2和2。所以计算结果为2*2=4，将结果压入栈中，stack=[4]。
• 第二步：继续读入数字，直到一个操作符。stack=[4,3,3]，操作符为*，操作数为连续两次出栈的结果3和3。所以计算结果为3*3=9，将结果压入栈中，stack=[4,9]。
• 第三部：继续读入，下一个元素为+操作数，所以执行加法操作，操作数为连续两次出栈的结果4和9，所以计算结果为4+9=13。压栈，stack=13。到此遍历完了整个后缀表达式，最后结果就为栈顶元素13。

代码######

public class StackApplication2 {
    // 字符数组，用来保存后缀表达式的每一个字符
    private char[] postfix;
    // 操作数栈
    Stack<Integer> numberStack = new Stack<Integer>();

    // 构造器，传入一个后缀表达式字符串
    public StackApplication2(String postfix) {
        this.postfix = postfix.toCharArray();
    }

    public StackApplication2() {

    }

    // 判断后缀表达式中字符是否为数字
    private boolean isNumeric(char ch) {
        return (ch >= '0' && ch <= '9') ? true : false;
    }

    // 科学计算器的实现方法
    public int scientificCaculator() {
        // 两个操作数
        int num1;
        int num2;
        // 遍历后缀表达式
        for (int i = 0; i < postfix.length; i++) {
            char temp = postfix[i];
            // 如果是数字就压栈
            if (isNumeric(temp)) {
                numberStack.push(temp - '0');// char转int
            } else {
                // 如果是操作符就从栈中弹出操作数并执行相关运算
                num1 = numberStack.pop();
                num2 = numberStack.pop();
                if (temp == '+') {
                    numberStack.push(num1 + num2);
                } else if (temp == '-') {
                    numberStack.push(num1 - num2);
                } else if (temp == '*') {
                    numberStack.push(num1 * num2);
                } else if (temp == '/') {
                    numberStack.push(num1 / num2);
                }
            }
        }

        // 返回最后的栈顶元素，即结果
        return numberStack.pop();
    }

}

测试代码#######

    public static void main(String[] args) {
        StackApplication2 stackApplication2 = new StackApplication2("6523+8*+3+*");
        System.out.println(stackApplication2.scientificCaculator());
    }

结果######

测试结果
计算一个后缀表示花费的时间是O(N)，该算法是一个十分简单的算法。注意，当一个表达式以后缀表示给出时，我们就不用知道运算的优先级，这是一个明显的优点。

中缀到后缀的转换####

栈不仅仅可以用来计算后缀表达式的值，还可以用来用来讲一个标准形式的表达式（中缀表达式）转换成后缀表达式。 我们假设只有运算+,*,(,)，并且表达式合法以及使用普通的优先级法则，即括号>乘>加。
假设中缀表示1+2*3+(4*5+6)*7,则转换后的后缀表达式为：123*+45*6+7*+。

转换方法######

我们需要两个数据结构，一个用来存放操作符的栈operatorStack，一个用来存放后缀表达式的字符数组postfix。遍历中缀表达式，如果读到的是一个操作数，则立即添加到postfix数组中，如果是一个操作符则相对麻烦。为了说明方便，我们将operatorStack栈中的栈顶操作符称为top，当前遍历的操作符为temp。
操作符的处理规则如下：

• 如果栈为空，则直接将temp压入operatorStack栈中。
• 如果栈不为空并且temp= * 或 + 或 (，然后将temp的优先级和top比较，如果temp的优先级大于top优先级，则将temp压栈；否则，依次将栈中优先级大于或等于temp的操作符弹出，添加到postfix，直到top优先级高于temp，然后将temp压栈，但是有一个情况例外，即top=（,temp的优先级低于(时，这种情况，top不会出栈，而是将temp直接压栈。
• 如果读到的），则依次弹出操作符，加入postfix的末尾，直到（。

现在我们对刚才提到的例子1+2*3+(4*5+6)*7采用上面的算法依次计算：

1. 读取到操作数1，直接添加到postfix数组中。此时，operatorStack为空，postfix=[1]。
2. 读取到操作符+，因为此时栈为空，所以直接压栈。此时，operatorStack={+}，postfix=[1]。
3. 读取到操作数2，直接添加到postfix数组中。此时，operatorStack={+}，postfix=[1,2]。
4. 读取到操作符*，此时temp = *，top = +，优先级temp > top，所以temp压栈。此时，operatorStack={+,*}，postfix=[1,2]。
5. 读取到操作数3，直接添加到postfix数组中。此时，operatorStack={+,*}，postfix=[1,2,3]。
6. 读取到操作符+，此时temp = +,top = *，优先级top>=temp，所以top出栈并添加到postfix数组。此时operatorStack={+}，postfix=[1,2,3,*]，top=+，top>=temp，所以top出栈并添加到postfix数组。此时operatorStack={}，postfix=[1,2,3,*,+}。此时operatorStack为空，所以temp压栈。所以此时operatorStack={+}，postfix=[1,2,3,*,+}。
7. 读取操作符（，此时temp = (，top = +，优先级temp > top，所以temp直接压栈。此时，operatorStack={+,(}，postfix=[1,2,3,*,+]。
8. 读取操作数4，直接添加到postfix数组中。此时operatorStack={+,(}，postfix=[1,2,3*,+，4]。
9. 读取操作符*，此时temp = *，top = (，虽然优先级top >= temp，但是对于（特殊处理，不出栈。所以temp直接压栈。此时operatorStack={+,(,*}，postfix=[1,2,3,*,+,4]。
10. 读取操作数5，直接添加到postfix数组中。此时operatorStack={+,(,*}，postfix=[1,2,3,*,+,4,5]。
11. 读取操作符+，此时temp = +，top = *，优先级top >= temp，所以top出栈并且添加到postfix数组，此时operatorStack={+,(}，postfix=[1,2,3,*,+,4,5,*],top = （，优先级temp < top，temp直接压栈。此时operatorStack={+,(,+}，postfix=[1,2,3,*,+,4,5,*]。
12. 读取操作数6，直接添加到postfix数组中。此时operatorStack={+,(,+}，postfix=[1,2,3,*,+,4,5,*,6]。
13. 读取操作符），依次弹出栈顶操作符，直到（。此时operatorStack={+}，postfix=[1,2,3,*,+,4,5,*,6,+]。
14. 读取操作符*，此时temp = *，top = +，优先级temp > top，所以temp压栈。此时operatorStack={+,*}，postfix=[1,2,3,*,+,4,5,*,6,+]。
15. 读取操作数7，直接添加到postfix数组中。此时operatorStack={+,*}，postfix=[1,2,3,*,+,4,5,*,6,+,7]。
16. 依次弹出栈中剩余操作符，最终operatorStack={}，postfix=[1,2,3,*,+,4,5,*,6,+,7,*,+]。

代码实现######

public class InfixToPostfix {
    // 存放操作符的栈
    private Stack<Character> operatorStack = new Stack<Character>();
    // 存放后缀表达式的字符数组
    private char[] postfix;
    // 存放中缀表达式的字符数组
    private char[] infix;

    // 定义操作符
    private static final char multiply = '*';
    private static final char divide = '/';
    private static final char add = '+';
    private static final char substract = '-';
    private static final char leftParenthesis = '(';
    private static final char rightParenthesis = ')';

    // 构造器
    public InfixToPostfix(String infix) {
        this.infix = infix.toCharArray();
        postfix = new char[infix.length()];
    }

    public InfixToPostfix() {

    }

    // 判断一个字符是否为数字
    private boolean isNumeric(char ch) {
        return (ch >= '0' && ch <= '9') ? true : false;
    }

    private String infixToPostfix() {
        // 插入后缀的表达式下标
        int insertIndex = 0;
        // 操作符栈的大小
        int size;
        // 返回结果，后缀表达式字符串
        String result;

        for (int i = 0; i < infix.length; i++) {
            if (isNumeric(infix[i])) {
                postfix[insertIndex++] = infix[i];
            } else {

                char temp = infix[i];
                size = operatorStack.size();
                // 如果栈为空，就直接压栈
                if (size == 0) {
                    operatorStack.push(temp);
                } else { // 栈不为空时

                    // 弹出栈顶元素
                    char top = operatorStack.pop();

                    if (temp == rightParenthesis) {
                        while (top != leftParenthesis) {
                            postfix[insertIndex++] = top;
                            top = operatorStack.pop();
                        }
                    } else {

                        // 如果当前操作符的优先级大于栈顶操作符的优先级，则当前操作符进栈

                        if (operatorPriorityCompare(temp, top)) {
                            /*
                             * 因为上一行为了比较当前操作符和栈顶元素的操作符, 
                             * 上面弹出了栈顶元素,
                             * 所以这里要先将弹出的操作符压栈
                             */
                            operatorStack.push(top);
                        }

                        /*
                         * 如果当前操作符的优先级低于或等于栈顶操作符的优先级， 则栈顶操作符出栈，然后一直比较，
                         * 直到栈顶操作符优先级大于当前操作符或栈为空，然后当前操作符进栈。
                         */

                        while (!operatorPriorityCompare(temp, top)) {
                            if (top == leftParenthesis) {
                                operatorStack.push(top);
                                break;
                            } else {
                                postfix[insertIndex++] = top;
                                size = operatorStack.size();
                                if (size == 0) {
                                    break;
                                }
                                top = operatorStack.pop();
                            }
                        }

                        // 当前操作符进栈
                        operatorStack.push(temp);

                    }
                }
            }
        }

        // 遍历完毕，一次弹出栈中剩余操作符
        size = operatorStack.size();
        if (size != 0) {
            for (int i = 0; i < size; i++) {
                postfix[insertIndex++] = operatorStack.pop();
            }
        }

        result = String.valueOf(postfix).trim();
        return result;
    }

    // 判断操作符的优先级：括号>乘除>加减
    // true: temp>top false: top >= temp
    private boolean operatorPriorityCompare(char current, char top) {
        if (((current == multiply || current == divide) && (top == substract || top == add))
                || (current == leftParenthesis
                        && (top == multiply || top == divide || top == substract || top == add))) {
            return true;
        } else {
            return false;
        }

    }

}

测试代码######

    public static void main(String[] args) {
        InfixToPostfix infixToPostfix = new InfixToPostfix("1+2*3+(4*5+6)*7");
        String result = infixToPostfix.infixToPostfix();
        System.out.println(result);
    }

测试结果######

测试结果

与上面相同，这种转换需要O(N)时间。可以通过制定减法和加法有相同优先级以及乘法和除法有相同优先级二将减法和乘法添加到指令中去。需要注意的是，表达式a-b-c应该转化为ab-c-，而不是abc--。