- Interface: push, pop, peek
- 實作上皆必須是O(1)
- dtor可以呼叫pop來實作
- 利用Node之linked-list來實作Stack
- 動態記憶體配置必須小心memory leak, i.e., 別忘記de-allocate
C ++ code:
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
| #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 << " ";
}
}
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;
}
int main( ){
Stack x;
int cmd;
while(true){
cout << "1.push 2.pop 3.peek 4.show 5.exit: ";
cin >> cmd;
if( cmd == 5 )
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;
default:
break;
}
}
}
|
refine:
- Node可以寫成accessor, mutator 之方式
- Stack 可以多實作copy ctor, assignment operator
沒有留言:
張貼留言