// Stack.h          -*-C++-*-
// -------------------------------------------------------
// Algorithm Library Design. Juha K"arkk"ainen, 2003/06/17
// A simple stack class template


// a stack implemented as a singly-linked list
template <class T>
class Stack {

  // list node
  struct Node {
    T data;
    Node* next;
  };

  // recursive list copy
  Node* copy(Node* orig) {
    Node* cp = 0;
    if (orig) {
      cp = new Node(*orig);
      cp->next = copy(orig->next);
    }
    return cp;
  }

  // head of the list
  Node* head;

public:

  Stack() : head(0) {}
  Stack(const Stack& other) : head(copy(other.head)) {}
  ~Stack() { while (!empty()) pop(); }

  Stack& operator=(const Stack& rhs) {
    while (!empty()) pop();
    head = copy(rhs.head);
    return *this;
  }

  bool empty() const { return head == 0; }

  void push(const T& t) {
    Node* newnode = new Node;
    newnode->next = head;
    head = newnode;
    head->data = t;
  }

  T pop() {
    if (empty()) throw "pop() in empty stack";
    Node* tmp = head;
    head = head->next;
    T value = tmp->data;
    delete tmp;
    return value;
  }

};