CPSC 215 Lab 12, 12/9/99

 		 Data Structures and Algorithms in C++

 
  This lab allows you to apply the basic computer science principles
you've learned this semester to a slightly different programming language.


"delete" is not working properly in codewarrior, but the example shown
in class is correct for "ansi standard" C++.


  A stack is a structure, usually implemented as a linked list, where 
new elements are inserted to the front, and also deleted from the front.

  A queue is a structure where new elements are inserted at the end,
but deleted from the front.



Using the basic list "cell" class, you are to implement the basic operations
on stacks and queues.

class cell
{ public:
   int head;  
   cell *tail;
   cell(int h, cell *t) { head = h;  tail = t; }
};   // don't forget the extra ;!

class stack
{ private:
  cell *top;   // same as a "front" pointer, but called "top" of the stack.
	       // This is private so only push/pop can be used.
  public:
   stack() { top = 0; } // constructor.  Initially, the stack is empty (0=null)
   
   void push(int x)     // pushes x on top of the stack
     {  top = new cell(x,top); }

   int pop()      //  should delete the top cell of the stack, and return
     		  //  the value (head) stored there.
                  //  Hint: after saying "top = top->tail", you need to
		  //  "delete" the old cell that top pointed to previously.
   int empty()    //  should return 1 if the stack is not empty, 0 otherwise

   ~stack()    // destructor - might not work with codewarrior C++
     { cell *current;
       cell *temp;
       current = top;
       while (current != 0)  // must delete each cell individually
        { temp = current->tail;
          delete(current);   // current is now effectively null
          current = temp;
        }
     } // end destructor
};  // end class stack


Similarly, define a class "queue" with the following methods:

void enqueue(int x) // inserts a cell with x to the end of the queue

int dequeue() // deletes the cell at the "front" of the queue, return the value

int empty()  //  should be same as empty() for stacks

~queue() // destructor - should be same as destructor for stacks.


int main()    // main method
{
/* demonstrate your code here.
   Use cin and cout to ask the user to input values:
*/
 
// for example:
stack *mystack;
mystack = new stack();
int i, x;
for(i=0;i<5;i++)
  { cout << "enter a number: ";
    cin >> x;   // get number from user, store number in x;
    mystack->push(x);  // should push x on top of the stack
  }

// use another loop to pop and print the contents of the stack,
// and similarly for queues.

  return 0;
} // end main


/* This assignment must be completed by 4pm today */