双栈双队列实现API接口

栈排序

重点在push操作

class SortedStack {

    Stack<Integer> stackMin;
    Stack<Integer> stack;

    public SortedStack() {
        stackMin = new Stack<>();
        stack = new Stack<>();
    }

    public void push(int val) {
        //放入栈中前，将最小的弹出，并放在辅助栈中
        while(!stack.isEmpty() && stack.peek() < val){
            stackMin.push(stack.pop());
        }
        //放入栈中
        stack.push(val);
        //再借助辅助栈装回栈中，保证最小的永远在栈中
        while(!stackMin.isEmpty()){
            stack.push(stackMin.pop());
        }
    }

    public void pop() {
        //注意空处理
        if(isEmpty())
            return;
        stack.pop();
    }

    public int peek() {
        //空处理
        if (isEmpty()) {
            return -1;
        }
        return stack.peek();
    }

    public boolean isEmpty() {
        return stack.isEmpty();
    }
}

队列的最大值

class MaxQueue {
    Deque<Integer> res;
    Deque<Integer> max;
    public MaxQueue() {
        res = new LinkedList<>();
        max = new LinkedList<>();
    }

    public int max_value() {
        if(max.isEmpty())
            return -1;
        //返回max的头部
        return max.peekFirst();
    }

    public void push_back(int value) {
        res.addLast(value);
        //更新max队列，保证是单调递减的
        while(!max.isEmpty() && max.peekLast() < value){
            max.removeLast();
        }
        max.addLast(value);
    }

    public int pop_front() {
        if(res.isEmpty())
            return -1;
        int temp = res.removeFirst();
        if(temp == max.peekFirst()){
            max.removeFirst();
        }
        return temp;
    }
}