|
|
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 queue is an abstract data type in which insertion occurs at one end (the rear) and deletion occurs at the other end (the front). A queue 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 a queue. When an operating system (OS) runs in batch mode (i.e. non-interactive), jobs to be processed are placed in a queue awaiting execution. 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.
We define a queue using a Queue class. As in the case of a stack, there are several ways to implement the Queue class. We will illustrate two implementations and discuss the merits of each.
First we demonstrate how the data in a Queue class can be implemented with an array, say elements[0..n-1]. Of course the array could hold any type of data, even a record or a class type. In an array implementation of a queue front > rear will mean the queue is "empty." The data members front and rear would be initialized to 0 and -1 respectively by a class constructor. To enqueue an element we increment rear and store the new element at position rear in the array unless increasing rear would exceed the upper bound of the array. Thus code in the enqueue method might appear as:
//enqueue: if (! full()) //full checks for rear == n - 1 { rear ++; elements[rear] = newElement; }
Note: The queue will be full if rear = n - 1.
To dequeue an element we must first determine if the queue is empty. If the queue is not empty, we save the item at front and then increment front. Lastly, we return the saved item to the calling function. The code in the dequeue might appear as follows:
//dequeue: if (!empty()) //empty checks for front > rear { deleted = elements[front]; front++; return Deleted; }
Note: The queue is empty when front > rear.
q.enqueue(39);
q.enqueue(22);
item1 = q.dequeue();
q.enqueue(59);
item2 = q.dequeue();
item3 = q.dequeue();
As you can see, each enqueue advances the rear pointer and nothing ever decreases it. Matters can only get worse as the queue is used. For instance, suppose n elements are enqueued and then all are dequeued. We will have front = n and rear = n-1. Since front > rear the queue is empty but since rear > = n-1 the queue is also full. To avoid this paradox (an empty but full queue), we could copy all elements in the queue to the lower positions each time a dequeue occurs (or every so often). This has a high cost of data movement and is not practical. We need another solution.
We can think of the array of elements as a circular list by "gluing" the end of the array elements[0..n-1] to its front as in the following picture.
In this situation, the queue indexes front and rear advance by moving them clockwise around the array. To achieve this, addition modulo n is used in the enqueue and dequeue operations described above. Thus, when rear = n - 1, the end of the arrray, if there is room, rear is incremented by 1 as follows:
rear = (rear + 1) % n = (n - 1 + 1 ) % n = n % n = 0
A similar formula is used for front when dequeueing.
The only difficulty with this scheme involves detecting the queue-empty and queue-full conditions. It seems reasonable to select as the queue-empty condition front is one slot ahead of rear since front "passes" rear when the queue becomes empty. However, imagine you have enqueued n elements and no dequeues have occurred. All the array slots (0..n-1) are full so certainly the queue is full. On the other hand, front has not moved from its initial value of 0, so front is one slot ahead of rear, and the queue is empty. Obviously we need a way to distinguish the two situations so we agree to give up one slot and make front the index of the location before the front of the queue. The rear index still points to the last element enqueued and (front + 1) modulo n is the next element to dequeue, if the queue is not empty. Consider a queue with elements elements[0..3]. This queue has four elements. Suppose front = 2, then this means that elements[3] contains the item at the front of the queue.
Initially the constructor would set front = 0 and rear
= 0. Using the circular array implementation, the queue is empty
if front = rear. The queue is full if (rear + 1)
% n is equal to front. For example,
We cannot insert another element since (rear + 1) % 4 = 0 (=front). That is, the queue is full. But after a dequeue we could insert another element.
The new enqueue and dequeue algorithms are as follows:
//(Circular array) enqueue: if (! full()) // if rear+1 % n == front { rear = (rear + 1) % n; elements[rear] = newElement; } //(Circular array) dequeue: if (!empty()) // if front == rear { front = (front + 1) % n; return elements[front]; }
item = q.dequeue;
q.enqueue(96);
item = q.dequeue;
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 which a queue may need to contain. Thus we now consider
the linked list implementation of a queue. Assume that front
and rear 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 rear points) while dequeueing means deleting the node pointed to by front and resetting front. 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 rear = p
The definition for a queue implemented as a linked list is contained in the file inlab12.h and the implementation is contained in inlab12.cc. It uses a pointer to the first node (front) and the last node (rear) of the queue for dequeueing and enqueueing.