Queues in the Counselling Office

Imagine students are sitting in the counselling office on a row of chairs, waiting to talk to the counselor..  Each new student sits behind the last student.  There are 5 chairs.

>> Empty (beginning of the day)
 
:______:    :_____:    :_____:    :_____:    :_____:
   1           2          3          4          5
 
>> First student arrives (Al)
 
:__Al__:    :_____:    :_____:    :_____:    :_____:
   1           2          3          4          5
 
>> Second student arrives (Betty)
 
:__Al__:   :_Betty_:   :_____:    :_____:    :_____:
   1           2          3          4          5
 
|>> Al goes into the counselor's office
 
:______:   :_Betty_:   :_____:    :_____:    :_____:
 
   1           2          3          4          5
 
>> Carla arrives
 
:______:   :_Betty_:  :_Carla_:   :_____:    :_____:
 
   1           2          3          4          5
 
>> Doug arrives
 
:______:   :_Betty_:  :_Carla_:   :_Doug_:   :_____:
 
   1           2          3          4          5
 
>> Betty goes into counselor's office
 
:______:   :_______:  :_Carla_:   :_Doug_:   :_____:
 
   1           2          3          4          5
 

Question 1:  Who is "next in line" to see the counselor now?

Question 2: What happens if 2 more students come into the office?
      Where should they sit?

If the students are not very organized, or if the chairs are scattered around, or if there are lots more chairs,
it might be useful to have a computer where the students "sign in".  Then they can sit wherever they like.  
Indeed, they could go back outside for a few minutes without "losing their place."
Whenever a student leaves, the counselor presses the "next" button on the computer,
and it tells who is next in line. 

The WAITING program uses a queue to keep track of students waiting in the counselor's office.
A queue is a FIFO data structure = First In, First Out.

Notice that the subroutines are generic – that is, the operations Initialize, EnQueue, and Dequeue would be needed in any queue in any application.  The same ideas could be used to manage a queue of patients in a doctor's office, a queue of print jobs in a print server (spooling), and in many other practical situations.

Question 3:  What is the meaning of the variables  Head and Tail?  
       How many "chairs" does the program have?

Notice that the DeQueue command is a Function. Why? Because it outputs a name, so it returns a result. On the other hand, the EnQueue command accepts an Input Parameter – the name which is entering (input) the queue.

Question 4: It is quite possible that the Queue will overflow.  This could be solved by allocating more memory. However, as the day progresses, the data "crawls" through the queue, so even with 100 positions it is conceivable that the Tail pointer could overflow. Suggest a solution to this problem.  Which method must be changed?

/**************************************************\
WAITING QUEUE

This program inputs names and adds them to a QUEUE.
When the Leave button is clicked, it gets retrieves
the name from the HEAD of the queue and displays it.
This is useful for keeping a queue of names for
people waiting for a service, for example in a
doctor's office.

\**************************************************/

public class WaitingQueue
{ 
  String[] queue = new String[10];
  int head, tail;
 
  public WaitingQueue()
  {
     initialize();
    
     String command = "";
     while(true)
     {
        command = input("In/Out/Quit");
        command = command.toUpperCase();
        if(command.equals("IN"))
        {
           String newName = input("Type name to be added to the queue:");
           enqueue(newName);
           display();
        }
        if(command.equals("OUT"))
        {
           String name = dequeue();
           output("Next person is " + name); 
           display();
        }
        if(command.equals("QUIT"))
        {
           System.exit(0);
           display();
        }        
     }
  }
 
  void initialize()
  {
    head = 0;
    tail = -1;
  }
 
  void enqueue(String thisName)
  {
    tail = tail + 1;
    queue[tail] = thisName;
  }
 
  String dequeue()
  {
    if(head <= tail)
    {
      String name = queue[head];
      head = head + 1;
      return name;
    }  
    else
    {
      return "";
    }
  }
 
  void display()
  {
    String answer = "";
    for(int x = head; x <= tail; x = x+1)
    {
      answer = answer + queue[x] + "\n";
    }
    output(answer);
  }
 
  public static void main(String[] args)
  {  new WaitingQueue(); }
 
  public void output(String message)
  {  javax.swing.JOptionPane.showMessageDialog(null,message);  }
 
  public String input(String prompt)
  {  return javax.swing.JOptionPane.showInputDialog(null,prompt);  }
}

In our counselling office, there are actually three counselors – Starns, Reeves, and Kraus.
Kraus takes care of grades 7 and 9, Reeves takes care of grades 6, 8, and 10, and Starns takes care
of grades 11 and 12.

To add a second queue, the functions and procedures must all be duplicated and changed.

Problem 5:  Add all the necessary code to create a program with 2 queues.  If you manage that correctly, you probably don't need to make the third queue.

Problem 6:  What if a teacher comes in and wants to "cut in line"?  How can the program place a teacher at the front of the line (but the teacher must still wait until the student leaves the counselor's office)?

Problem 7: What does the following procedure do to the students in the queue?

What happens if the problem procedure runs when the queue is empty?

Problem 8:  What does the following function do?

Problem 9:  Without using the computer, write a method which exchanges the 1st and 2nd names
     in the queue, thus "moving up" the 2nd person to the head of the line.

Problem 10: Find out what a stack is, and how it behaves differently from a queue.