Sort Stack

public Stack<Integer> sort(Stack<Integer>stack){
    Stack<Integer>temp=new Stack<Integer>();
    if(stack.isEmpty()) return stack;
    temp.push(stack.pop());
    while(!stack.isEmpty()){
        int val=stack.pop();
        while(!temp.isEmpty()){
            if(temp.peek()<val)
                stack.push(temp.pop());
            else
                break;
        }
        temp.push(val);
    }
    return temp;
}

Min Stack

public class MinStack {
    Deque<Integer> seq;
    Deque<Integer> min;
    /** initialize your data structure here. */
    public MinStack() {
        seq = new LinkedList<>();
        min = new LinkedList<>();
    }

    public void push(int x) {
        seq.push(x);

        // 不要忘了重复数字的时候也要push，不然将来可能栈空
        if (min.isEmpty() || x <= min.peek()) min.push(x); 
    }

    public void pop() {
        int cur = seq.pop();
        if (cur == min.peek()) min.pop();
    }

    public int top() {
        return seq.peek();
    }

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

Implement Queue using Stacks

public class MyQueue {
    Deque<Integer> sequence;
    Deque<Integer> reverse;
    /** Initialize your data structure here. */
    public MyQueue() {
        sequence = new ArrayDeque<>();
        reverse = new ArrayDeque<>();
    }

    /** Push element x to the back of queue. */
    public void push(int x) {
        sequence.addFirst(x);
    }

    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        if (reverse.isEmpty()) {
            while (!sequence.isEmpty()) {
                reverse.addFirst(sequence.removeFirst());
            }
        }
        return reverse.pop();
    }

    /** Get the front element. */
    public int peek() {
        if (reverse.isEmpty()) {
            while (!sequence.isEmpty()) {
                reverse.addFirst(sequence.removeFirst());
            }
        }
        return reverse.peekFirst();
    }

    /** Returns whether the queue is empty. */
    public boolean empty() {
        return reverse.isEmpty() && sequence.isEmpty();
    }
}

Longest Valid Parentheses

store the first index before valid Parentheses into stack

 public int longestValidParentheses(String s) {
    Stack<Integer> stack = new Stack<>();
    int res = 0;
    stack.push(-1);
    for (int i = 0; i < s.length(); ++i) {
        if (s.charAt(i) == '(') {
            stack.push(i);
        } else {
            stack.pop();
            if (stack.isEmpty()) {    // no valid 
                stack.push(i);
            } else {
                res = Math.max(res, i - stack.peek());
            }
        }
    }
    return res;
}