discordia@18: // Linked list based stack after Sedgewick and Wayne, Algorithms 4th ed, Algorithm 1.2
discordia@18: 
discordia@6: #ifndef STACK_HPP
discordia@6: #define STACK_HPP
discordia@6: 
discordia@18: #include <cassert>
discordia@6: #include <cstddef>
discordia@6: 
discordia@6: 
discordia@6: template <typename T>
discordia@6: class Stack {
discordia@6: 
discordia@9: private:
discordia@6: 
discordia@6:     ////////////////////////////////////
discordia@6:     class Node {
discordia@6:     public:
discordia@6:         T item;
discordia@6:         Node *next;
discordia@6:         };
discordia@6: 
discordia@6: 
discordia@9: public:
discordia@9: 
discordia@6:     ////////////////////////////////////
discordia@6:     class iterator;
discordia@6:     friend class iterator;
discordia@6:     class iterator {
discordia@6: 
discordia@6:     public:
discordia@6: 
discordia@6:         iterator( Node *c );
discordia@6: 
discordia@6:         iterator& operator++();
discordia@6:         iterator operator++(int);
discordia@6: 
discordia@6:         T operator*();
discordia@6:         bool operator!=( typename Stack<T>::iterator );
discordia@6: 
discordia@6:     private:
discordia@6: 
discordia@6:         Node *curr;
discordia@6:         };
discordia@6: 
discordia@6:     ////////////////////////////////////
discordia@6: 
discordia@6:     Stack( void );
discordia@6:     ~Stack( void );
discordia@6: 
discordia@6:     void push( T &item );
discordia@6:     T pop( void );
discordia@6: 
discordia@6:     bool is_empty( void );
discordia@6:     size_t size( void );
discordia@6: 
discordia@6:     iterator begin( void );
discordia@6:     iterator end( void );
discordia@6: 
discordia@10: #ifdef EXERCISES
discordia@10: 
discordia@10:     T delete_bottom( void );    // 1.3.19
discordia@10:     T remove( size_t k );       // 1.3.20
discordia@10:     bool find( T key );         // 1.3.21
discordia@10: 
discordia@10: #endif
discordia@10: 
discordia@6: private:
discordia@6: 
discordia@6:     size_t N;
discordia@6:     Node *list;
discordia@6: 
discordia@6:     };
discordia@6: 
discordia@6: 
discordia@18: ////////////////////////////////////////////////////////////////////////////////
discordia@18: 
discordia@18: 
discordia@18: template <typename T>
discordia@18: Stack<T>::Stack( void ) :
discordia@18:     N (0),
discordia@18:     list (nullptr)
discordia@18:     {
discordia@18:     }
discordia@18:     
discordia@18: template <typename T>
discordia@18: Stack<T>::~Stack( void ) {
discordia@18:     assert( N == 0 );  // Catch the potential memory leak.
discordia@18:     while ( list ) {
discordia@18:         Node * next = list->next;
discordia@18:         delete list;
discordia@18:         list = next;
discordia@18:         }
discordia@18:     }
discordia@18: 
discordia@18: template <typename T>
discordia@18: void Stack<T>::push( T &item ) {
discordia@18:     Node * node = new Node();
discordia@18:     node->item = item;
discordia@18:     node->next = list;
discordia@18:     list = node;
discordia@18:     N++;
discordia@18:     }
discordia@18: 
discordia@18: template <typename T>
discordia@18: T Stack<T>::pop( void ) {
discordia@18:     assert( N > 0 );
discordia@18: 
discordia@18:     T item = list->item;
discordia@18: 
discordia@18:     Node *old = list;
discordia@18:     list = list->next;
discordia@18:     delete old;
discordia@18:     N--;
discordia@18: 
discordia@18:     return item;
discordia@18:     }
discordia@18: 
discordia@18: template <typename T>
discordia@18: bool Stack<T>::is_empty( void ) {
discordia@18:     return N == 0;
discordia@18:     }
discordia@18: 
discordia@18: template <typename T>
discordia@18: size_t Stack<T>::size( void ) {
discordia@18:     return N;
discordia@18:     }
discordia@18: 
discordia@18: template <typename T>
discordia@18: typename Stack<T>::iterator Stack<T>::begin( void ) {
discordia@18:     return Stack<T>::iterator( list );
discordia@18:     }
discordia@18: 
discordia@18: template <typename T>
discordia@18: typename Stack<T>::iterator Stack<T>::end( void ) {
discordia@18:     return Stack<T>::iterator( nullptr );
discordia@18:     }
discordia@18: 
discordia@18: 
discordia@18: ////////////////////////////////////////////////////////////////////////////////
discordia@18: 
discordia@18: template <typename T>
discordia@18: Stack<T>::iterator::iterator( Node *c ) :
discordia@18:     curr (c)
discordia@18:     {
discordia@18:     }
discordia@18: 
discordia@18: template <typename T>
discordia@18: typename Stack<T>::iterator & Stack<T>::iterator::operator++() {
discordia@18:     if ( this->curr != nullptr ) {
discordia@18:         this->curr = this->curr->next;
discordia@18:         }
discordia@18:     return *this;
discordia@18:     }
discordia@18: 
discordia@18: template <typename T>
discordia@18: typename Stack<T>::iterator Stack<T>::iterator::operator++( int ) {
discordia@18:     auto t = Stack<T>::iterator( *this );
discordia@18: 
discordia@18:     if ( this->curr != nullptr ) {
discordia@18:         this->curr = this->curr->next;
discordia@18:         }
discordia@18:     return t;
discordia@18:     }
discordia@18: 
discordia@18: template <typename T>
discordia@18: T Stack<T>::iterator::operator*() {
discordia@18:     return this->curr->item;
discordia@18:     }
discordia@18: 
discordia@18: template <typename T>
discordia@18: bool Stack<T>::iterator::operator!=( typename Stack<T>::iterator other ) {
discordia@18:     return this->curr != other.curr;
discordia@18:     }
discordia@18: 
discordia@18: ////////////////////////////////////////////////////////////////////////////////
discordia@18: 
discordia@18: 
discordia@18: #ifdef EXERCISES
discordia@18: 
discordia@18: // 1.3.19
discordia@18: // Returns the item if entry was found.  If the entry did not exist, then the returned value is undefined.
discordia@18: template <typename T>
discordia@18: T Stack<T>::delete_bottom( void ) {
discordia@18:     Node *prev, *curr;
discordia@18:     T item;
discordia@18: 
discordia@18:     prev = nullptr;
discordia@18:     curr = list;
discordia@18:     if ( curr ) {
discordia@18:         while ( curr->next ) {
discordia@18:             prev = curr;
discordia@18:             curr = curr->next;
discordia@18:             }
discordia@18: 
discordia@18:         item = curr->item;
discordia@18:         delete curr;
discordia@18:         if ( prev )
discordia@18:             prev->next = nullptr;
discordia@18:         else
discordia@18:             list = nullptr;
discordia@18: 
discordia@18:         N--;
discordia@18:         }
discordia@18: 
discordia@18:     return item;
discordia@18:     }
discordia@18: 
discordia@18: 
discordia@18: // 1.3.20
discordia@18: // Returns the item if entry was found.  If the entry did not exist, then the returned value is undefined.
discordia@18: template <typename T>
discordia@18: T Stack<T>::remove( size_t k ) {
discordia@18:     Node *prev, *curr;
discordia@18:     size_t i=0;
discordia@18:     T item;
discordia@18: 
discordia@18:     prev = nullptr;
discordia@18:     curr = list;
discordia@18:     while ( curr && (i < k) ) {
discordia@18:         prev = curr;
discordia@18:         curr = curr->next;
discordia@18:         ++i;
discordia@18:         }
discordia@18: 
discordia@18:     if ( curr &&( i == k) ) {
discordia@18:         item = curr->item;
discordia@18:         if ( prev )
discordia@18:             prev->next = curr->next;
discordia@18:         else
discordia@18:             list = curr->next;;
discordia@18:         delete curr;
discordia@18:         N--;
discordia@18:         }
discordia@18: 
discordia@18:     return item;
discordia@18:     }
discordia@18: 
discordia@18: // 1.3.21
discordia@18: // Returns true if the specified key is in the stack.
discordia@18: template <typename T>
discordia@18: bool Stack<T>::find( T key ) {
discordia@18:     Node *curr = list;
discordia@18: 
discordia@18:     while ( curr ) {
discordia@18:         if ( curr->item == key )
discordia@18:             return true;
discordia@18:         curr = curr->next;
discordia@18:         }
discordia@18: 
discordia@18:     return false;
discordia@18:     }
discordia@6: 
discordia@6: #endif
discordia@6: 
discordia@18: 
discordia@18: #endif
discordia@18: