3.3 Queue

A queue is an ordered collection of items where the addition of new items happens at one end, called the "rear", and the removal of existing items occurs at the other end, commonly called the "front". As an element enters the queue it starts at the rear and makes its way toward the front, waiting until that time when it is the next element to be removed.

The most recently added item in the queue must wait at the end of the collection. The item that has been in the collection the longest is at the front. This ordering principle is sometimes called FIFO, first-in first-out. It is also known as "first-come first-served".

The simplest example of a queue is the typical line that we all participate in from time to time. We wait in a line for a movie, we wait in the check-out line at a grocery store, and we wait in the cafeteria line (so that we can pop the tray stack). Well-behaved lines, or queues, are very restrictive in that they have only one way in and only one way out. There is no jumping in the middle and no leaving before you have waited the necessary amount of time to get to the front.

Computer science also has common examples of queues. Let's take an office with 30 computers networked with a single printer. When employees want to print, their print tasks "get in line" with all the other printing tasks that are waiting. The first task in is the next to be completed. If you are last in line, you must wait for all the other tasks to print ahead of you. We will explore this interesting example in more detail later.

In addition to printing queues, operating systems use a number of different queues to control processes within a computer. The scheduling of what gets done next is typically based on a queuing algorithm that tries to execute programs as quickly as possible and serve as many users as it can. Also, as we type, sometimes keystrokes get ahead of the characters that appear on the screen. This is due to the computer doing other work at that moment. The keystrokes are being placed in a queue-like buffer so that they can eventually be displayed on the screen in the proper order.

3.3.1 The Queue Abstract Data Type

The queue abstract data type is defined by the following structure and operations. A queue is structured, as described above, as an ordered collection of items which are added at one end, called the "rear", and removed from the other end, called the "front". Queues maintain a FIFO ordering property. The queue operations are given below.

• Queue() creates a new queue that is empty. It needs no parameters and returns an empty queue.
• enqueue(item) adds an item to the rear of the queue. It needs the item and returns nothing.
• dequeue() removes the front item from the queue. It needs no parameters and returns the item. The queue is modified.
• isEmpty() tests to see whether the queue is empty. It needs no parameters and returns a boolean value.
• size() returns the number of items in the queue. It needs no parameters and returns an integer.

As an example, if we assume that q is a queue that has been created and is currently empty, then the following table shows the results of a sequence of queue operations. The queue contents are shown such that the front is on the right. 4 was the first item enqueued so it is the first item returned by dequeue.

3.3.2 Implementing a Queue in JavaScript

It is again appropriate to create a new class for the implementation of the abstract data type queue. As before, we will use the power and simplicity of the list collection to build the internal representation of the queue.

We need to decide which end of the list to use as the rear and which to use as the front. The implementation I propose assumes that the rear is at position 0 in the list.

class Queue {
    constructor() {
        this.items = [];
    }

    isEmpty() {
        return (this.items.length === 0);
    }

    enqueue(item) {
        this.items.unshift(item);
    }

    dequeue() {
        return this.items.pop();
    }

    size() {
        return this.items.length;
    }
}

export default Queue;

Manipulation of this queue would give the following results:

var q = new Queue();

console.log( q.isEmpty() ); // true
q.enqueue(8.4);
q.enqueue('banana')
console.log( q.size() ); // 2
console.log( q.dequeue() ); // 8.4
console.log( q.isEmpty() ); // false
console.log( q.size() ); // 1

3.3.3 Simulation: Hot Potato

One of the typical applications for showing a queue in action is to simulate a real situation that requires data to be managed in a FIFO manner. To begin, let’s consider the children’s game Hot Potato. In this game children line up in a circle and pass an item from neighbor to neighbor as fast as they can. At a certain point in the game, the action is stopped and the child who has the item (the potato) is removed from the circle. Play continues until only one child is left.

We will implement a general simulation of Hot Potato. Our program will input a list of names and a constant, call it "num", to be used for counting. It will return the name of the last person remaining after repetitive counting by num. What happens at that point is up to you.

To simulate the circle, we will use a queue. Assume that the child holding the potato will be at the front of the queue. Upon passing the potato, the simulation will simply dequeue and then immediately enqueue that child, putting her at the end of the line. She will then wait until all the others have been at the front before it will be her turn again. After num dequeue/enqueue operations, the child at the front will be removed permanently and another cycle will begin. This process will continue until only one name remains (the size of the queue is 1).

