Advertisement
markruff

C++ stack (raw pointers)

Jan 6th, 2016
288
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.10 KB | None | 0 0
  1. /*
  2.  * Stack class
  3.  * raw pointers
  4.  * no Iterator
  5.  * just the basics
  6.  *
  7.  * Author: Mark Ruff
  8.  */
  9.  
  10. template <class T>
  11. class Stack {
  12.  
  13.   private:
  14.     // Define elements/nodes in the stack (unidirectional linked list)
  15.     class StackElement {
  16.       protected:
  17.         T value;
  18.         StackElement* next;
  19.       public:
  20.         StackElement(T value, StackElement* next)
  21.           : value(value)
  22.           , next(next)
  23.           { }
  24.      
  25.       friend Stack<T>;
  26.     };
  27.  
  28.   private:
  29.     // Pointer to the top of the stack
  30.     StackElement* top;
  31.  
  32.     // height of the stack
  33.     int size;
  34.  
  35.     // recursive method used as copy constructor
  36.     StackElement* recursiveCopy(const StackElement &current) {
  37.       if ( current.next == 0 ) {
  38.         return new StackElement(current.value, 0);
  39.       }
  40.       return new StackElement(current, recursiveCopy(current.next) );
  41.     }
  42.  
  43.   public:
  44.  
  45.     // Constructor: empty stack
  46.     Stack<T>() : top(0), size(0) { }
  47.  
  48.     // Constructor: copy constructor
  49.     Stack<T>(const Stack<T> &that) {
  50.       if ( that.top == 0 ) {
  51.         top = 0;
  52.         size = 0;
  53.       }
  54.       else {
  55.         top = recursiveCopy(*(that.top));
  56.         size = that.size();
  57.       }
  58.     }
  59.  
  60.     // Destructor: delete all StackElements
  61.     ~Stack<T>() {
  62.        while(top != 0) {
  63.          StackElement* temp = top;
  64.          top = temp->next;
  65.          delete temp;
  66.        }
  67.     }
  68.  
  69.     // Push an element onto the stack
  70.     void push(T value) {
  71.       StackElement* element = new StackElement(value,top);
  72.       top = element;
  73.       size++;
  74.     }
  75.  
  76.     // Pop an element off the stack
  77.     // You mustn't pop an empty stack
  78.     T pop() {
  79.       StackElement* popped = top;
  80.       T return_value = popped->value;
  81.       top = popped->next;
  82.       size--;
  83.       delete popped;
  84.       return return_value;
  85.     }
  86.  
  87.     // Peek at the top element without popping it
  88.     // You also mustn't peek at an empty stack
  89.     T peek() {
  90.       return top->value;
  91.     }
  92.  
  93.     // return true if stack size = 0
  94.     bool empty() {
  95.       if ( size == 0 ) { return true; }
  96.       else { return false; }
  97.     }
  98.  
  99.     // return the height of the stack
  100.     int height() { return size; }
  101. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement