discordia@6: #ifndef STACK_HPP
discordia@6: #define STACK_HPP
discordia@6: 
discordia@6: #include <cstddef>
discordia@6: 
discordia@6: // Linked list based stack after Sedgewick and Wayne, Algorithms 4th ed, Algorithm 1.2
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@6: private:
discordia@6: 
discordia@6:     size_t N;
discordia@6:     Node *list;
discordia@6: 
discordia@6:     };
discordia@6: 
discordia@6: 
discordia@6: 
discordia@6: #endif
discordia@6: