posts - 183,  comments - 10,  trackbacks - 0
设计一个保护 min 函数的栈,min 函数返回栈的最小元素。并且 min、push、pop 函数的时间复杂度都为 O(1)。

主要思想是定义一个辅助栈记录最小元素在原栈中的索引。

实现中参考:
http://hi.baidu.com/xiangzifengshi/blog/item/2f9e833aef17d6f7828b131e.html
http://zhedahht.blog.163.com/blog/static/25411174200712895228171/

代码实现:
 1 #include <iostream>
 2 #include <ctime>
 3 #include <cassert>
 4 using namespace std;
 5 
 6 class MinStack
 7 {
 8 private:
 9     int stack[100];
10     int p;
11     int minstack[100];
12     int q;
13     
14     bool minEmpty()
15     {
16         return q == 0;
17     }
18     void minPop()
19     {
20         assert(!minEmpty());
21         --q;
22     }
23     int minTop()
24     {
25         assert(!minEmpty());
26         return minstack[q - 1];
27     }
28 public:
29     MinStack() : p(0), q(0) {}
30     bool empty()
31     {
32         return p == 0;
33     }
34     void push(int i)
35     {
36         stack[p++= i;
37         if (minEmpty())
38         {
39             minstack[q++= p - 1;
40         }
41         else
42         {
43             if (i <= stack[minTop()])
44             {
45                 minstack[q++= p - 1;
46             }
47         }
48     }
49     void pop()
50     {
51         assert(!empty());
52         if (top() == stack[minTop()])
53         {
54             minPop();
55         }
56         --p;
57     }
58     int min()
59     {
60         assert(!empty());
61         return stack[minTop()];
62     }
63     int top()
64     {
65         assert(!empty());
66         return stack[p - 1];
67     }
68 };
69 
70 int main()
71 {
72     MinStack ms;
73     srand(time(0));
74     for (int i = 0; i < 10++i)
75     {
76         int n = rand() % 100;
77         ms.push(n);
78     }
79     while (!ms.empty())
80     {
81         cout << ms.top() << '\t' << ms.min() << endl;
82         ms.pop();
83     }
84     return 0;
85 }
posted on 2011-04-23 01:28 unixfy 阅读(159) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理