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

请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。

若队列为空，pop_front 和 max_value 需要返回 -1

解题思路

额外维护一个双端队列, 用来保存当前队列可能的最大值, 且是有序的, 首大尾小
插入数据时, 将双端队列中所有小于value的尾部元素弹出, 将value存放于双端队列尾部
弹出队首时, 需要判断双端队列的队首是否也是该值, 如果是则一起弹出

代码

class MaxQueue {
        Queue<Integer> queue;
        Deque<Integer> deque;

        public MaxQueue() {
            queue = new LinkedList<>(); // 队列: 插入和删除
            deque = new LinkedList<>(); // 双端队列: 获取最大值
        }

        public int max_value() {
            return deque.isEmpty() ? -1 : deque.getFirst();
        }

        public void push_back(int value) {
            queue.add(value);
            // 将双端队列中所有小于value的尾部元素弹出
            while (!deque.isEmpty() && deque.getLast() < value) {
                deque.removeLast();
            }
            // 将该值存放于尾部
            deque.addLast(value);
        }

        public int pop_front() {
            if (queue.isEmpty()) {
                return -1;
            }
            int result = queue.poll();
            if (result == deque.getFirst()) {
                deque.removeFirst();
            }
            return result;
        }
}