最大值栈和最大值队列(Tsinghua OJ,PA2)
最大值栈
要求
以O(1)的时间查询栈中的最大值.
思路
维护一个最大值栈，在原栈中数据发生改变时最大值栈也跟着改变。
每次输入一个数据，若最大值栈为空，则比较最大值栈栈顶和当前元素，如果当前元素较大或相等，就把当前元素推入栈中，反之出栈时，如果出栈元素和当前元素相等，则把最大值栈中元素也推出栈。
实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
template <typename T>
class MaxStack
{
private:
Stack <T> max_stack;
Stack <T> _data;
public:
T max(){
return max_stack.top();
}
void push(T ele){
_data.push(ele);
if(max_stack.empty() || ele >= max_stack.top()){
max_stack.push(ele);
}
}
T pop(){
T tmp = _data.top();
if(_data.pop() == max_stack.top()){
max_stack.pop();
}
return tmp;
}
};
|
最大值队列
要求
用o(n)时间查询队列的最大值
思路
用两个最大值栈模拟队列。入队时把元素压入栈A，出队时弹出B的栈顶。（若B为空，则把A中元素全部弹出压入B再弹出）。取最大值时去A，B中的最大值的最大值。
输入
第一行仅含一个整数，即高度查询和车辆出入操作的总次数n
以下n行，依次这n次操作。各行的格式为以下几种之一:
- E x //有一辆高度为x的车进入隧道（x为整数）
- D //有一辆车离开隧道
- M //查询此时隧道中车辆的最大高度
输出
若D和M操作共计m次，则输出m行
对于每次D操作，输出离开隧道车辆的高度
对于每次M操作，输出所查询到的最大高度
实现
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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
|
#include "Stack.h"
#include <iostream>
#include <cstdio>
using namespace std;
template <typename T>
class MaxStack
{
private:
Stack <T> max_stack;
Stack <T> _data;
public:
bool empty(){
return _data.empty();
}
T max(){
return max_stack.top();
}
void push(T ele){
_data.push(ele);
if(max_stack.empty() || ele >= max_stack.top()){
max_stack.push(ele);
}
}
T pop(){
T tmp = _data.top();
if(_data.pop() == max_stack.top()){
max_stack.pop();
}
return tmp;
}
T top(){
return _data.top();
}
};
template <typename T>
class MaxQueue{
private:
MaxStack <T> s1,s2;
public:
bool empty(){
return s1.empty() && s2.empty();
}
void enqueue(T ele){
s1.push(ele);
}
T dequeue(){
if(s2.empty()){
while(!s1.empty()){
s2.push(s1.top());
s1.pop();
}
}
return s2.pop();
}
T front(){
if(s2.empty()){
while(!s1.empty()){
s2.push(s1.top());
s1.pop();
}
}
return s2.top();
}
T max(){
if((!s1.empty()) && (!s2.empty()))
return (s1.max() > s2.max() ? s1.max() : s2.max());
else if ((!s1.empty()) && (s2.empty()))
return s1.max();
else return s2.max();
}
};
int main(int argc, char const *argv[])
{
MaxQueue <int>queue;
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
char op[2];
scanf("%s", op);
if (*op == 'E') {
int num;
cin >> num;
queue.enqueue(num);
} else if (*op == 'D') {
printf("%d\n", queue.front());
queue.dequeue();
} else {
printf("%d\n", queue.max());;
}
}
return 0;
}
|