剑指 Offer 59 - II. 队列的最大值

class MaxQueue {

    private final Queue<Integer> queue;
    private final Deque<Integer> increaseDeque;

    public MaxQueue() {
        this.queue = new LinkedList<>();
        this.increaseDeque = new LinkedList<>();
    }

    public int max_value() {
        if (queue.isEmpty()) {
            return -1;
        }

        return increaseDeque.getLast();
    }

    public void push_back(int value) {
        queue.offer(value);

        while (!increaseDeque.isEmpty() && increaseDeque.getFirst() < value) {
            increaseDeque.removeFirst();
        }
        increaseDeque.addFirst(value);
    }

    public int pop_front() {
        if (queue.isEmpty()) {
            return -1;
        }

        int value = queue.poll();
        if (increaseDeque.getLast().equals(value)) {
            increaseDeque.removeLast();
        }
        return value;
    }

}
Reference
