/* Stack.h provides a Stack template class, containing both its
   declarations and definitions.

   Begun by: Joel C. Adams, Spring 1994 at Calvin College.
   Completed by:
   Written for: Hands On C++, Lab 17.
----------------------------------------------------------------*/

#ifndef STACK
#define STACK

#include <iostream.h>  // ostream, operator<<
#include <ctype.h>     // isspace()
#include <assert.h>    // assert()

template<class DataType>
class Stack
{
 protected:

  struct Node
    {
      DataType
        Data;
      Node
        *Next;

      /* --- The default Node constructor builds a Node whose
                Data member remains undefined.

          Precondition: A Node has been defined (no arguments).
          Postcondition: Its Next member is initialized to NULL.
      ----------------------------------------------------------*/
      Node() {Next = 0;}

      /* --- The second Node constructor builds a Node whose
                Data and Next members are both defined.

          Precondition: A Node has been defined (with arguments).
          Receive: DataVal, a DataType value; and
                   NextVal, a pointer to a Node (default NULL).
          Postcondition: Data and Next have been initialized to
                          DataVal and NextVal, respectively.
      ----------------------------------------------------------*/
      Node(DataType DataVal, Node *NextVal = 0)
        {
          Data = DataVal;
          Next = NextVal;
        }

      /* --- The Node destructor reclaims a Node and all Nodes
             that follow it.

            Precondition: The lifetime of a Node is over.
            Postcondition: Its storage has been reclaimed
                    (as well as all Nodes that follow it).
      ----------------------------------------------------------*/
      ~Node() { delete Next;}

      /* --- The Node copy constructor makes a copy of a Node.

          Precondition: A copy of a Node is needed.
		  Receive: OrigNode, (a reference to) the Node to be copied.
		  Postcondition: A copy of OrigNode has been made.
      -----------------------------------------------------------*/
      Node(const Node& OrigNode)
        {
          Data = OrigNode.Data;

          if (OrigNode.Next == 0)
            Next = 0;
          else
            Next = new Node(*OrigNode.Next);
        }
    };

  typedef Node * NodePtr;

  // declare Top as a NodePtr here

 public:

  /* --- The Stack constructor initializes a Stack as empty.

     Precondition: A Stack has been declared.
     Postcondition: It has been initialized as an empty stack.
  ------------------------------------------------------------*/
  // define Stack constructor here


  /* --- The Stack destructor reclaims the storage of a Stack.

     Precondition: The lifetime of a Stack is over.
     Postcondition: It's storage has been reclaimed.
  ------------------------------------------------------------*/
  // define Stack destructor here


  /* --- The copy constructor makes a copy of a Stack.

     Precondition: A copy of a Stack is needed.
     Receive: OrigStack, (a reference to) the Stack to be copied.
     Postcondition: A copy of OrigStack has been made.
  --------------------------------------------------------------*/
//  Stack(const Stack<DataType>& OrigStack);

  /* --- Empty() determines if a Stack is empty or not.

     Receive: A Stack.
     Return: True, if the Stack is empty, False otherwise.
  -------------------------------------------------------------*/
  // define Empty() here


  /* --- Full() determines if a Stack is full or not.

     Receive: A Stack.
     Return: True, if not values can be added to the Stack,
              False otherwise.
  --------------------------------------------------------------*/
  // declare Full() here


  /* --- Push() adds a value to a Stack.

     Receive: A Stack;
             DataVal, a DataType value.
     Return: The Stack, containing DataVal in its 'most recently
              added' position.
  ---------------------------------------------------------------*/
  // declare Push() here



  /* Pop() retrieves and removes a value from a Stack.

     Receive: A Stack;
             DataVal, a DataType variable.
     Return: DataVal, containing the 'most recently added' value;
             The Stack, minus its 'most recently added' value.
  ---------------------------------------------------------------*/
  // declare Pop() here


  /* --- Operator << displays the contents of a Stack.

     Receive: Out, an ostream;
              aStack, a Stack.
     Output: The values in aStack, via Out.
     Pass back: Out, containing the output values.
     Return: Out, for chaining.
  ---------------------------------------------------------------*/
  // declare operator<< here

};

// ********** Definitions of (Nontrivial) Stack Operations ********

/* --- The copy constructor makes a copy of a Stack.

     Precondition: A copy of a Stack is needed.
     Receive: OrigStack, (a reference to) the Stack to be copied.
     Postcondition: A copy of OrigStack has been made.
--------------------------------------------------------------*/

// define the Stack copy constructor here



/* --- Full() determines if a Stack is full or not.

     Receive: A Stack.
     Return: True, if not values can be added to the Stack,
              False otherwise.
--------------------------------------------------------------*/

// define Full() here



/* --- Push() adds a value to a Stack.

     Receive: A Stack;
             DataVal, a DataType value.
     Return: The Stack, containing DataVal in its 'most recently
              added' position.
---------------------------------------------------------------*/

// define Push() here



/* Pop() retrieves and removes a value from a Stack.

     Receive: A Stack;
             DataVal, a DataType variable.
     Return: DataVal, containing the 'most recently added' value;
             The Stack, minus its 'most recently added' value.
---------------------------------------------------------------*/

// define Pop() here



/* --- Operator << displays the contents of a Stack.

	 Receive: Out, an ostream;
              aStack, a Stack.
     Output: The values in aStack, via Out.
     Pass back: Out, containing the output values.
     Return: Out, for chaining.
 ---------------------------------------------------------------*/

 // define operator<< here


#endif