栈、队列及优先级队列

整体把握

数组、链表、树等等都适用于数据库应用中作数据记录，常用来记录对应于现实世界的数据；而栈、队列及优先级队列更多地是作为程序员的工具来使用(用最合适的工具干活)，以简化某些程序操作。

栈、队列及优先级队列都可以使用数组链表来实现，优先级队列通常使用堆实现。

在栈、队列及优先级队列中，访问是受限制的，在某一时刻只有某一个特定的数据项可以被读取或删除。

栈

应用：单词逆序；解析源代码时检验括号匹配；解析算术表达式；栈操作还嵌入在微处理器中，比如当调用一个方法时返回值和参数压入栈，方法结束时，那些数据出栈。

解析算术表达式：

算术表达式求值通常都是先转换为后缀表达式，再求后缀表达式的值；在中缀表表达式转换为后缀表达式以及求后缀表达式的值的过程里，栈都是很有用的工具。

中缀表表达式	后缀表达式
((A+B)*C)-D	AB+C*D-
A+B*(C-D/(E+F))	ABCDEF+/-*+

转换后缀表达式规则：操作数不入栈，操作符入栈，在适当的时候出栈，比如中缀表达式1+2*3-5=，解析为后缀表达式过程如下表所示

步数	读表达式	var	栈	备注
第一步	1	1
第二步	1+	1	+
第三步	1+2	12	+
第四步	1+2*	12	+*
第五步	1+2*3	123	+*
第六步	1+2*3-	123*+	-	读到-时把*出栈，把+也出栈
第七步	1+2*3-5	123*+5	-
第八步	1+2*3-5=	123*+5-		读到=时把-出栈

后缀表达式求值规则：操作数入栈、遇到操作符从栈中提出两个操作数执行计算，结果入栈，计算123*+5-的值如下表所示

步数	读表达式	栈
第一步	1	1
第二步	12	12
第三步	123	123
第四步	123*	16
第五步	123*+	7
第六步	123*+5	75
第七步	123*+5-	2

实现

数组实现，栈内有一个top记录栈顶的数据顶，插入++top，删除top--
单链表实现，push()对应insertFisrt()，pop()对应deleteFirst()

效率

入栈出栈O(1)，也就是说，所耗的时间不依赖于栈中数据项的个数，栈不需要比较和移动操作。

代码

package MyTest;

public class Stack {
    private int[] dataArr;
    private int initCapacity;
    private int top;

    public Stack(int initCapacity) {
        dataArr = new int[initCapacity];
        top = -1;
        this.initCapacity = initCapacity;
    }

    public void push(int element) {
        dataArr[++top] = element;
    }

    public int pop() {
        return dataArr[top--];
    }

    public int peek() {
        return dataArr[top];
    }

    public boolean isEmpty() {
        return top == -1;
    }

    public boolean isFull() {
        return top == initCapacity - 1;
    }
}

class MyTest {
    public static void main(String[] args) {
        Stack stack = new Stack(20);
        stack.push(200);
        stack.push(300);
        stack.push(404);
        stack.push(555);
        stack.push(606);

        System.out.print(stack.peek() + "  ");
        System.out.print(stack.peek() + "  
");
        while (!stack.isEmpty()) {
            int pop = stack.pop();
            System.out.print(pop + "  ");
        }

        if (!stack.isEmpty()) {
            System.out.print(stack.peek());
        } else {
            System.out.println();
            System.out.print("Stack is empty");
        }
    }
}

class WordReverser {
    public static void main(String[] args) {
        String str = wordReverser("中华人民共和国");
        System.out.println(str);
    }

    private static String wordReverser(String str) {
        Stack stack = new Stack(20);
        for (int i = 0; i < str.length(); i++) {
            stack.push(str.charAt(i));
        }
        str = "";
        while (!stack.isEmpty()) {
            str += (char) stack.pop();
        }
        return str;
    }
}

class Compiler {
    private static String src1 = "c[d]";        // correct，正确的
    private static String src2 = "a{b[c]d}e";  // correct
    private static String src3 = "a{b(c]d}e";  // not correct; doesn't match
    private static String src4 = "a[b{c}d]e}"; // not correct; nothing matches final }
    private static String src5 = "a{b(c)";     // not correct; nothing mathches opening {
    private static Stack stack = new Stack(10);

    public static void main(String[] args) {
        /*
         * 结果有四种情况
         * 1、正确
         * 2、不匹配
         * 3、左括号多余，右括号多余
         */
        compile(src5);
    }

    public static void compile(String src) {
        char c = 0;
        for (int i = 0; i < src.length(); i++) {
            c = src.charAt(i);
            switch (c) {
                case '{':
                case '[':
                case '(':
                    stack.push(c);
                    break;
                case '}':
                case ']':
                case ')':
                    if (stack.isEmpty()) {
                        System.out.println("not correct; nothing matches final " + (char)c);
                        return;
                    } else {
                        int pop = stack.pop();
                        if (!(pop == '{' && c == '}' || pop == '[' && c == ']' || pop == '(' && c == ')')) {
                            System.out.println("not correct; doesn't match");
                            return;
                        }
                    }
            }
        }
        if (stack.isEmpty()) {
            System.out.println("correct");
        } else {
            System.out.println("not correct; nothing mathches opening " + (char) stack.pop());
        }
    }
}

View Code

队列

应用：

因特网数据包等待传送；操作系统里有很多队列，打印作业的打印队列；文字处理软件有一个容纳键入内容的队列，队列保证了键入内容的顺序不会改变。
队列也可以用于模拟真实世界，比如模拟银行排队、飞机等待起飞。

实现：

数组实现，通常的作法是通过移动队头队尾的指针保持数据项的位置不变，这样必须使用环绕式处理。
双端链表实现，insert()对应insertLast()，remove对应deleteFirst()

效率：

插入删除数据项的时间复杂度都是O(1)

双端队列

头尾都可以插入和删除，比如可能有方法insertLeft()/insertRight、removeLeft()/removeRight()

优先级队列

优先级队列其实就是有序队列，有升序优先级队列和降序优先级队列；它允许访问最小(最大)的数据项。

应用：

在抢先式多任务操作系统中，程序排列在优先级队列中，这样优先级最高的程序就会先得到时间片运行。
很多情况下需要访问具有最小关键字值的数据项，比如寻找最便宜的方法或最短的路径去做某件事。

实现：

除了可以快速访问最小关键字值的数据项，优先级队列还应该实现相当快的插入数据项，因此优先级队列通常使用椎来实现。
数组实现1——>有序数组实现，不需要使用环绕指针，插入慢，删除快
数组实现2——>无序数组实现，插入快，删除慢，因为要寻找最小值
有序链表实现