Stack with min

How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time.

C++:
01 template <class T>
02 class Stack{
03     public:
04         bool Push(T);
05         bool Pop();
06         T Top();
07         bool Empty();
08         T Min();
09     private:
10         T min;
11         stack <T> S;
12         vector <T> V;
13 };
14 
15 template <class T>
16 bool Stack<T>::Push(T a)
17 {
18     if(Empty())
19         min=a;
20     if(min>a)
21         min=a;
22     S.push(a);
23     V.push_back(min);
24     return true;
25 }
26 
27 template <class T>
28 bool Stack<T>::Pop()
29 {
30     if(Empty())
31         return false;
32     S.pop();
33     V.pop_back();
34     if(!Empty())
35         min=V.at(V.size()1);
36 }
37 
38 template <class T>
39 T Stack<T>::Min()
40 {
41     if(!Empty())
42         return min;
43 }
44 
45 template <class T>
46 T Stack<T>::Top()
47 {
48     return (S.top());
49 }
50 
51 template <class T>
52 bool Stack<T>::Empty()
53 {
54     return (S.empty());
55 }
Advertisements
This entry was posted in Stack and Queue. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s