stack: 先入后出；添加、删除都是O(1)

Queue:先入先出；添加、删除皆为O(1)

双端队列(Double-End Queue)：

元素的首尾都能够进行进入和删除。

优先队列(Priority Queue)：

1.插入操作:O(1)
2.取出操作:O(logN)-按照元素的优先级取出1.插入操作:O(1)
3.head底层数据结构复杂：heap（堆）、bst、teap

(66条消息) 面试 | Java 算法的 ACM 模式_多氯环己烷的博客-CSDN博客_acm模式java

参考链接

· Java 的 PriorityQueue 文档

什么是单调栈：

单调栈中存放的数据应该是有序的，所以单调栈也分为单调递增栈和单调递减栈

单调递增栈：单调递增栈就是从栈底到栈顶数据是从大到小
单调递减栈：单调递减栈就是从栈底到栈顶数据是从小到大

模拟单调栈的数据push和pop
模拟实现一个递增单调栈：

现在有一组数10，3，7，4，12。从左到右依次入栈，则如果栈为空或入栈元素值小于栈顶元素值，则入栈；否则，如果入栈则会破坏栈的单调性，则需要把比入栈元素小的元素全部出栈。单调递减的栈反之。

10入栈时，栈为空，直接入栈，栈内元素为10。

3入栈时，栈顶元素10比3大，则入栈，栈内元素为10，3。

7入栈时，栈顶元素3比7小，则栈顶元素出栈，此时栈顶元素为10，比7大，则7入栈，栈内元素为10，7。

4入栈时，栈顶元素7比4大，则入栈，栈内元素为10，7，4。

12入栈时，栈顶元素4比12小，4出栈，此时栈顶元素为7，仍比12小，栈顶元素7继续出栈，此时栈顶元素为10，仍比12小，10出栈，此时栈为空，12入栈，栈内元素为12。

刷题：

20. 有效的括号 - 力扣（LeetCode）

class Solution {
    public boolean isValid(String s) {
       
        int length    = s.length();
//         长度应该为偶数
        if(length%2==1){
            return false;
        }
        
//    每次保证栈中存在一个元素的右括号,利用元素右括号查询左括号
        
    Map<Character,Character> map = new HashMap<>();
        map.put(')','(');
        map.put('}','{');
        map.put(']','[');

            Deque<Character> pairs = new LinkedList<>();
     for(int i=0;i<s.length();i++){
//          判断是否是右括号，不过不是，加入到stack中
         
         char c = s.charAt(i);
         if(map.containsKey(c)){
             if(pairs.isEmpty()||pairs.peek()!=map.get(c)){
                return false;
             }
             pairs.pop();
         }else{
             pairs.push(c);
         }
     }
//         最后栈是空值
        
        return pairs.isEmpty();
        
    }
}

push()方法：每当push()新值进来时，如果小于等于 min_stack栈顶值，则一起push()到min_stack，即更新了栈顶最小值；
pop()方法：判断将pop()出去的元素值是否是min_stack栈顶元素值（即最小值），如果是则将min_stack栈顶元素一起pop()，这样可以保证min_stack栈顶元素始终是stack中的最小值。
getMin()方法：返回min_stack栈顶即可。
min_stack作用分析：

min_stack等价于遍历stack所有元素，把升序的数字都删除掉，留下一个从栈底到栈顶降序的栈。
相当于给stack中的降序元素做了标记，每当pop()这些降序元素，min_stack会将相应的栈顶元素pop()出去，保证其栈顶元素始终是stack中的最小元素。
复杂度分析：

时间复杂度 O(1)O(1) ：压栈，出栈，获取最小值的时间复杂度都为 O(1)O(1) 。
空间复杂度 O(N)O(N) ：包含 NN 个元素辅助栈占用线性大小的额外空间。

84:柱状图中最大的矩形

暴力法：

利用二重循环，穷举出所有可能的长，并选择标记每次的最小高度。

计算出面积。

