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
29
30
31
32
33
34
35
36
37
38
39
40
| 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;
}
}
|