栈 / 队列

带最小值操作的栈

实现一个栈, 额外支持一个操作：min() 返回栈中元素的最小值

public class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> minStack; // 维护一个辅助栈，传入当前栈的最小值
    
    public MinStack() {
        stack = new Stack<Integer>();
        minStack = new Stack<Integer>();
    }

    public void push(int number) {
        stack.push(number);
        if (minStack.isEmpty()) {
            minStack.push(number);
        } else {
            minStack.push(Math.min(number, minStack.peek()));
        }
    }

    public int pop() {
        minStack.pop();
        return stack.pop();
    }

    public int min() {
        return minStack.peek();
    }
}

有效括号

给定一个字符串所表示的括号序列，包含以下字符： '(', ')', ', ', '[' and ']'， 判定是否是有效的括号序列。括号必须依照 "()" 顺序表示， "()[]" 是有效的括号，但 "([)]" 则是无效的括号。

public boolean isValidParentheses(String s) {
    Stack<Character> stack = new Stack<Character>();
    for (Character c : s.toCharArray()) {
        if ("({[".contains(String.valueOf(c))) {
            stack.push(c);
        } else {
            if (!stack.isEmpty() && isValid(stack.peek(), c)) {
                stack.pop();
            } else {
                return false;
            }
        }
    }
    return stack.isEmpty();
}

private boolean isValid(char c1, char c2) {
    return (c1 == '(' && c2 == ')') || (c1 == '{' && c2 == '}')
        || (c1 == '[' && c2 == ']');
}

用栈实现队列

public class MyQueue {
    private Stack<Integer> outStack;
    private Stack<Integer> inStack;

    public MyQueue() {
       outStack = new Stack<Integer>();
       inStack = new Stack<Integer>();
    }
    
    private void in2OutStack(){
        while(!inStack.isEmpty()){
            outStack.push(inStack.pop());
        }
    }
    
    public void push(int element) {
        inStack.push(element);
    }

    public int pop() {
        if(outStack.isEmpty()){
            this.in2OutStack();
        }
        return outStack.pop();
    }

    public int top() {
        if(outStack.isEmpty()){
            this.in2OutStack();
        }
        return outStack.peek();
    }
}

逆波兰表达式求值

在反向波兰表示法中计算算术表达式的值, ["2", "1", "+", "3", "*"] -> (2 + 1) * 3 -> 9

public int evalRPN(String[] tokens) {
    Stack<Integer> s = new Stack<Integer>();
    String operators = "+-*/";
    for (String token : tokens) {
        if (!operators.contains(token)) {
            s.push(Integer.valueOf(token));
            continue;
        }

        int a = s.pop();
        int b = s.pop();
        if (token.equals("+")) {
            s.push(b + a);
        } else if(token.equals("-")) {
            s.push(b - a);
        } else if(token.equals("*")) {
            s.push(b * a);
        } else {
            s.push(b / a);
        }
    }
    return s.pop();
}