正常的栈如果想取最大或最小值需要O(N)时间复杂度，如果需要O(1)时间的话该如何做呢？可以采取空间换时间的方法，使用另外一个栈来记录当前的最大值，这样就可以达到时间最优，代码如下：
1 template<typename Type>
2 class Stack {
3 public:
4 Stack() {}
5 ~Stack() {}
6
7 void Push(Type elem) {
8 if (s.empty()) {
9 s.push(elem);
10 cur_max.push(elem);
11 cur_min.push(elem);
12 } else {
13 s.push(elem);
14 cur_max.push(cur_max.top() > elem ? cur_max.top() : elem);
15 cur_min.push(cur_min.top() > elem ? elem : cur_min.top());
16 }
17 }
18
19 void Pop() {
20 assert(!s.empty() && !cur_max.empty() && !cur_min.empty());
21 s.pop();
22 cur_max.pop();
23 cur_min.pop();
24 }
25
26 Type Top() {
27 assert(!s.empty());
28 return s.top();
29 }
30
31 Type Max() {
32 assert(!cur_max.empty());
33 return cur_max.top();
34 }
35
36 Type Min() {
37 assert(!cur_min.empty());
38 return cur_min.top();
39 }
40
41 bool Empty() {
42 return s.empty();
43 }
44
45 bool Empty() {
46 return s.empty();
47 }
48
49 int Size() {
50 return s.size();
51 }
52
53 private:
54 std::stack< Type > s;
55 std::stack< Type > cur_max;
56 std::stack< Type > cur_min;
57 };
上面的代码采用C++的模版，并且底层数据结构依然采用stl中的栈来实现。
如果要使得去队列的Max和Min操作尽量快，那么可以考虑使用两个栈来模拟队列，假设栈为s1和s2，入队的时候只往s1中入；出栈的时候只从s2出，如果s2为空，则将s1中所有的元素都一次出栈并依次入栈进s2；求队列的最大值即求s1和s2两个栈的最大值，求队列的最小值即求s1和s2两个栈的最小值，代码如下：
1 template <typename Type>
2 class Queue {
3 public:
4 Queue() {}
5 ~Queue() {}
6
7 void Push(Type elem) {
8 s1.Push(elem);
9 }
10
11 void Pop() {
12 if (s2.Empty()) {
13 while (!s1.Empty()) {
14 s2.Push(s1.Top());
15 s1.Pop();
16 }
17 }
18 assert(!s2.Empty());
19 s2.Pop();
20 }
21
22 Type Front() {
23 if (s2.Empty()) {
24 while (!s1.Empty()) {
25 s2.Push(s1.Top());
26 s1.Pop();
27 }
28 }
29 assert(!s2.Empty());
30 return s2.Top();
31 }
32
33 Type Max() {
34 Type res1;
35 Type res2;
36 if (s1.Empty()) {
37 assert(!s2.Empty());
38 return s2.Max();
39 } else {
40 res1 = s1.Max();
41 if (!s2.Empty()) {
42 res2 = s2.Max();
43 return res1 > res2 ? res1 : res2;
44 } else {
45 return res1;
46 }
47 }
48 }
49
50 Type Min() {
51 Type res1;
52 Type res2;
53 if (s1.Empty()) {
54 assert(!s2.Empty());
55 return s2.Min();
56 } else {
57 res1 = s1.Min();
58 if (!s2.Empty()) {
59 res2 = s2.Min();
60 return res1 > res2 ? res2 : res1;
61 } else {
62 return res1;
63 }
64 }
65 }
66
67 private:
68 Stack< Type > s1;
69 Stack< Type > s2;
70 };
主要是思想，编码比较简单。
posted on 2012-09-03 20:08
myjfm 阅读(717)
评论(0) 编辑 收藏 引用 所属分类:
算法基础