Queue ADT and its applications, Applications, Implementations

The Queue ADT

A queue is like a "natural" queue of elements. It is an ordered list in which all insertions occur at one end called the back or rear of the queue, whereas all deletions occur at the other end called the front orhead of the queue.

1. The queue ADT and its applications

In the popular terminology, insertion and deletion in a queue are respectively called the enqueue and the dequeue operations. The element dequeued from a queue is always the first to have been enqueued among the elements currently present in the queue. In view of this, a queue is often called a First-In-First-Out or a FIFO list.

The following functions specify the operations on the queue ADT. We are going to maintain a queue of characters. In practice, each element of a queue can be of any well-defined data type.

Q = init();

Initialize the queue Q to the empty queue.

isEmpty(Q);

Returns "true" if and only if the queue Q is empty.

isFull(Q);

Returns "true" if and only if the queue Q is full, provided that we impose a limit on the maximum size of the queue.

front(Q);

Returns the element at the front of the queue Q or error if the queue is empty.

Q = enqueue(Q,ch);

Inserts the element ch at the back of the queue Q. Insertion request in a full queue should lead to failure together with some appropriate error messages.

Q = dequeue(Q);

Delete one element from the front of the queue Q. A dequeue attempt from an empty queue should lead to failure and appropriate error messages.

print(Q);

Print the elements of the queue Q from front to back

2. Applications of queues

• For implementing any "natural" FIFO service, like telephone enquiries, reservation requests,

traffic flow, etc.

• For implementing any "computational" FIFO service, for instance, to access some resources.

Examples: printer queues, disk queues, etc.

• F or searching in special data structures (breadth-first search in graphs and trees).

• For handling scheduling of processes in a multitasking operating system.

3. Implementations of the queue ADT

Continuing with our standard practice followed so far, we are going to provide two implementations of the queue ADT, the first using static memory, the second using dynamic memory. The implementations aim at optimizing both the insertion and deletion operations.

3.1. Using static arrays

Recall that in our implementation of the "ordered list" ADT we always let the list start from the array index 0. This calls for relocation of elements of the list in the supporting array after certain operations (usually deletion). Now we plan to exploit the specific insertion and deletion patterns in queues to avoid these costly relocations. We maintain two indices to represent the front and the back of the queue. During an enqueue operation, the back index is incremented and the new element is written in this location. For a dequeue operation, on the other hand, the front is simply advanced by one position. It then follows that the entire queue now moves down the array and the back index may hit the right end of the array, even when the size of the queue is smaller than the capacity of the array. In order to avoid waste of space, we allow our queue to wrap at the end. This means that after the back pointer reaches the end of the array and needs to proceed further down the line, it comes back to the zeroth index, provided that there is space at the beginning of the array to accommodate new elements. Thus, the array is now treated as a circular one with index MAXLEN treated as 0,MAXLEN + 1 as 1, and so on. That is, index calculation is done modulo MAXLEN. We still don't have to maintain the total queue size. As soon as the back index attempts to collide with the front index modulo MAXLEN, the array is considered to befull.

There is just one more problem to solve. A little thought reveals that under this wrap-around technology, there is no difference between a full queue and an empty queue with respect to arithmetic modulo MAXLEN. This problem can be tackled if we allow the queue to grow to a maximum size of MAXLEN - 1. This means we are going to lose one available space, but that loss is inconsequential. Now the condition for full array is that the front index is two locations ahead of the back modulo MAXLEN, whereas the empty array is characterized by that the front index is just one position ahead of the back again modulo MAXLEN. An implementation of the queue ADT under these design principles is now given.

#define MAXLEN 100

typedefstruct {

char element[MAXLEN];

int front;

int back; }

queue;

queueinit ()

{

queue Q; Q.front = 0;

Q.back = MAXLEN - 1;

return Q;

}

intisEmpty ( queue Q )

{

return (Q.front == (Q.back + 1) % MAXLEN);

}

intisFull ( queue Q )

{

return (Q.front == (Q.back + 2) % MAXLEN);

}

char front ( queue Q )

{

if (isEmpty(Q)) {

fprintf(stderr,"front: Queue is empty\n"); return '\0';

}

returnQ.element[Q.front];

}

queueenqueue ( queue Q , char ch )

{

if (isFull(Q)) {

fprintf(stderr,"enqueue: Queue is full\n"); return Q;

}

++Q.back;

if (Q.back == MAXLEN) Q.back = 0; Q.element[Q.back] = ch;

return Q;

}

queuedequeue ( queue Q )

{

if (isEmpty(Q)) {

fprintf(stderr,"dequeue: Queue is empty\n"); return Q;

}

++Q.front;

if (Q.front == MAXLEN) Q.front = 0; return Q;

}

void print ( queue Q )

{

inti;

if (isEmpty(Q)) return; i = Q.front;

while (1) {

printf("%c", Q.element[i]); if (i == Q.back) break;

if (++i == MAXLEN) i = 0;

}

}

Here is a sample main() for these functions.

int main ()

{

queue Q;

Q = init(); printf("Current queue : "); print(Q); printf("\n");

Q = enqueue(Q,'h'); printf("Current queue : "); print(Q); printf("\n");

Q = enqueue(Q,'w'); printf("Current queue : "); print(Q); printf("\n");

Q = enqueue(Q,'r'); printf("Current queue : "); print(Q); printf("\n");

Q = dequeue(Q); printf("Current queue : "); print(Q); printf("\n");

Q = dequeue(Q); printf("Current queue : "); print(Q); printf("\n");

Q = enqueue(Q,'c'); printf("Current queue : "); print(Q); printf("\n");

Q = dequeue(Q); printf("Current queue : "); print(Q); printf("\n");

Q = dequeue(Q); printf("Current queue : "); print(Q); printf("\n");

Q = dequeue(Q); printf("Current queue : "); print(Q); printf("\n");

}

Finally, this is the output of the complete program.

Current queue :

Current queue : h

Current queue :hw

Current queue :hwr

Current queue :wr

Current queue : r

Current queue :rc

Current queue : c

Current queue : dequeue:

Queue is empty

Current queue :