A call to the hotPotato function using 7 as the counting constant returns Susan.

import Queue from './queue.js';

function hotPotato(namelist, num) {
    var simqueue = new Queue();

    for (let i = 0; i < namelist.length; i++) {
        simqueue.enqueue(namelist[i]);
    }

    while (simqueue.size() > 1) {
        for (let i = 0; i < num; i++) {
            simqueue.enqueue(simqueue.dequeue());
        }
        simqueue.dequeue();
    }

    return simqueue.dequeue();
}

console.log( hotPotato(['Bill', 'David', 'Susan', 'Jane', 'Kent', 'Brad'],7) );

Note that in this example the value of the counting constant is greater than the number of names in the list. This is not a problem since the queue acts like a circle and counting continues back at the beginning until the value is reached. Also, notice that the list is loaded into the queue such that the first name on the list will be at the front of the queue. Bill in this case is the first item in the list and therefore moves to the front of the queue.

3.3.4 Simulation: Printing Tasks

A more interesting simulation allows us to study the behavior of the printing queue described earlier in this section. Recall that as employees send printing tasks to the shared printer, the tasks are placed in a queue to be processed in a first-come first-served manner. Many questions arise with this configuration. The most important of these might be whether the printer is capable of handling a certain amount of work. If it cannot, employees will be waiting too long for printing and may miss their next meeting.

Consider the following situation in an office. On any average day about 10 employees are working in the office at any given hour. These employees typically print up to twice during that time, and the length of these tasks ranges from 1 to 20 pages. The printer in the lab is older, capable of processing 10 pages per minute of draft quality. The printer could be switched to give better quality, but then it would produce only five pages per minute. The slower printing speed could make employees wait too long. What page rate should be used?

We could decide by building a simulation that models the office. We will need to construct representations for employees, printing tasks, and the printer. As employees submit printing tasks, we will add them to a waiting list, a queue of print tasks attached to the printer. When the printer completes a task, it will look at the queue to see if there are any remaining tasks to process. Of interest for us is the average amount of time employees will wait for their papers to be printed. This is equal to the average amount of time a task waits in the queue.

To model this situation we need to use some probabilities. For example, employees may print a paper from 1 to 20 pages in length. If each length from 1 to 20 is equally likely, the actual length for a print task can be simulated by using a random number between 1 and 20 inclusive. This means that there is equal chance of any length from 1 to 20 appearing.

If there are 10 students in the lab and each prints twice, then there are 20 print tasks per hour on average. What is the chance that at any given second, a print task is going to be created? The way to answer this is to consider the ratio of tasks to time. Twenty tasks per hour means that on average there will be one task every 180 seconds:

$$\frac {20\ tasks}{1\ hour} \times \frac {1\ hour} {60\ minutes} \times \frac {1\ minute} {60\ seconds}=\frac {1\ task} {180\ seconds}$$

For every second we can simulate the chance that a print task occurs by generating a random number between 1 and 180 inclusive. If the number is 180, we say a task has been created. Note that it is possible that many tasks could be created in a row or we may wait quite a while for a task to appear. That is the nature of simulation. You want to simulate the real situation as closely as possible given that you know general parameters.

3.14.1. Main Simulation Steps

Here is the main simulation.

1. Create a queue of print tasks. Each task will be given a timestamp upon its arrival. The queue is empty to start.
2. For each second (currentSecond):
   1. Does a new print task get created? If so, add it to the queue with the currentSecond as the timestamp.
   2. If the printer is not busy and if a task is waiting,
      1. Remove the next task from the print queue and assign it to the printer.
      2. Subtract the timestamp from the currentSecond to compute the waiting time for that task. Append the waiting time for that task to a list for later processing.
      3. Based on the number of pages in the print task, figure out how much time will be required.
   3. The printer now does one second of printing if necessary. It also subtracts one second from the time required for that task.
   4. If the task has been completed, in other words the time required has reached zero, the printer is no longer busy.
3. After the simulation is complete, compute the average waiting time from the list of waiting times generated.

3.14.2 JavaScript implementation

