/* This file contains the declaration of a Stack class template.
...
-------------------------------------------------------------------*/

#ifndef STACK
#define STACK

#include <iostream.h>

template <class StackElem>        // a Stack of StackElem values
class Stack
{
   struct StackNode               // nodes to store & link StackElems
   {
      StackElem
         Element;                 // the node's data member
      StackNode
         *Next;                   // the node's link member

      StackNode(void)             // default class constructor
      {
         Next = 0;
      }

      StackNode(StackElem Elem,   // initialization class constructor
                StackNode *Nptr = 0)
      {
         Element = Elem;
         Next = Nptr;
      }

      ~StackNode() { delete Next; }

   };

   typedef StackNode *SNodePtr;   // pointer-type to a node

   SNodePtr
      Top;                        // the top node on the stack

public:

   Stack(void) { Top = 0;}                  // constructor: empty stack

   ~Stack(void)                             // deallocate a Stack
   {                                        //  using recursive
      delete Top;                           //  Top->~StackNode()
      Top = 0;                              //  and reset Top
   }

   void Push(StackElem Elem)                // push an element onto
   {                                        //   the stack using the
      Top = new StackNode(Elem, Top);       // StackNode constructor
   }

   StackElem Pop();                         // remove top element

   int Empty(void) const {return Top == 0;} // is the stack empty?
   int Full(void) const {return 0;}         // is the stack full?

   friend ostream& operator<<(ostream& Out, // display the stack
                              const Stack<StackElem>& S);
};

template <class StackElem>
StackElem Stack<StackElem>::Pop(void)       // remove top element
{
   StackElem
      Elem = Top->Element;                  // save return-value
   Stack<StackElem>::SNodePtr
      NodePtr = Top;                        // save ptr to top node

   Top = Top->Next;                         // update Top
   NodePtr->Next = 0;                       // detach old top node
   delete NodePtr;                          // deallocate it
   return Elem;                             // return its value
}

template <class StackElem>
ostream& operator<<(ostream& Out,           // interactive output
                    const Stack<StackElem>& St)
{
   Stack<StackElem>::SNodePtr
      NodePtr = St.Top;                     // start at the top

   while (NodePtr != 0)                     // while not at bottom
   {
      Out << NodePtr->Element << endl;      //   display node's data
      NodePtr = NodePtr->Next;              //   move down 1 node
   }

   return Out;                              // allow chaining
}

#endif