//////////////////////////////////////////////////////////////////////////////////////////////
//                                                                                          //
//                 CSE 428, Spring 2001, code for first exercise of HW #3                   //
//                                                                                          //
//                               File A3_code_stack_simple.C                                //
//                                                                                          //
//                      Simplified version, without memory leaks tests                      //
//                                                                                          //
//////////////////////////////////////////////////////////////////////////////////////////////

const int NULL = 0;


#include <iostream>
using namespace std;

//////////////////////////////////////////////////////////////////////////////////////////////

class element { // This is an auxiliary class for stack1. It defines the elements of stack1

   int info;        // information content of an element
   element* next;   // pointer to the next (previously inserted) element in the stack

   element(int n, element* e)  // Constructor method for an element
   {
      info = n;
      next = e;
   }
 
   friend class stack1;
   // stack1 is a friend class: it can access all (private) fields and members of element
};

/////////////////////////////////////////////////////////////////////////////////////////////

class stack1 { // In this implementation, a stack is an object "stack1" which contains
               // the pointer to the first element (top) of a linked list of elements
private:

   element* top;  // pointer to the top element in the stack

public:

   stack1()  // Constructor of an empty stack
   {
      top = NULL;
   }

   void push(int n) // insert an element at the top of the stack
   {
      top = new element(n,top);
   }

   //////////////////////  THE FOLLOWING METHODS ARE TO BE DEFINED /////////////////////////

   ~stack1(); // destructor

   void pop(); // removes the element at the top

   int position(int x);
   // This function returns the position in the stack of the x last inserted and not yet
   // removed:
   // It returns 1 if x is at the top, 2 if x is in the second element from the top,  etc.
   // If x is not in the stack, it returns 0.
};

///////////////////////////////////////////////////////////////////////////////////////////////

class stack2 { // In this implementation, an object "stack2" is the first
               // element of a linked list of elements. The significant part
               // of the stack starts from the second element of the list (top)
               // the info field in the first element of the list is not used
private:
     
   int info;     // information content of an element of the stack
   stack2* next; // pointer to the next element

   stack2(int n, stack2* s) // Private constructor for the insertion of a new element
   {
      info = n;
      next = s;
   }

public:
   stack2()  // Constructor. It constructs a stack whose significant part is empty
   {
      next = NULL;
   }

   void push(int n) // insert an element at the top of the stack
   {
      next = new stack2(n,next);
   }

   ~stack2() // destructor
   {
      delete next;
   }

   //////////////////////  THE FOLLOWING METHODS ARE TO BE DEFINED ////////////////////////

   void pop(); // remove the element at the top

   int position(int x);
   // This function returns the position in the stack of the x last inserted and not yet
   // removed:
   // It returns 1 if x is at the top of the stack, namely, in the second element of the
   // linked list. It returns 2 if x is in the third element of the list,  etc.
   // If x is not in the list, it returns 0.
};

///////////////////////////////////////////////////////////////////////////////////////////////
// Examples of use of the stacks

int main()
{
   //////////////////////////////////////////////////////////////////////////////////////////
   // Same operations on a stack of type stack1

   stack1* s1 = new stack1();
   s1->push(5);
   s1->push(5);
   s1->push(6);
   s1->push(7);

   cout << "the last inserted " << 5 << " is in position " << s1->position(5) << "\n";  
                //It should print 3

   s1->pop();   //It should eliminate the top element without leaving memory leaks
                //and without creating dangling references

   cout << "the last inserted " << 5 << " is in position " << s1->position(5) << "\n";  
                //It should print 2

   delete s1;   //It should eliminate the stack without leaving memory leaks
   s1 = NULL;

   //////////////////////////////////////////////////////////////////////////////////////////
   // Now we perform similar operations on a stack of type stack2

   stack2* s2 = new stack2();
   s2->push(5);
   s2->push(6);
   s2->push(6);

   cout << "the last inserted " << 6 << " is in position " << s2->position(6) << "\n";  
                //It should print 1

   s2->pop();   //It should eliminate the top element without leaving memory leaks
                //and without creating dangling references

   s2->push(7);
   s2->push(8);
   s2->push(9);
   cout << "the last inserted " << 6 << " is in position " << s2->position(6) << "\n";  
                //It should print 4

   delete s2;   //It eliminates the stack without leaving memory leaks
   s2 = NULL;
}

///////////////////////////////////////////////////////////////////////////////////////////////