To design this simulation we will create classes for the three real-world objects described above: Printer, Task, and PrintQueue.

The Printer class will need to track whether it has a current task. If it does, then it is busy (lines 13–17) and the amount of time needed can be computed from the number of pages in the task. The constructor will also allow the pages-per-minute setting to be initialized. The tick method decrements the internal timer and sets the printer to idle (line 11) if the task is completed.

class Printer {
   constructor(ppm) { 
        this.pageRate = ppm;
        this.currentTask = null;
        this.timeRemaining = 0;
    }

    tick() {
        if (this.currentTask) {
            this.timeRemaining = this.timeRemaining - 1;
            if (this.timeRemaining <= 0) {
                this.currentTask = null;
            }
        }
    }

    busy() {
        if (this.currentTask) {
            return true;
        }
        else {
            return false;
        }
    }

    startNext(newTask) {
        this.currentTask = newTask;
        this.timeRemaining = newTask.getPages() * 60/this.pageRate;
    }
}

The Task class will represent a single printing task. When the task is created, a random number generator will provide a length from 1 to 20 pages. We have chosen to use the Math methods to generate the random numbers. Here is an exemple:

Math.floor(Math.random() * (42 - 1)) + 1;

The logic behind is a simple rule of three:

Math.random() returns a Number between 0 (inclusive) and 1 (exclusive). So we have an interval like this:

[0 .... 1]

Now, we'd like a number between min (inclusive) and max (exclusive):

[0 .................................... 1]
[min .................................. max]

We can use theMath.random to get the correspondent in the [min, max] interval. But, first we should factor a little bit the problem by subtracting min from the second interval:

[0 .................................... 1]
[min - min ............................ max - min]

This gives:

