Stack and Queue

LC155. Min Stack
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> Returns -3.
minStack.pop();
minStack.top(); --> Returns 0.
minStack.getMin(); --> Returns -2.

class MinStack {
    //思想就是建两个栈，一个是正常的操作，另一个是存放实时的最小值
    private Stack<Integer> stack;
    private Stack<Integer> minStack;

    /** initialize your data structure here. */
    public MinStack() {
        stack = new Stack<Integer>();
        minStack = new Stack<Integer>();
    }
    
    public void push(int x) {
        stack.push(x);
        if(minStack.isEmpty()){
            minStack.push(x);
        } else {
            minStack.push(Math.min(x, minStack.peek()));
        }
    }
    
    public void pop() {
        stack.pop();
        minStack.pop();
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return minStack.peek();
    }
}

LC232. Implement Queue using Stacks

class MyQueue {
    private Stack<Integer> stack1; 
    private Stack<Integer> stack2;
    /** Initialize your data structure here. */
    public MyQueue() {
        stack1 = new Stack<Integer>();
        stack2 = new Stack<Integer>();
    }
    private void stack2ToStack1(Stack stack1, Stack stack2){
        while(!stack2.isEmpty()){
            stack1.push(stack2.pop());//第二个栈先判断第一个栈是不是非空，再把元素一一添加进第二个栈
        }
    }
    /** Push element x to the back of queue. */
    public void push(int x) {
         stack2.push(x);//第一个栈正常放入数
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        this.stack2ToStack1(stack1, stack2);
        return stack1.pop();
    }
    
    /** Get the front element. */
    public int peek() {
         this.stack2ToStack1(stack1, stack2);
        return stack1.peek();
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        this.stack2ToStack1(stack1, stack2);
        return stack1.isEmpty();
    }
}

LC84. Largest Rectangle in Histogram
Input: [2,1,5,6,2,3]
Output: 10

 public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) return 0;
        
        Stack<Integer> stack = new Stack<Integer>();
        int max = 0;
        for (int i = 0; i <= heights.length; i++){
            int cur = (i == heights.length) ? -1 : heights[i];//在最后的末位补上-1，能让单调栈中的所有元素都能pop出来。
            while(!stack.isEmpty() && cur <= heights[stack.peek()]){//当有元素小于栈顶的元素时，需要把栈顶的元素pop掉，此时恰巧可以计算以pop掉的元素为最小高度的最大面积
                int height = heights[stack.pop()];//此时已经pop掉了栈顶元素所以后续有可能是空的。
                int width = stack.isEmpty() ? i : i-stack.peek()-1;//如果是空的说明pop掉的元素的右边没有元素了，宽度就是i
                max = Math.max(max, height*width);
            }
            stack.push(i);
        }
        return max;
    }

LC42. Trapping Rain Water

public int trap(int[] height) {
        Stack<Integer> stack = new Stack<>();
        int sum = 0;
        int i = 0, j = height.length;
        while(i < j){
            if (stack.isEmpty() || height[i] <= height[stack.peek()]){//这句话是保证潜在bottom永远比栈顶元素小才有可能形成坑
                stack.push(i++);
            } else {//代表后面的元素比目前的栈顶元素大，这样bottom比两边都小所以形成了坑
                int bottom = stack.pop();
                if(stack.isEmpty()) continue; //如果bottom 后面没有栈元素了，那形成不了坑 
                sum += (Math.min(height[i], height[stack.peek()]) - height[bottom]) * (i - stack.peek() - 1);// 坑的左右两面的高度的最小值减去bottom然后乘以两面高度的的坐标的差减一。
            }
        }
        return sum;
    }

LC225. Implement Stack using Queues

class MyStack {
    Queue<Integer> q1;
    Queue<Integer> q2;
    /** Initialize your data structure here. */
    public MyStack() {
        q1 = new LinkedList<Integer>();
        q2 = new LinkedList<Integer>();
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        if (!q1.isEmpty()){
            q1.add(x);
        } else {
            q2.add(x);
        }
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        int x = 0;
        if (q2.isEmpty()){
            while (!q1.isEmpty()){
                x = q1.remove();
                if(!q1.isEmpty()){
                    q2.add(x);
                }
            }
        } else if (q1.isEmpty()){
            while (!q2.isEmpty()){
                x = q2.remove();
                if (!q2.isEmpty()){
                    q1.add(x);
                }
            }
        }
        return x;
    }
    
