Mercurial > Algorithms__Sedgewick

view algs4-c++/src/Stack.cpp @ 10:8af1a61be7c1

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