class Solution {
    public int largestRectangleArea(int[] heights) {
//         初始化面积
        int area=0;
//      初始化最小高
        int  minH =0;
        int w = heights.length;
        for(int i=0;i<w;i++){
              minH =heights[i];
            for(int j=i;j<w;j++){
//           找出一个最小高,二重循环每次遍历一个，那么就进行记录高的值
              minH =Math.min(minH,heights[j]);
//                 计算出底边
             int  maxw =j-i+1;
             area=Math.max(area,maxw*minH);
            }
            
        }
        return area;
    }

}

算法复杂度：

O(n2)

利用栈来解决

739. 每日温度 - 力扣（LeetCode）

题目分析

对于题目给定的列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，最终的输出是 [1, 1, 4, 2, 1, 1, 0, 0]。

这表示对于第一天的温度73来说，要想观察到比它高的气温，需要等待的天数是1，即第二天的温度74。

对于第二天的温度74来说，要想观察到比它高的气温，需要等待的天数是1，即第三天的温度75。

对于第三天的温度75来说，要想观察到比它高的气温，需要等待的天数是4，即第七天的温度76。

分析到这里，我们就知道由于题目给出的是一个由每日温度组成的数组，而对于某天的温度来说，如果其后有一天温度高于其温度，则它需要等待的天数就是那个更高温度所在的索引值与当前温度所在的索引值的差值；如果其后没有比其更高的温度，则等待天数为0。

至此，这个问题的关键就是对于某天温度来说，如何找出其后面的更高温度？又，最终结果是索引的差值。因此，过程中记录的应该是索引值。

分析：

对于第一天的温度73来说，它是第一个被考察的温度，这时我们还不知道其后面是否有比其高的温度，所以需要将其对应的索引0入栈。

接着，考察第二天的温度74。这时，我们发现第二天温度74大于第一天温度73。因此，对于第一天温度73来说，找到了比它更高的气温，两者索引差值是1。这时，第一天温度73对应的索引0就可以出栈了，接着需要将第二天温度74对应的索引1入栈，

栈739每日温度正序动画1.gif

对于第二天的温度74来说，第三天温度75高于它，因此两者索引差值为1。

当第三天温度75入栈之后，第四天温度71，第五天温度69，都是小于其值且逐渐递减的，对于这种情况，我们将其直接入栈就好。

直到其后某一天温度高于栈顶索引对应的温度时，需要将栈顶索引出栈，计算其和当前温度索引间的差值。然后，继续看当前考察的温度值是否大于栈顶索引对应的温度值，如果是，则栈顶索引出栈，计算其与当前温度索引间的差值；如果不是，则将当前温度对应索引入栈，继续考察下一天的温度，

栈739每日温度正序动画2.gif

代码

class Solution {
    
//    利用栈记录比当天数据大的元素的索引值
    public int[] dailyTemperatures(int[] temperatures) {
//        声明
        Stack<Integer>  dataList = new Stack<>();
        int[] result = new int[temperatures.length];
//       默认值使用0进行代替
        Arrays.fill(result,0);
//       遍历数组，压入栈中
        for(int i=0;i<temperatures.length;i++){
            int tempNum = temperatures[i];
            if(dataList.isEmpty()){
                dataList.push(i);
            } else{
                while(!dataList.isEmpty()&&temperatures[dataList.peek()]<tempNum){
                     int preIndex = dataList.pop();
//                    计算时间天数，并修改返回数组
                     result[preIndex] = (i-preIndex);
                }
                dataList.push(i);
            }
            
        }
        return result;
    
    }
}

转载：动画演示单调栈 739.每日温度 - 每日温度 - 力扣（LeetCode）

496. 下一个更大元素 I

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        Deque<Integer> stack = new ArrayDeque<Integer>();
        //倒序遍历
        for (int i = nums2.length - 1; i >= 0; --i) {
            int num = nums2[i];
            //如果当前值大于栈中的元素，出栈直到小于停止
            while (!stack.isEmpty() && num >= stack.peek()) {
                stack.pop();
            }
//           元素值和栈中的元素一一对应，
            map.put(num, stack.isEmpty() ? -1 : stack.peek());
            stack.push(num);
        }
        int[] res = new int[nums1.length];
        for (int i = 0; i < nums1.length; ++i) {
            res[i] = map.get(nums1[i]);
        }
        return res;
    }
}

栈和队列