    /** Get the top element. */
    public int top() {
        int x = 0;
        if (q2.isEmpty()){
            while (!q1.isEmpty()){
                x = q1.remove();
                    q2.add(x);
            }
        } else if (q1.isEmpty()){
            while (!q2.isEmpty()){
                x = q2.remove();
                   q1.add(x);
            }
        }
        return x;
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        if (q1.isEmpty() && q2.isEmpty()) return true;
        else return false;
    }
}

LC71. Simplify Path
···
public String simplifyPath(String path) {
Stack<String> stack = new Stack<>();

    String[] str = path.split("/");// 把字符串分割成只含有"","..","."和文件路径的字符串数组
    for(String s : str){
        if(s.equals("..")){
            if(!stack.isEmpty())
                stack.pop(); //如果他的前置文件路径是遇到..，他的前置文件路径就要被pop掉
        } else if (!s.equals(".") && !s.equals("")){
            stack.push(s);//遇到没有"","."的说明是正常路径
        }
    }
    
    String res = "";
    while(!stack.isEmpty()){
        res = "/" + stack.pop() + res;
    }
    if (res.length() == 0) return "/";
    return res;
}

···
LC150. Evaluate Reverse Polish Notation
Input: ["2", "1", "+", "3", "*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (String token : tokens){
            if (token.equals("+")){
                stack.push(stack.pop() + stack.pop());
            } else if (token.equals("-")){
                int b = stack.pop();
                int a = stack.pop();
                stack.push(a - b);
            } else if (token.equals("*")){
                stack.push(stack.pop() * stack.pop());
            } else if (token.equals("/")){
                int b = stack.pop();
                int a = stack.pop();
                stack.push(a / b);
            } else {
                stack.push(Integer.parseInt(token));
            }
        }
        return stack.pop();
    }

LC20. Valid Parentheses
Input: "{[]}"
Output: true;

 public boolean isValid(String s) {
        char[] strs =s.toCharArray();
        Stack<Character> stack = new Stack<>();
        for (Character str : strs){
            if(str == '('){
                stack.push(')');
            } else if (str == '['){
                stack.push(']');
            } else if (str == '{'){
                stack.push('}');//遇到一个左括号，就把右括号放进栈里，根据栈的特性，当遇到不是左括号时，栈顶的元素一定时最后一个左括号对应的右括号
            } else {
                if (stack.isEmpty() || stack.pop() != str){
                    return false;//如果未遍历完栈空了，或者pop出的不是元素则是false
                }
            }
        }
        return stack.isEmpty(); //最后根据对称性，栈应该是空的
    }

227. Basic Calculator II

 // String/stack
    //3+5-4/6, 先在第一个数前加+，因为不可能是负数，所以sign是+
    //步骤是 3 +? -> +3,0, 5 +? -> +5, 0
    public int calculate(String s) {
       if (s == null || s.length() == 0) return 0;
       Stack<Integer> stack = new Stack<>();
        char sign = '+';
        int num = 0;
        
        for (int i = 0; i < s.length(); i++){
            char c =s.charAt(i);
            if (Character.isDigit(c)){
            num = num*10 + c -'0';
            }// 累加数字
            if (c!=' ' && !Character.isDigit(c) || i + 1 == s.length()){
                if (sign == '+'){
                    stack.push(num);
                } else if (sign == '-'){
                    stack.push(-num);
                } else if (sign == '/'){
                    stack.push(stack.pop() / num);
                } else if (sign == '*'){
                    stack.push(stack.pop() * num);
                }
                sign = c;
                num = 0;
            }
        }
        int res = 0;
        while(!stack.isEmpty()){
            res += stack.pop();
        }
        return res;
    }

LC224. Basic Caculator

class Solution {
    // 3 + (5 + 4)
    public int calculate(String s) {
        int res = 0, num = 0, sign = 1;
        
        Stack<Integer> stack = new Stack<>();
        char[] chars = s.toCharArray();
        
        for (Character c : chars){
            if(Character.isDigit(c))
                num = num*10 + c - '0';
            if(c == '+' || c == '-'){
                res += sign * num;//计算的是前一次的数
                sign = (c == '+') ? 1 : -1;
                num = 0;
            } else if (c == '('){
                stack.push(res); 
                stack.push(sign); // 记录括号前的总和和符号
                res = 0;
                sign = 1; //初始化和和符号
            } else if (c == ')'){
                res += sign * num;
                num = 0;
                res *= stack.pop();
                res += stack.pop();//计算完括号里的9，再把括号外的和加上，第一个stack.pop是括号外的符号
            }
        }
        res += sign*num;
        return res;
    }
}