Mercurial > Algorithms__Sedgewick

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