Mercurial > Algorithms__Sedgewick

view algs4-c++/src/Stack.hpp @ 18:a149b424b4e2

find changesets by author, revision, files, or words in the commit message
Updated all template classes to have the implementaiton in the header file.
author Eris Caffee <discordia@eldalin.com>
date Sat, 20 Jun 2015 19:36:11 -0500
parents 8af1a61be7c1
children
line source
1 // Linked list based stack after Sedgewick and Wayne, Algorithms 4th ed, Algorithm 1.2
2
3 #ifndef STACK_HPP
4 #define STACK_HPP
5
6 #include <cassert>
7 #include <cstddef>
8
9
10 template <typename T>
11 class Stack {
12
13 private:
14
15 ////////////////////////////////////
16 class Node {
17 public:
18 T item;
19 Node *next;
20 };
21
22
23 public:
24
25 ////////////////////////////////////
26 class iterator;
27 friend class iterator;
28 class iterator {
29
30 public:
31
32 iterator( Node *c );
33
34 iterator& operator++();
35 iterator operator++(int);
36
37 T operator*();
38 bool operator!=( typename Stack<T>::iterator );
39
40 private:
41
42 Node *curr;
43 };
44
45 ////////////////////////////////////
46
47 Stack( void );
48 ~Stack( void );
49
50 void push( T &item );
51 T pop( void );
52
53 bool is_empty( void );
54 size_t size( void );
55
56 iterator begin( void );
57 iterator end( void );
58
59 #ifdef EXERCISES
60
61 T delete_bottom( void ); // 1.3.19
62 T remove( size_t k ); // 1.3.20
63 bool find( T key ); // 1.3.21
64
65 #endif
66
67 private:
68
69 size_t N;
70 Node *list;
71
72 };
73
74
75 ////////////////////////////////////////////////////////////////////////////////
76
77
78 template <typename T>
79 Stack<T>::Stack( void ) :
80 N (0),
81 list (nullptr)
82 {
83 }
84
85 template <typename T>
86 Stack<T>::~Stack( void ) {
87 assert( N == 0 ); // Catch the potential memory leak.
88 while ( list ) {
89 Node * next = list->next;
90 delete list;
91 list = next;
92 }
93 }
94
95 template <typename T>
96 void Stack<T>::push( T &item ) {
97 Node * node = new Node();
98 node->item = item;
99 node->next = list;
100 list = node;
101 N++;
102 }
103
104 template <typename T>
105 T Stack<T>::pop( void ) {
106 assert( N > 0 );
107
108 T item = list->item;
109
110 Node *old = list;
111 list = list->next;
112 delete old;
113 N--;
114
115 return item;
116 }
117
118 template <typename T>
119 bool Stack<T>::is_empty( void ) {
120 return N == 0;
121 }
122
123 template <typename T>
124 size_t Stack<T>::size( void ) {
125 return N;
126 }
127
128 template <typename T>
129 typename Stack<T>::iterator Stack<T>::begin( void ) {
130 return Stack<T>::iterator( list );
131 }
132
133 template <typename T>
134 typename Stack<T>::iterator Stack<T>::end( void ) {
135 return Stack<T>::iterator( nullptr );
136 }
137
138
139 ////////////////////////////////////////////////////////////////////////////////
140
141 template <typename T>
142 Stack<T>::iterator::iterator( Node *c ) :
143 curr (c)
144 {
145 }
146
147 template <typename T>
148 typename Stack<T>::iterator & Stack<T>::iterator::operator++() {
149 if ( this->curr != nullptr ) {
150 this->curr = this->curr->next;
151 }
152 return *this;
153 }
154
155 template <typename T>
156 typename Stack<T>::iterator Stack<T>::iterator::operator++( int ) {
157 auto t = Stack<T>::iterator( *this );
158
159 if ( this->curr != nullptr ) {
160 this->curr = this->curr->next;
161 }
162 return t;
163 }
164
165 template <typename T>
166 T Stack<T>::iterator::operator*() {
167 return this->curr->item;
168 }
169
170 template <typename T>
171 bool Stack<T>::iterator::operator!=( typename Stack<T>::iterator other ) {
172 return this->curr != other.curr;
173 }
174
175 ////////////////////////////////////////////////////////////////////////////////
176
177
178 #ifdef EXERCISES
179
180 // 1.3.19
181 // Returns the item if entry was found. If the entry did not exist, then the returned value is undefined.
182 template <typename T>
183 T Stack<T>::delete_bottom( void ) {
184 Node *prev, *curr;
185 T item;
186
187 prev = nullptr;
188 curr = list;
189 if ( curr ) {
190 while ( curr->next ) {
191 prev = curr;
192 curr = curr->next;
193 }
194
195 item = curr->item;
196 delete curr;
197 if ( prev )
198 prev->next = nullptr;
199 else
200 list = nullptr;
201
202 N--;
203 }
204
205 return item;
206 }
207
208
209 // 1.3.20
210 // Returns the item if entry was found. If the entry did not exist, then the returned value is undefined.
211 template <typename T>
212 T Stack<T>::remove( size_t k ) {
213 Node *prev, *curr;
214 size_t i=0;
215 T item;
216
217 prev = nullptr;
218 curr = list;
219 while ( curr && (i < k) ) {
220 prev = curr;
221 curr = curr->next;
222 ++i;
223 }
224
225 if ( curr &&( i == k) ) {
226 item = curr->item;
227 if ( prev )
228 prev->next = curr->next;
229 else
230 list = curr->next;;
231 delete curr;
232 N--;
233 }
234
235 return item;
236 }
237
238 // 1.3.21
239 // Returns true if the specified key is in the stack.
240 template <typename T>
241 bool Stack<T>::find( T key ) {
242 Node *curr = list;
243
244 while ( curr ) {
245 if ( curr->item == key )
246 return true;
247 curr = curr->next;
248 }
249
250 return false;
251 }
252
253 #endif
254
255
256 #endif
257