正常的棧如果想取最大或最小值需要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 閱讀(752)
評論(0) 編輯 收藏 引用 所屬分類:
算法基礎