3 栈、队列、优先队列

1 栈的基本使用

例1：LeetCode 20。本题虽然为简单题目但却是很经典的一个问题，在这里因为各处讲解比较多此处直接给出代码：

class Solution {

    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '{' || c =='[' || c == '(') {
                stack.push(c);
            }else{
                //即解决了当栈为空时弹出会报错的情况，又可以检验了一种不匹配情况
                if(stack.isEmpty())
                    return false;
                char pop = stack.pop();
                //这个使用判断不匹配更适合
                if (c == '}' && pop != '{') {
                    return false;
                }else if (c == ']' && pop != '[') {
                    return false;
                }else if (c == ')' && pop != '(') {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

与此类似题目有：LeetCode 150、71。

例2：栈与递归 LeetCode 341。这道题目是作为课下练习的，在这里可以做出来然后分析一下作为例题。

2 队列

队列的基本应用就是广度优先遍历，对应的一般在树中主要是解决层序遍历的问题而在图中主要是解决无权图的最短路径问题。

例1：LeetCode 102。本题可以看作是树的层序遍历的提高版本，对于树的层序遍历可以参考算法与数据结构学习2-5示例，在这里直接给出代码。

class Solution {

    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null){
            return new ArrayList<>();
        }
        //保存最后结果
        List<List<Integer>> res = new ArrayList<>();
        // 层序遍历借用队列来实现
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        while (!queue.isEmpty()){
            // 每层元素数目
            int count = queue.size();
            // 每层遍历的结果
            List<Integer> list = new ArrayList<Integer>();
            while (count > 0){
                TreeNode node = queue.poll();
                list.add(node.val);
                if (node.left != null){
                    queue.add(node.left);
                }
                if (node.right != null){
                    queue.add(node.right);
                }
                count --;
            }
            res.add(list);
        }
        return res;
    }
}

与此类似题目有：LeetCode 107、103、199

例2：LeetCode 279。对于一些问题可能一开始并不是图的问题，但是分析后可以发现可以转向图的问题中。在这里有一点注意，任何一个正整数n都是有解的，因为1就是一个完全平方数，所以一定可以表示为n个1相加的形式。对问题建模：从n到0每个数字表示一个节点，如果两个数字x到y相差一个完全平方数则连接一条边，那么变得到了一个无权图。其图示如下：

class Solution {
    static class Node{
        // 具体的第几个数字
        int val;
        // 走了几段路径来到了这个数字
        int step;
        public Node(int val,int step){
            this.val = val;
            this.step = step;
        }
    }
    public int numSquares(int n) {
        //定义一个队列
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(n,0));
        // 利用visited数组来检查数据是否已经add过了，从而防止数据重复出现，影响图的遍历
        boolean[] visited = new boolean[n+1];
        while (!queue.isEmpty()){
            // 这个数字是多少
            int num = queue.peek().val;
            // 已经走了几步
            int step = queue.peek().step;
            // 取出对首元素后将其出队
            queue.remove();
            /* 没有优化前
            // 若取出的元素为0那么就相当于已经找到解了，直接返回即可
            if (num == 0){
                return step;
            }
            for (int i = 0; num-i*i >= 0; i++) {
                if (!visited[num-i*i]){
                    queue.add(new Node(num-i*i,step+1));
                    visited[num-i*i] = true;
                }
            }
            */
            //对上面的代码优化后
            for (int i = 0; ; i++) {
                int a = num - i*i;
                if (a < 0){
                    break;
                }
                if (a == 0){
                    return step + 1;
                }
                if (!visited[a]){
                    queue.add(new Node(a,step+1));
                    visited[a] = true;
                }
            }
        }
        return -1;
    }
}

与此类似题目：127、126

3 优先队列

对于优先队列其底层是采用堆来实现的，在面试中常见的白板编程就是实现一个堆。因此要重视，这里主要是利用优先队列解决问题。

例1：LeetCode 347。本题在其数据结构中也有一些讲解，只不过笔记中的代码太过于繁琐，这里参考讨论区的给出一个简化版的代码。

class Solution {

    public List<Integer> topKFrequent(int[] nums, int k) {
        // 统计每个元素出现的频率，元素为键，频率为值
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])){
                map.put(nums[i],map.get(nums[i])+1);
            }else {
                map.put(nums[i],1);
            }
        }
        // Java中优先队列就是用最小堆实现的，因为比较的是频率因此需要重写比较方法
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return map.get(o1) - map.get(o2);
            }
        });
        for (Integer key : map.keySet()) {
            // 不足k个元素则进行添加
            if (priorityQueue.size() < k){
                priorityQueue.add(key);
            }else if (map.get(key) > map.get(priorityQueue.peek())){
                //当新元素频率大于队首时便移除对首元素，因为最小堆队首元素便是最小的元素
                priorityQueue.remove();
                priorityQueue.add(key);
            }
        }
        // 取出最小堆中的元素
        List<Integer> res = new ArrayList<>();
        while (!priorityQueue.isEmpty()){
            res.add(priorityQueue.remove());
        }
        return res;
    }
}

与此类似题目：LeetCode 23。