Advertisement
markruff

C++ stack (with iterator)

Jan 7th, 2016
181
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.69 KB | None | 0 0
  1. /*
  2.  * Stack class with Iterator
  3.  *
  4.  */
  5.  
  6. template <class T>
  7. class Stack {
  8.  
  9.   private:
  10.     // Define elements/nodes in the stack (unidirectional linked list)
  11.     class StackElement {
  12.       protected:
  13.         T value;
  14.         StackElement* next;
  15.       public:
  16.         StackElement(T value, StackElement* next) : value(value), next(next) { }
  17.  
  18.         ~StackElement() { ; } // nothing to be done
  19.       friend Stack<T>;
  20.     };
  21.  
  22.     // Pointer to the top of the stack
  23.     StackElement* top;
  24.  
  25.     // height of the stack
  26.     int size;
  27.  
  28.     StackElement* recursiveCopy(StackElement* current) {
  29.       if ( current->next == 0 ) {
  30.         return new StackElement(current->value, 0);
  31.       }
  32.       return new StackElement(current, recursiveCopy(current->next) );
  33.     }
  34.  
  35.   public:
  36.     // Define Iterator for the stack    
  37.     // The iterator allows the following code to traverse Stack s
  38.     // for (Stack::Iterator si = s.begin() ; si != s.end() ; si++ ) {
  39.     //   si.value().do_stuff();
  40.     // }
  41.     class Iterator {
  42.     private:
  43.       StackElement* current;
  44.       Stack<T>* my_stack;
  45.  
  46.     public:
  47.       Iterator( Stack<T>* my_stack )
  48.         : current(my_stack->top)
  49.         , my_stack(my_stack)
  50.         {}
  51.  
  52.       Iterator( const Iterator &that )
  53.         : current(that.current)
  54.         , my_stack(that.my_stack)
  55.         {}
  56.  
  57.       // Constructor for Iterator at end
  58.       Iterator( Stack<T>* my_stack, bool end )
  59.         : current(0)
  60.         , my_stack(my_stack)
  61.         {}
  62.      
  63.       ~Iterator() { ; } // nothing to do, does not own pointers
  64.  
  65.       // Overload operators
  66.       // Equality ==
  67.       inline bool operator==(const Iterator &rhs) {
  68.         if ( this->my_stack == rhs.my_stack && this->current == rhs.current ) {
  69.           return true;
  70.         }
  71.         else {
  72.           return false;
  73.         }
  74.       }
  75.  
  76.       // Inequlaity !=
  77.       inline bool operator!=(const Iterator &rhs) { return !(*this == rhs); }
  78.  
  79.       // Increment ++
  80.       inline Iterator &operator++(int) {
  81.         current = current->next;
  82.         return *this;
  83.       }
  84.  
  85.       // Move the iterator to the top of the stack
  86.       void begin() { current = my_stack->top; }
  87.  
  88.       // Move the iterator forward      
  89.       void advance() { current = current->next; }
  90.  
  91.       // Get the value of the element the iterator is pointing at
  92.       T value() { return current->value; }
  93.  
  94.     };
  95.  
  96.  
  97.   public:
  98.  
  99.     // Constructor: empty stack
  100.     Stack<T>() : top(0), size(0) { }
  101.  
  102.     // Constructor: copy constructor
  103.     Stack<T>(const Stack<T> &that) {
  104.       if ( that.top == 0 ) {
  105.         top = 0;
  106.         size = 0;
  107.       }
  108.       else {
  109.         top = recursiveCopy(that.top);
  110.         size = that.size();
  111.       }
  112.     }
  113.  
  114.     // Destructor
  115.     ~Stack<T>() {
  116.        while(top != 0) {
  117.          StackElement* temp = top;
  118.          top = top->next;
  119.          delete temp;
  120.        }
  121.     }
  122.  
  123.     // Push an element onto the stack
  124.     void push(T value) {
  125.       StackElement* element = new StackElement(value,top);
  126.       top = element;
  127.       size++;
  128.     }
  129.  
  130.     // Pop an element off the stack
  131.     // Assert: stack not empty
  132.     T pop() {
  133.       StackElement* popped = top;
  134.       T return_value = popped->value;
  135.       top = top->next;
  136.       size--;
  137.       delete popped;
  138.       return return_value;
  139.     }
  140.  
  141.     // Peek at the top element without popping it
  142.     T peek() {
  143.       return top->value;
  144.     }
  145.      
  146.  
  147.     // return true if stack size = 0
  148.     bool empty() {
  149.       if ( size == 0 ) { return true; }
  150.       return false;
  151.     }
  152.  
  153.     // return the height of the stack
  154.     int height() { return size; }
  155.    
  156.     // return an Iterator to the top of the stack
  157.     Iterator begin() { return Iterator(this); }
  158.  
  159.     // return an Iterator to the element past the end of the stack (null)
  160.     Iterator end() { return Iterator(this, true); }
  161. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement