Scientific Programming II

ModSim

Queues

What is a queue?

In this unit, we will simulate the line at a single check-out counter in a supermarket. We will use a queue to represent the customers in the line. Typically, customers arrive at a certain rate and are processed at a certain rate. If the arrival rate of the customers is significantly more than their processing rate or vice versa, the line grows very quickly.

Queues are a special form of a linked list (or other one-dimensional data structure) with the following restrictions:

• Additions can be only be made at the back
• Deletions can only occur from the front

Queues are considered a FIFO (first in, first out) data structure. We will edit our original linked list files such that insertions only happen from the back of the list and deletions only happen from the front of the list. We will retain the methods which would allow us to print the list and check to see if the list is empty or not.

Queues are quinessentially Linked Lists with three methods:

• public void enqueue(T val) - Add a value to the Queue
• public T dequeue() - Remove a value from the Queue
• public boolean isEmpty() - Test if the Queue is empty
• public String toString() - Convert the Queue into a String
  

Using Queues

Queues are useful in several different scenarios, the obvious example being a supermarket checkout queue. Additionally, however, they allow an elegant and simple solution to the Knights of the Round Table problem. Is is as follows:

import java.util.Scanner;

public class Knights
{
    public static void main(String[] args)
    {
        Scanner scan = new Scanner(System.in);
        System.out.println("Knights of the Round Table");
        System.out.print("Enter a number between 1 & 9: ");
        int m = scan.nextInt();
        Queue knights = new Queue();
        for (int i = 1; i < 10; i++) {
            knights.enqueue(i);
        }

        while (knights.length() > 1) {
            for (int i = 0; i < m; i++) {
                knights.enqueue(knights.dequeue());
            }
            knights.dequeue();
        }

        System.out.println("Knight leader: " + knights.dequeue().getData());
    }
}