Mercurial > Algorithms__Sedgewick
view algs4-c++/src/Stack.cpp @ 15:63df3e6590e2
Bag and RandomBag (1.3.34) classes.
There are not really robust enough to use as they will leak memory on
destruction if you use them to store dynamically allocated objects.
| author | Eris Caffee <discordia@eldalin.com> |
|---|---|
| date | Thu, 11 Jun 2015 16:30:14 -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
5 #include "Stack.hpp"
7 #include <cassert>
8 #include <cstddef>
10 #include <iostream>
12 template <typename T>
13 Stack<T>::Stack( void ) :
14 N (0),
15 list (nullptr)
16 {
17 }
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 }
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 }
38 template <typename T>
39 T Stack<T>::pop( void ) {
40 assert( N > 0 );
42 T item = list->item;
44 Node *old = list;
45 list = list->next;
46 delete old;
47 N--;
49 return item;
50 }
52 template <typename T>
53 bool Stack<T>::is_empty( void ) {
54 return N == 0;
55 }
57 template <typename T>
58 size_t Stack<T>::size( void ) {
59 return N;
60 }
62 template <typename T>
63 typename Stack<T>::iterator Stack<T>::begin( void ) {
64 return Stack<T>::iterator( list );
65 }
67 template <typename T>
68 typename Stack<T>::iterator Stack<T>::end( void ) {
69 return Stack<T>::iterator( nullptr );
70 }
73 ////////////////////////////////////////////////////////////////////////////////
75 template <typename T>
76 Stack<T>::iterator::iterator( Node *c ) :
77 curr (c)
78 {
79 }
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 }
89 template <typename T>
90 typename Stack<T>::iterator Stack<T>::iterator::operator++( int ) {
91 auto t = Stack<T>::iterator( *this );
93 if ( this->curr != nullptr ) {
94 this->curr = this->curr->next;
95 }
96 return t;
97 }
99 template <typename T>
100 T Stack<T>::iterator::operator*() {
101 return this->curr->item;
102 }
104 template <typename T>
105 bool Stack<T>::iterator::operator!=( typename Stack<T>::iterator other ) {
106 return this->curr != other.curr;
107 }
109 ////////////////////////////////////////////////////////////////////////////////
112 #ifdef EXERCISES
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;
121 prev = nullptr;
122 curr = list;
123 if ( curr ) {
124 while ( curr->next ) {
125 prev = curr;
126 curr = curr->next;
127 }
129 item = curr->item;
130 delete curr;
131 if ( prev )
132 prev->next = nullptr;
133 else
134 list = nullptr;
136 N--;
137 }
139 return item;
140 }
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;
151 prev = nullptr;
152 curr = list;
153 while ( curr && (i < k) ) {
154 prev = curr;
155 curr = curr->next;
156 ++i;
157 }
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 }
169 return item;
170 }
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;
178 while ( curr ) {
179 if ( curr->item == key )
180 return true;
181 curr = curr->next;
182 }
184 return false;
185 }
187 #endif
190 ////////////////////////////////////////////////////////////////////////////////
192 #ifdef STACK_MAIN
194 #include <iostream>
196 int main ( int argc, char **argv ) {
198 Stack<long> stack;
200 long i;
201 while ( ! std::cin.eof() ) {
202 std::cin >> i;
203 if ( std::cin.good() )
204 stack.push(i);
205 }
207 std::cout << "Stack has " << stack.size() << " entries." << std::endl;
209 for ( auto iter = stack.begin(); iter != stack.end(); ++iter ) {
210 std::cout << *iter << std::endl;
211 }
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;
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;
222 for ( auto iter = stack.begin(); iter != stack.end(); ++iter ) {
223 std::cout << *iter << std::endl;
224 }
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;
231 for ( auto iter = stack.begin(); iter != stack.end(); ++iter ) {
232 std::cout << *iter << std::endl;
233 }
235 #endif
237 std::cout << "Popping entries..." << std::endl;
239 while ( ! stack.is_empty() ) {
240 i = stack.pop();
241 std::cout << i << std::endl;
242 }
244 std::cout << "Stack has " << stack.size() << " entries." << std::endl;
246 }
248 #endif