#ifndef __STACKD_H_
#define __STACKD_H_
#include <cstdlib>

template <class T>
class stackd {
private:
   struct Node {
      T data;
      Node* next;
   };
   Node* head;
public:
   stackd();
   stackd(const stackd& s);
   ~stackd();
   bool isEmpty() const;
   bool isFull() const;
   bool push(const T data);
   bool pop(T& data);
   stackd& operator=(const stackd& s);
};

template <class T>
stackd<T>::stackd() { head = NULL; }

template <class T>
stackd<T>::stackd(const stackd& s) {
   Node* p = s.head;
   Node* prev = NULL;
   while (p != NULL) {
      // create new node
      Node* n = new Node();
      if (n == NULL) return;   // unrecoverable error
      n->data = p->data;
      n->next = NULL;

      // set up pointers
      if (prev == NULL) head = n;  // first node in stack/list
      else prev->next = n;

      // get ready for next pass
      prev = n;
      p = p->next;
   }
}

template <class T>
stackd<T>& stackd<T>::operator=(const stackd<T>& s) {
   if (this == &s) return *this;
   T tmp;
   while (!isEmpty()) pop(tmp);
   Node* p = s.head;
   Node* prev = NULL;
   while (p != NULL) {
      // create new node
      Node* n = new Node();
      if (n == NULL) return *this;  // unrecoverable error
      n->data = p->data;
      n->next = NULL;

      // set up pointers
      if (prev == NULL) head = n;   // first node in stack/list
      else prev->next = n;

      // get ready for next pass
      prev = n;
      p = p->next;
   }
   return *this;
}

template <class T>
stackd<T>::~stackd() {
   T tmp;
   while (!isEmpty()) pop(tmp);
}

template <typename T>
bool stackd<T>::isEmpty() const { return head==NULL; }

template <class T>
bool stackd<T>::push(const T data) {
   Node* n = new Node();
   if (n==NULL) return false;
   n->data = data;
   n->next = head;
   head = n;
   return true;   
}

template <class T>
bool stackd<T>::pop(T& data) {
   if (isEmpty()) return false;
   Node* tmp = head;
   data = head->data;
   head = head->next;
   delete tmp;
   return true;
}

#endif