队列的最大值

问题陈述

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

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

思路分析

使用一个队列和一个双端队列实现，普通队列用来插入和删除， 双端队列用来存储maxvalue。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class MaxQueue {
    Queue<Integer> queue;
    Deque<Integer> deque;
public MaxQueue() {
    queue = new LinkedList<>();  //队列：插入和删除
    deque = new LinkedList<>();  //双端队列：获取最大值
}

public int max_value() {
    return deque.size()>0?deque.peek():-1;  //双端队列的队首为que的最大值
}

public void push_back(int value) {
    queue.offer(value);  //value入队
    while(deque.size()>0 && deque.peekLast()<value){
        deque.pollLast();  //将deq队尾小于value的元素删掉
    }
    deque.offerLast(value);  //将value放在deq队尾
}

public int pop_front() {
    int tmp = queue.size()>0?queue.poll():-1;  //获得队首元素
    if(deque.size()>0 && tmp==deque.peek()){
        deque.poll();  //如果出队的元素是当前最大值，将deq的队首出队
    }
    return tmp;
}
}

Queue和Deque知识点补充

Queue

1
2
3
4
5
1. 在队尾添加一个元素：offer()

2. 在队首移除一个元素：poll()

3. 获取队列头部元素：peek()

Deque

1
2
3
4
5
1. offerFirst()/pollFirst() 检索并(插入)删除此双端队列的第一个元素，null如果此双端队列为空，则返回。

2. offerLast()/pollLast() 检索并(插入)删除此双端队列的最后一个元素，null如果此双端队列为空，则返回。

3.peekFirst()/peekLast() 检索但不删除此双端队列的第一个(最后一个)元素，null如果此双端队列为空，则返回。