Mercurial > Algorithms__Sedgewick

comparison algs4-c++/src/Stack.hpp @ 27:80ca1973e3bd

find changesets by author, revision, files, or words in the commit message
Fleshed out Queue::generic_iterator a bit more to make it a more or less complete example of implmenting an iterator.
author Eris Caffee <discordia@eldalin.com>
date Tue, 23 Jun 2015 17:14:09 -0500
parents 8af1a61be7c1
children
comparison
equal deleted inserted replaced
3:35c4271a13af 4:f871a80eb8d1
1 // Linked list based stack after Sedgewick and Wayne, Algorithms 4th ed, Algorithm 1.2
2
1 #ifndef STACK_HPP 3 #ifndef STACK_HPP
2 #define STACK_HPP 4 #define STACK_HPP
3 5
6 #include <cassert>
4 #include <cstddef> 7 #include <cstddef>
5 8
6 // Linked list based stack after Sedgewick and Wayne, Algorithms 4th ed, Algorithm 1.2
7 9
8 template <typename T> 10 template <typename T>
9 class Stack { 11 class Stack {
10 12
11 private: 13 private:
68 Node *list; 70 Node *list;
69 71
70 }; 72 };
71 73
72 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 }
73 252
74 #endif 253 #endif
75 254
255
256 #endif
257