[0 .................................... 1
[0 ............................ max - min]

We may now apply Math.random and then calculate the correspondent. Let's choose a random number:

                Math.random()
                    |
[0 .................................... 1]
[0 .................................... max - min]
                    |
                    x (what we need)

So, in order to find x, we would do:

var x = Math.random() * (max - min);

By adding min back, so that we get a number in the [min, max] interval:

var x = Math.random() * (max - min) + min;

To get an integer we can use Math.floor to have a perfectly even distribution.

min.... min+1... min+2 ... max-1... max.... max+1 (is excluded from interval)
|        |        |         |        |        |
└───┬───┘└───┬───┘└─── ... ┘└───┬───┘└───┬───┘   ← floor()
   min     min+1               max-1    max

Now, about our task, each of them will also need to keep a timestamp to be used for computing waiting time. This timestamp will represent the time that the task was created and placed in the printer queue. The waitTime method can then be used to retrieve the amount of time spent in the queue before printing begins.

class Task {
    constructor(time) {
        this.timestamp = time;
        this.pages = Math.floor(Math.random() * (21 - 1)) + 1;
    }

    getStamp() {
        return this.timestamp;
    }

    getPages() {
        return this.pages;
    }

    waitTime(currentTime) {
        return currentTime - this.timestamp;
    }
}

The main simulation implements the algorithm described above. The printQueue object is an instance of our existing queue ADT. A boolean helper function, newPrintTask, decides whether a new printing task has been created. Print tasks arrive once every 180 seconds. By arbitrarily choosing 180 from the range of random integers (line 32), we can simulate this random event. The simulation function allows us to set the total time and the pages per minute for the printer.

import Queue from './queue.js';

function simulation(numSeconds, pagesPerMinute) {
    var printer = new Printer(pagesPerMinute);
    var printQueue = new Queue();
    var waitingTimes = [];

    for (var i = 0; i < numSeconds; i++) {
        var currentSecond = i;
        console.log('currentSecond:', currentSecond);

        if (newPrintTask()) {
            var task = new Task(currentSecond);
            printQueue.enqueue(task);
        }
        if (!printer.busy() && !printQueue.isEmpty()) {
            var nextTask = printQueue.dequeue();
            console.log('nextTask.waitTime(currentSecond):', nextTask.waitTime(currentSecond));
            waitingTimes.push(nextTask.waitTime(currentSecond));
            printer.startNext(nextTask);
        }
        printer.tick();
    }

    var sumWaitingTimes = 0;
    for (var i = 0; i < waitingTimes.length; i++) { 
        sumWaitingTimes += waitingTimes[i];
    }
    console.log('waitingTimes:', waitingTimes);
    var averageWait = sumWaitingTimes / waitingTimes.length;
    console.log(`Average Wait ${averageWait} secs. ${printQueue.size()} tasks remaining`);
}

function newPrintTask() {
    var num = Math.floor(Math.random() * (181 - 1)) + 1;
    if (num === 180) {
        return true;
    }
    else {
        return false;
    }
}

for(var i = 0; i < 10; i++) { 
    simulation(3600, 5);
}

When we run the simulation, we should not be concerned that the results are different each time. This is due to the probabilistic nature of the random numbers. We are interested in the trends that may be occurring as the parameters to the simulation are adjusted. Here are some results.

First, we will run the simulation for a period of 60 minutes (3,600 seconds) using a page rate of five pages per minute. In addition, we will run 10 independent trials. Remember that because the simulation works with random numbers each run will return different results.

for(var i = 0; i < 10; i++) {
    simulation(3600, 5);
}
// Average Wait 63 secs. 0 tasks remaining
// Average Wait 155.76923076923077 secs. 0 tasks remaining
// Average Wait 51.23076923076923 secs. 1 tasks remaining
// Average Wait 95.8 secs. 1 tasks remaining
// Average Wait 321.29411764705884 secs. 0 tasks remaining
// Average Wait 18.45 secs. 0 tasks remaining
// Average Wait 18.785714285714285 secs. 0 tasks remaining
// Average Wait 141.2 secs. 1 tasks remaining
// Average Wait 171.41176470588235 secs. 3 tasks remaining
// Average Wait 240.2173913043478 secs. 0 tasks remaining

After running our 10 trials we can see that the mean average wait time is 127.71 seconds. You can also see that there is a large variation in the average weight time with a minimum average of 18.45 seconds and a maximum of 321.29 seconds. You may also notice that in only 6 of the cases were all the tasks completed.

Now, we will adjust the page rate to 10 pages per minute, and run the 10 trials again, with a faster page rate our hope would be that more tasks would be completed in the one hour time frame.

for(var i = 0; i < 10; i++) {
    simulation(3600, 10);
}
// Average Wait 57.65384615384615 secs. 0 tasks remaining
// Average Wait 25 secs. 2 tasks remaining
// Average Wait 9.45 secs. 0 tasks remaining
// Average Wait 1 secs. 0 tasks remaining
// Average Wait 4.894736842105263 secs. 0 tasks remaining
// Average Wait 10.235294117647058 secs. 0 tasks remaining
// Average Wait 6.6521739130434785 secs. 0 tasks remaining
// Average Wait 3.3529411764705883 secs. 0 tasks remaining
// Average Wait 24.473684210526315 secs. 0 tasks remaining
// Average Wait 22.41176470588235 secs. 0 tasks remaining

3.14.3 Discussion

We were trying to answer a question about whether the current printer could handle the task load if it were set to print with a better quality but slower page rate. The approach we took was to write a simulation that modeled the printing tasks as random events of various lengths and arrival times.

The output above shows that with 5 pages per minute printing, the average waiting time varied from a low of 18.45 seconds to a high of 321.29 seconds (about 5 minutes). With a faster printing rate, the low value was 1 second with a high of only 57. In addition, in 4 out of 10 runs at 5 pages per minute there were print tasks still waiting in the queue at the end of the hour.

Therefore, we are perhaps persuaded that slowing the printer down to get better quality may not be a good idea. Employees cannot afford to wait that long for their papers, especially when they need to be getting on to their next meeting. A five-minute wait would simply be too long.

This type of simulation analysis allows us to answer many questions, commonly known as “what if” questions. All we need to do is vary the parameters used by the simulation and we can simulate any number of interesting behaviors. For example:

• What if the enrollment goes up and the average number of employees increase by 20?
• What if the direction decide that the Monday will be meeting-free? Can they afford to wait?
• What if the size of the average print task decreases?

These questions could all be answered by modifying the above simulation. However, it is important to remember that the simulation is only as good as the assumptions that are used to build it. Real data about the number of print tasks per hour and the number of students per hour was necessary to construct a robust simulation.