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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
| class listNode {
public:
listNode() {val = 0; next = NULL;}
listNode(int v) {val = v; next = NULL;}
listNode(int v, listNode *n) {val = v; next = n;}
int val;
listNode *next;
};
class MaxQueue {
public:
MaxQueue() {
head = NULL;
tail = NULL;
maxVal = NULL;
}
int max_value() {
if (maxVal == NULL)
return -1;
else
return maxVal->val;
}
void push_back(int value) {
listNode *newNode = new listNode(value, NULL);
if (head == NULL) {
head = newNode;
tail = newNode;
maxVal = newNode;
}
else {
tail->next = newNode;
tail = newNode;
if (value >= maxVal->val)
maxVal = newNode;
}
}
int pop_front() {
if (head == NULL)
return -1;
else {
int res;
if (head == tail) {
res = head->val;
delete head;
head = NULL;
tail = NULL;
maxVal = NULL;
} else {
listNode *temp = head->next;
res = head->val;
if (head == maxVal) {
maxVal = head->next;
listNode *p = maxVal->next;
while (p != NULL) {
if (p->val >= maxVal->val)
maxVal = p;
p = p->next;
}
}
delete head;
head = temp;
}
return res;
}
}
private:
listNode *head;
listNode *tail;
listNode *maxVal;
};
|