Now add a new feature: min in O(1)
====================================================
====================================================
Idea 1(not work)
provide a min function but with time O(n): simply search entire stack and find the min value among all====================================================
Idea 2(not work)
provide a O(1) min function but makes pop O(n):
- push: compare the new value with min( O(1) ), if need to change then change it
- min: when pushing element into the stack, min value would be updated. So does popping out an element
- pop: when we pop the top, if the popped element is not minimum value, then OK.but, if the popped element is minimum value, then we need to search for the current minimum value.This makes the time go to O(n)
====================================================
Idea 3(this works!)
- push, pop, min all in O(1)
- needs more space ( space-time trade off )
e.g.
push 4 -> 4 ; min 4
push 5 -> 5 4 ; min 4
push 3 -> 3 5 4 ; min 3
push 2 -> 2 3 5 4 ; min 2
push 7 -> 7 2 3 5 4 ; min 2
pop -> 2 3 5 4 ; min 2
pop -> 3 5 4 ; min 3
pop -> 5 4 ; min 4
every state, each element accompanied with a minimum value
we can make each node contains not only the key value, but also a minimum value.
Then we can look up the current minimum value immediately on the top node.
so it goes like this:
push 4 -> 4/4 ; min 4
push 5 -> 5/4 4/4 ; min 4
push 3 -> 3/3 5/4 4/4 ; min 3
push 2 -> 2/2 3/3 5/4 4/4 ; min 2
push 7 -> 7/2 2/2 3/3 5/4 4/4 ; min 2
(we only need to peek the top node, then we can know the current minimum value)
pop -> 2/2 3/3 5/4 4/4 ; min 2
pop -> 3/3 5/4 4/4 ; min 3
pop -> 5/4 4/4 ; min 4
====================================================
====================================================
Idea 4(perfect!)
- a little refinement on the way storing a corresponding minimum
Watch...
push 4 -> 4 ; min 4 ; CANDIDATE MIN: 4
push 5 -> 5 4 ; min 4 ; CANDIDATE MIN: 4
push 3 -> 3 5 4 ; min 3 ; CANDIDATE MIN: 3 4
push 2 -> 2 3 5 4 ; min 2 ; CANDIDATE MIN: 2 3 4
push 7 -> 7 2 3 5 4 ; min 2 ; CANDIDATE MIN: 2 3 4
(we only need to peek the top node, then we can know the current minimum value)
pop -> 2 3 5 4 ; min 2 ;
7 is not equal to the current min -> CANDIDATE MIN: 2 3 4
pop -> 3 5 4 ; min 3 ;
2 is equal to the current min, so change current min to 3 -> CANDIDATE MIN: 3 4
pop -> 5 4 ; min 4 ;
3 is equal to the current min, so change current min to 4 -> CANDIDATE MIN: 4
- Current minimum is on the top of candidate list( this is a stack ) -> A additional Stack needed
- each push or pop is performed, we need to check the top value of candidate list, in order to follow up the change that it may take! -> function implementations support
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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
| #include <iostream>
using namespace std;
class Node{
public:
Node( ):val(0), next(NULL){}
int val;
Node *next;
};
class Stack{
public:
Stack( );
virtual ~Stack( );
void push( int );
int pop();
int peek() const;
void showElements( ) const;
private:
Node *top;
};
Stack::Stack( ) : top(NULL){
}
Stack::~Stack( ){
cout << "dtor: \n";
while( top != NULL ){
int v = this->pop();
if( v != -1 )
cout << "delete " << v << " ";
}
cout << endl;
}
void Stack::push(int value){
Node *add = new Node;
add->val = value;
add->next = top;
top = add;
}
int Stack::pop( ){
if( top == NULL )
return -1;
else{
Node *deleted = top;
top = deleted->next;
int r = deleted->val;
delete deleted;
return r;
}
}
int Stack::peek() const{
if( top == NULL )
return -1;
else{
return top->val;
}
}
void Stack::showElements( ) const{
Node *current = top;
while( current != NULL ){
cout << current->val << " ";
current = current->next;
}
cout << endl;
}
// Inherited part -------------------------------------------------
class StackWithMin : public Stack{
public:
StackWithMin(){ }
~StackWithMin( ){}
void push( int );
int pop();
int min( ) const;
private:
Stack minStack; // keep tracking min
};
void StackWithMin::push( int value ){
Stack::push( value );
// update candidate minimum stack
if( min() == -1 || value <= min() )
minStack.push( value );
}
int StackWithMin::pop( ){
int v = Stack::pop( );
// update candidate minimum stack, change to the next min
if( min() == v ){
minStack.pop( );
}
return v;
}
int StackWithMin::min( ) const{
return minStack.peek( );
}
int main( ){
StackWithMin x;
int cmd;
while(true){
cout << "1.push 2.pop 3.peek 4.show 5.Min 6.exit: ";
cin >> cmd;
if( cmd == 6 )
break;
switch(cmd){
case 1:
cout << "push: ";
int v;
cin >> v;
x.push(v);
break;
case 2:
cout << "pop " << x.pop( );
cout << endl;
break;
case 3:
v = x.peek();
if( v == -1 )
cout << "No element!\n";
else
cout << "top element: " << x.peek();
cout << endl;
break;
case 4:
x.showElements( );
break;
case 5:
cout << "Min: " << x.min();
cout << endl;
break;
default:
break;
}
}
}
|
Note: can add a isEmpty method to the interface of Stack
沒有留言:
張貼留言