|
|
In this lab session we will study a data structure called a queue. This structure has many applications in computing, such as holding files awaiting printer access.
A. Definition of Queue
B. Array Implementation of a Queue
C. "Circular Array" Implementation of a Queue
D. Linked List Implementation of a Queue
A. Definition of Queue
A queue is an abstract data type in which insertion occurs at
the back of the list (aka the rear or tail)
and deletion/removal occurs at the front end (aka the head).
A queue in C++ is defined to hold one type of data element.
Only the elements indicated by front and rear can be accessed.
Thus a queue is a restricted access data structure similar to the stack.
Like a stack, the elements are related to each other by the order in
which they are placed on the queue.
An example of a queue is a line of people waiting at a ticket counter to buy a ticket. Whoever gets in line first gets a ticket first. A queue is a First In, First Out (FIFO) data storage mechanism. The storage structure that holds jobs for printing on a printer is typically a queue. When an operating system (OS) runs in batch mode (i.e. non-interactive), jobs to be processed are usually placed in a queue awaiting execution. However, sometimes the OS gives priority to smaller jobs in the queue, and if so, it becomes a "priority queue."
Insertion and deletion operations have special names in queues - insertion is called enqueue and deletion is called dequeue. A queue often serves as a "waiting line." Items put onto the queue (enqueued) come off (dequeued) in the same order. A queue, like a cafeteria line, has a front and a rear. Items are inserted at the rear of the queue and removed from the front of the queue.
B. Array Implementation of a Queue
First we demonstrate how the data in a Queue class can be implemented with an array, say elements[0..n-1], a counter nbrElts, and a pair of array indices, frontIndx and rearIndx. The array could hold any type of data, even a record or a class type. In an array implementation of a queue nbrElts = 0 will mean the queue is empty. The data members nbrElts and frontIndx would be initialized to 0 by a class constructor; the data member rearIndx would be initialized to -1. To enqueue an element we increment the rearIndx (unless the array is full) and store the new element at position rearIndx in the array. Thus code in the enqueue method might appear as:
//enqueue:To dequeue an element we must first determine if the queue is empty. If the queue is not empty, we save the item at frontIndx and then increment frontIndx. Finally, we return the saved item to the calling function. The code in the dequeue method might appear as follows:
if ( !full() ) // full checks for nbrElts >= n
{
rearIndx++;
elements[rearIndx] = newElement;
nbrElts++;
}
//dequeue:
if ( !empty() ) // empty checks for nbrElts = 0
{
frontElt = elements[frontIndx];
frontIndx++;
nbrElts--;
return frontElt;
}
As you can see, each enqueue operation advances rearIndx and nothing ever decreases it. Matters get worse as the queue gets used. For instance, suppose n elements are enqueued and then all of them are dequeued. We will have frontIndx = n , rearIndx = n-1 and nbrElts = 0. Since nbrElts = 0 says the queue is empty, we could try to store something at elements[rearIndx+1] (that is, elements[n]) but this slot does not exist in an array indexed from 0 to MAX_QUEUE_SIZE-1. To avoid this problem, we could copy each element in the queue to the next lower position each time a dequeue occurs, but this has a high cost of data movement and is not practical. A different and better solution is needed.
C. "Circular Array" implementation of a Queue
In this situation, the front and rear queue indices advance by moving them
"clockwise" around the array.
To achieve this, addition modulo n is used in the
enqueue and dequeue operations described above.
Hence incrementing rearIndx is done using the assignment statement
rearIndx = (rearIndx + 1) % (MAX_QUEUE_SIZE);
This will cause readIndx to "wrap around to zero" when
if "rearIndx == MAX_QUEUE_SIZE-1"
(i.e., is equal to the last position in the array).
A similar scheme is used for frontIndx when dequeueing.
The new enqueue and dequeue algorithms are as follows:
// (Circular array) enqueue:
if ( !full() ) // full checks for nbrElts >= MAX_QUEUE_SIZE
{
rearIndx = (rearIndx + 1) % MAX_QUEUE_SIZE;
elements[rearIndx] = newElement;
nbrElts++; // update the number of elements
}
// (Circular array) dequeue:
if ( !empty() ) // empty checks for nbrElts == 0
{
frontElt = elements[frontIndx];
frontIndx = (frontIndx + 1) % MAX_QUEUE_SIZE;
nbrElts--; // update the number of elements
return frontElt;
}
D. Linked List Implementation of a Queue
Using a circular array implementation is physically limiting. As was the case in a stack, it is sometimes difficult to determine the maximum number of elements that a queue may need to contain. Thus we now consider the linked list implementation of a queue. Assume that frontPtr and rearPtr are pointers to the front and rear nodes in a linked representation of a queue. The queue can now be visualized as in the following picture:
Enqueueing means inserting a new node at the "end" of the list (where rearPtr points) and making rearPtr point at this new node, while dequeueing means deleting the node pointed to by frontPtr and resetting frontPtr. Both operations are straightforward. Here is the algorithm for the enqueue:
//(linked list) enqueue:
Make p point at a new node
Copy new data into node p
Set p's pointer field to NULL
Set the link in the rear node to point to p
Set rearPtr = p
The definition for a queue implemented as a linked list is contained in the file inlab21.h and the implementation is contained in inlab21.cpp. It uses a pointer to the first node (front) and the last node (rear) of the queue for dequeueing and enqueueing.
Exercise 6: Copy inlab21.h and inlab21.cpp to your account. The code for the dequeue is missing from the implementation section of the queue. Complete the dequeue function.
Exercise 7: The code in main21.cpp generates 100 random real numbers and enqueues some of them while using the others to request a dequeue. Add code to the program so you can determine the maximum size (length) the queue becomes in the process of generating the 100 random numbers. Display the maximum length. Create a script log, lab21ex7.log, with a print out (pr -n -t -e4 ...) of your revised inlab21.cpp and main21.cpp files, a compile, and a run demonstrating that the code written for Exercises 6 and 7 is working.
Submit the required log files by using the command
$ handin lab21log lab21ex7.log