// Lab 10 source code for a stack. Last updated May 1, 2000, by Rick Wagner.

#include <iostream.h>
#include <string.h>

// Node class definition:
template <class Item>
class Node                                               // Node for use with the Stack class defined below.
{                                                        // Data items stored in a node must have a copy
public:
  Node();                                                // Default constructor.
  Node(const Item& data);                                // Data constructor.
  ~Node();

  void setData(const Item& data);                        // Mutators
  void setNext(Node* next);

  Item getData() const;                                  // Accessors
  Node* getNext() const;

private:
  Node* _next;                                           // Pointer to the next node.
  Item* _data;                                           // Pointer to the data contained in the node.
};

// Default Node constructor:
template <class Item>
Node<Item>::Node()
{
  _next = NULL;                                          // Default is an empty node with no next node.
  _data = NULL;
}

// One parameter Node constructor:
template <class Item>
Node<Item>::Node(const Item& data)
{
  _data = new Item(data);                                // Makes copy of the input data.
  _next = NULL;                                          // No next node by default.
}

// Node destructor:
template <class Item>
Node<Item>::~Node()
{
  if (_data != NULL) delete _data;                       // Give back the memory for data storage.
}

// Node mutators:
template <class Item>
void Node<Item>::setData(const Item& data)
{
  if (_data != NULL) delete _data;                       // Prevent memory leaks.
  _data = new Item(data);                                // Makes a copy of the input data.
}

template <class Item>
void Node<Item>::setNext(Node* next)
{
  _next = next;
}

// Node accessors:
template <class Item>
Item Node<Item>::getData() const
{
  return *_data;
}

template <class Item>
Node<Item>* Node<Item>::getNext() const
{
  return _next;
}

// Stack class definition:
template <class Item>                                    // A versatile stack ADT.
class Stack
{
public:
  Stack();                                               // Default constructor.
  ~Stack();                                              // Destructor (doesn't need a copy constructor).

  void push(const Item& entry);                          // Mutators
  Item pop();

  int empty();                                           // Accessors
  Item peek();

private:
  Node<Item>* _top;                                      // Data are stored in a sequence of linked nodes.
};

// Stack default constructor:
template <class Item>
Stack<Item>::Stack()
{
  _top = NULL;                                           // Empty stack by default.
}

// Stack destructor:
template <class Item>
Stack<Item>::~Stack()
{
  Item temp;

  while (_top != NULL)
  {
    temp = pop();
  }
}

// Stack push() implementation:
template <class Item>
void Stack<Item>::push(const Item& entry)
{
  Node<Item>* temp;
  temp = new Node<Item>(entry);
  temp->setNext(_top);
  _top = temp;
}

// Stack pop() implementation:
template <class Item>
Item Stack<Item>::pop()
{
  Item temp = NULL;
  Node<Item>* next;

  if (_top != NULL)
  {
    temp = _top->getData();
    next = _top->getNext();
    delete _top;
    _top = next;
  }
  else
  {
    cout << "Attempt to pop an empty stack!";
  }
  return temp;
}

// Stack empty() implementation:
template <class Item>
int Stack<Item>::empty()
{
  if (_top == NULL)
  {
    return 1;
  }
  else
  {
    return 0;
  }
}

// Stack peek() implementation:
template <class Item>
Item Stack<Item>::peek()
{
  Item temp = NULL;

  if (_top != NULL)
  {
    temp = _top->getData();
  }
  return temp;
}

// Test a few stack functions:
void main()
{
  Stack<int> s;
  int i = 0;

  for (i = 0; i < 10; i++)
  {
    s.push(i);
    cout << s.peek();
  }
  cout << endl;

  while (!s.empty())
  {
    cout << s.pop();
  }
  cout << endl;
}