/*
 * Stack class
 * raw pointers
 * no Iterator
 * just the basics
 *
 * Author: Mark Ruff
 */

template <class T>
class Stack {

  private:
    // Define elements/nodes in the stack (unidirectional linked list)
    class StackElement {
      protected:
        T value;
        StackElement* next;
      public:
        StackElement(T value, StackElement* next)
          : value(value)
          , next(next)
          { }
      
      friend Stack<T>;
    };

  private:
    // Pointer to the top of the stack
    StackElement* top;

    // height of the stack
    int size;

    // recursive method used as copy constructor
    StackElement* recursiveCopy(const StackElement &current) {
      if ( current.next == 0 ) {
        return new StackElement(current.value, 0);
      }
      return new StackElement(current, recursiveCopy(current.next) );
    }

  public:

    // Constructor: empty stack
    Stack<T>() : top(0), size(0) { }

    // Constructor: copy constructor
    Stack<T>(const Stack<T> &that) {
      if ( that.top == 0 ) {
        top = 0;
        size = 0;
      }
      else {
        top = recursiveCopy(*(that.top));
        size = that.size();
      }
    }

    // Destructor: delete all StackElements
    ~Stack<T>() {
       while(top != 0) {
         StackElement* temp = top; 
         top = temp->next;
         delete temp;
       }
    }

    // Push an element onto the stack 
    void push(T value) {
      StackElement* element = new StackElement(value,top);
      top = element;
      size++;
    }

    // Pop an element off the stack
    // You mustn't pop an empty stack
    T pop() {
      StackElement* popped = top;
      T return_value = popped->value;
      top = popped->next;
      size--;
      delete popped;
      return return_value;
    }

    // Peek at the top element without popping it
    // You also mustn't peek at an empty stack
    T peek() {
      return top->value;
    } 

    // return true if stack size = 0
    bool empty() {
      if ( size == 0 ) { return true; }
      else { return false; }
    }

    // return the height of the stack
    int height() { return size; } 
};