Leetcode-stack&Queue

1，Queue接口与其他接口/实现类的关系：
https://blog.csdn.net/u010871004/article/details/52604171
（1）Deque和Queue的关系：双向队列(Deque),是Queue的一个子接口，双向队列是指该队列两端的元素既能入队(offer)也能出队(poll)。
（2）Java中PriorityQueue实现了Queue接口，不允许放入null元素；其通过堆实现，具体说是通过完全二叉树（complete binary tree）实现的小顶堆（任意一个非叶子节点的权值，都不大于其左右子节点的权值），也就意味着可以通过数组来作为PriorityQueue的底层实现。
2，Stack类一般都尽量避免用。原因：https://www.cnblogs.com/leefreeman/archive/2013/05/16/3082400.html
3，Stack，Queue，都用 LinkedList来构建：
Deque<xxx> stack = new LinkedList<>();
Queue<xxx> queue = new LinkedList<>(); //或者Deque<> ....
方法对照：
https://www.jianshu.com/p/64fc76ca66c9

4，PriorityQueue 是Queue的实现类：
PriorityQueue<String> pQueue = new PriorityQueue<>();

Stack类型题目
Leetcode 20. Valid Parentheses 【Green】【Easy】
题目简介：
解答过程：每次碰到 ) ] }, 都需要检查前面的是不是对应的 ( [ { 。显然是用stack来解决。

class Solution {
    public boolean isValid(String s) {
        if(s==null || s.length()==0) return true;
        Deque<Character> stack = new LinkedList<>();
        for(Character a: s.toCharArray()){            
            if(a=='('||a=='['||a=='{'){
                stack.push(a);
            } else if (a==')'){
                if(stack.isEmpty()||stack.pop()!='(') return false;
            } else if(a==']'){
                if(stack.isEmpty()||stack.pop()!='[') return false;
            } else if(a=='}'){
                if(stack.isEmpty()||stack.pop()!='{') return false;
            }
        }
        return stack.isEmpty();       
    }
}

Leetcode 739.

class Solution {
    public int[] dailyTemperatures(int[] T) {
        //整体是O(n)，因为stack.pop()
        Deque<Integer> stack = new LinkedList<>(); 
        int[] res = new int[T.length];
        for(int i=0; i<T.length; i++){
            while(!stack.isEmpty() && T[i] > T[stack.peek()]){ 
                int index = stack.pop();
                res[index] = i-index;
            }
            stack.push(i);
        }
        return res;
    }
}