Queue ADT

We can make an ADT that implements a queue, and then use it over and over again.  For example, the Counselling program could conatain 2 queues - one for students, and one for teachers.  Then we'd like to write the Counselling program something like this pseudocode:

class Conselling
{  
    Queue studentQ = new Queue();
    Queue teacherQ = new Queue();

    actions
    {
       when student arrives
       {
           who = new student()
           who.setName ...
           studentQ.enqueue( who )
       }
       when teacher arrives
       {
           who = new teacher()
           who.setName
           teacherQ.enqueue( who )
       }    
       when sending in the next person
       {
           if (teacherQ is not empty)
           {  
              who = teacherQ.dequeue() 
              call who.name
           }
           else if (studentQ is not empty)
           {
              who = studentQ.dequeue() 
              call who.name
           }   
           else
           {  send counsellor to lunch }
       }
    }
}

To make this work, we need an ADT class called Queue, with an array to hold the people, and methods to do the following:
      initialize - makes the queue empty
      enqueue - add a new person into the queue
      dequeue - remove a person from the queue and return the person to the main program
      checkEmpty - checks whether the queue is empty, returning true or false
      The array probably needs a front pointer and a back pointer to keep track of where the data is stored

Putting the array, pointers, and methods all inside a Queue class is called encapsulation.  This makes it easy to re-use the code - e.g. to make two separate queues without rewriting any code.

1. The Counselling program has been rewritten, but does not contain the Queue class.  Get a copy of the new Conselling program, write the queue class, and make the whole thing work correctly.  You might wish to look at the sample code in previous notes.  This should take 1 class period (plus some time at home if necessary). If you don't make sufficiently rapid progress, GET HELP FROM THE TEACHER!

2. Write a stack class.  This is very similar to a queue, but works in LIFO mode instead of FIFO.  Change your counselling program to use stack logic instead of queue logic.  This should take at most 2 class period (plus time at home if necessary).

3. Check that both your stack and queue classes are correctly protected agains overflow and underflow errors by letting another student test your programs. To test the overflow handling, make the array very small (say 3 names), so you can “provoke” an overflow error without typing in hundreds of names.

4. Prepare for a written test about stacks, queues, and OOP on Monday, 11 Sep. The teacher will give you some study questions next week.

/******************************************
This version of the counselling program only records names,
and only has a single Person class.  This allows us to concentrate
on programming the QUEUE class.
********************************************/

import java.awt.*;

public class CounsellingQ extends EasyApp
{   
   public static void main(String[] args)
   {  new CounsellingQ();  }   

   Button bTeacher = addButton("Teacher",50,50,100,50,this);
   Button bStudent = addButton("Student",150,50,100,50,this);
   Button bNext = addButton("Next",250,50,100,50,this);
   
   Queue studentQ = new Queue();
   Queue teacherQ = new Queue();
   
   public CounsellingQ()
   {   
      setSize(400,200);
      setVisible(true);
   }
   
   public void actions(Object source,String command)
   {
      if (source == bTeacher)
      {  
         Person who = new Person();
         String name = input("Name?");
         ________.setName(name);
         ________.enqueue(who);
      }
      else if (source == bStudent)
      {
         Person who = new Person();
         String name = input("Name?");
         ________.setName(name);
         ________.enqueue(who);         
      }
      else if (source == bNext)
      {
         if (______________________________)
         {
            Person who = teacherQ.________();
            output(who.name);
         }
         else if (_______________________________)
         {
            Person who = studentQ.________();
            output(who.name);            
         }
         else
         {  output("Nobody waiting - go to lunch"); }
      }
   }
}

class Person
{
   String name = "";
   
   public String getName()
   {
      return name ;
   }   
   
   public void setName(String n)
   {
      name = n;
   }
}

class Queue
{
   Person[] list = _________________________;
   int front = _______;
   int back = ________;
   
   public void enqueue(Person who)
   {
      if (______________________)
      {  
         back = ______________;
         ____________ = who;
      }   
   }
   
   public Person dequeue()
   {
      if (_________________)
      {
         front = _____________;
         return _______________;
      }
      else
      {  return null; }         
   }
   
   public boolean checkEmpty()
   {
      if (________________)
      {  return true; }
      else
      {  return false; }
   }
}