栈

• 顺序栈（用数组实现ArrayDeque）；
• 链式栈（由链表实现LinkedDeque）。

• 因为无论是顺序栈还是链式栈，入栈、出栈都只涉及栈顶个别数据的操作；
• 例如顺序栈实际上就是操作数组的最后一个元素，链式栈实际上就是对头节点做增删。

• 一种是可能会涉及到数据迁移时间复杂度为O（n）；
• 一种是会普通的入栈操作时间复杂度为O（1）；
• 通过将耗时多的入栈操作的时间均摊到其他入栈操作上，平均时间复杂度为O（1）。

• 操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成“栈”这种结构，用来存储函数调用时的临时变量；
• 每次进入一个函数，就会将临时变量作为一个栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈。

• 通过两个栈实现，一个栈保存操作数、一个栈保存运算符。
• 从左到右遍历表达式，当遇到数字，直接压入操作数栈；
• 当遇到运算符，就与运算符栈顶元素进行比较。如果比运算符栈顶元素的优先级高，就将当前运算符压入栈；如果比运算符栈顶元素的优先级低或者相同，从运算符栈中取栈顶元素运算符，从操作数栈的栈顶取2个操作数，然后进行计算，再把计算完的结果压入操作数栈，继续比较。

常见算法

• 772. 基本计算器 III
• 227. 基本计算器 II
• 224. 基本计算器

class Solution {
    public int calculate(String s) {
        Deque<Integer> deque = new ArrayDeque<>();
        Deque<Character> ops = new ArrayDeque<>();

        int i = 0;
        while(i < s.length()){
            char c = s.charAt(i);
            if(c == ' '){
                i++;
                continue;
            }else if(isDigit(c)){
                // 将数组压入栈中
                int number = 0;
                while(i < s.length() && isDigit(s.charAt(i))){
                    number = number * 10 + (s.charAt(i) - '0');
                    i++;
                }
                deque.push(number);
                continue;
            }else if(c == '('){
                ops.push(c);
            }else if(c == ')'){
                // 括号的部分进行运算
                while(ops.peek() != '('){
                    int temp = cal(deque.pop(), deque.pop(), ops.pop());
                    deque.push(temp);
                }
                ops.pop();
            }else{
                // 操作符的优先级进行排序、大于则压入，小于则将压入计算之后再次比较
                if(ops.isEmpty() || !findFirst(ops.peek(), c)){
                    ops.push(c);
                }else{
                    int temp = cal(deque.pop(), deque.pop(), ops.pop());
                    deque.push(temp);
                    continue;
                }
            }

            i++;
        }

        while(!ops.isEmpty()){
            int temp = cal(deque.pop(), deque.pop(), ops.pop());
            deque.push(temp);
        }

        return deque.pop();
    }

    public int cal(int nums1, int nums2, char c){
        if(c == '+'){
            return nums1 + nums2;
        }else if(c == '-'){
            return nums2 - nums1;
        }else if(c == '*'){
            return nums2 * nums1;
        }else{
            return nums2 / nums1;
        }
    }

    public boolean findFirst(char top, char c){
        return top != '(' && (top == '*' || top == '/' || c == '+' || c == '-');
    }

    public boolean isDigit(char c){
        return (c >= '0' && c <= '9');
    }
}

class Solution {
    public boolean isValid(String s) {
        Map<Character, Character> map = new HashMap<>();
        map.put(')', '(');
        map.put(']', '[');
        map.put('}', '{');

        Deque<Character> deque = new ArrayDeque<>();
        for(int i = 0; i < s.length(); i++){
            char temp = s.charAt(i);
            if(!deque.isEmpty() && deque.peek() == map.get(temp)){
                deque.pop();
            }else{
                deque.push(temp);
            }
        }
        return deque.isEmpty();
    }
}

class MinStack {

    Deque<Integer> min;
    Deque<Integer> deque;

    public MinStack() {
        min = new ArrayDeque<>();
        deque = new ArrayDeque<>();
    }
    
    public void push(int val) {
        deque.push(val);
        if(min.isEmpty() || min.peek() >= val){
            min.push(val);
        }
    }
    
    public void pop() {
        if(deque.pop().equals(min.peek())){
            min.pop();
        }
       
    }
    
    public int top() {
        return deque.peek();
    }
    
    public int getMin() {
        return min.peek();
    }
}

class CQueue {

    Deque<Integer> deque;
    Deque<Integer> help;

    public CQueue() {
        deque = new ArrayDeque<>();
        help = new ArrayDeque<>();
    }
    
    public void appendTail(int value) {
        help.push(value);
    }
    
    public int deleteHead() {
        if(deque.isEmpty()){
            while(!help.isEmpty()){
                deque.push(help.pop());
            }
        }

        return deque.isEmpty() ? -1 : deque.pop();
    }
}

class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> deque = new ArrayDeque<>();
        int nums1 = 0, nums2 = 0;
        for(String i : tokens){
            switch(i){
                case("+"):
                nums1 = deque.pop();
                nums2 = deque.pop();
                deque.push(nums2 + nums1); 
                break;
                case("-"):
                nums1 = deque.pop();
                nums2 = deque.pop();
                deque.push(nums2 - nums1); 
                break;
                case("*"):
                nums1 = deque.pop();
                nums2 = deque.pop();
                deque.push(nums2 * nums1); 
                break;
                case("/"):
                nums1 = deque.pop();
                nums2 = deque.pop();
                deque.push(nums2 / nums1); 
                break;
                default:
                deque.push(Integer.parseInt(i));
            }
        }

        return deque.pop();
    }
}

• 496. 下一个更大元素 I
• 503. 下一个更大元素 II
• 剑指 Offer II 038. 每日温度
• 739. 每日温度
• 42. 接雨水

int[] res = new int[n];
//存储下标
Deque<Integer> deque = new ArrayDeque<>();
for(int i = 0; i < n; i++){
    //如果当前元素大于栈里的元素、说明当前元素就是栈首的下一个元素
    while(!deque.isEmpty() && arr[i] > arr[deque.peek()]){
        res[deque.pop()] = arr[i];
    }
    //继续下一个元素
    deque.push(i);
}

• 84. 柱状图中最大的矩形
• 962. 最大宽度坡
• 1124. 表现良好的最长时间段
  

class Solution {
    public int largestRectangleArea(int[] heights) {
        // 核心思路：找到左右两侧第一个小于当前值的元素
        // deque是单调递减栈，栈中的下一个元素就是左侧小于当前值的元素，右侧是i
        // 前面填0可以不需要判断栈为空，后面填0为了让栈中的元素全部拿出
        int[] arr = new int[heights.length + 2];
        System.arraycopy(heights, 0, arr, 1, heights.length);
        int res = 0, n = arr.length;
        Deque<Integer> deque = new ArrayDeque<>();

        for(int i = 0; i < n; i++){
            while(!deque.isEmpty() && arr[deque.peek()] > arr[i]){
                int h = arr[deque.pop()];
                res = Math.max(res, h * (i - deque.peek() - 1));
            }

            deque.push(i);
        }

        return res;
    }
}