Queues

We can use an array to hold the items in the queue. While doing so we must keep track of both the front and the rear of the queue. One method to do this would be to keep the front of the queue always in the first location of the array. Then an item could be added to the queue simply by increasing the counter signifying the rear. This addition would be same as the way we add an item to a stack. To delete an item from the queue, however, would be very expensive indeed, since after the first item is removed, all the remaining items would have to be moved one position up the queue to fill in the vacancy. With a long queue, this process would be prohibitively slow. Although this method of storage closely models a queue of people waiting to be served, it is a poor choice for use in computers. For efficient processing of queues, we shall therefore need two indices so that we can keep track of both the front and the rear of the queue without moving any items. To add an item to the queue, we simply increase the rear by one and put the item into that position. To remove an item, we take it from the position at the front and then increase value of front by one. Here is the program that implements these ideas...

#include "stdio.h"

# define MAX 10

int arr[MAX] ;

int front, rear ;

main( )

{

int data ;

rear = front = -1 ;

addq ( 11 ) ;

addq ( 12 ) ;

addq ( 13 ) ;

addq ( 14 ) ;

addq ( 15 ) ;

addq ( 16 ) ;

addq ( 17 ) ;

addq ( 18 ) ;

addq ( 19 ) ;

addq ( 20 ) ;

addq ( 21 ) ;

data = delq( ) ;

printf ( "\nItem deleted = %d ", data ) ;

data = delq( ) ;

printf ( "\nItem deleted = %d ", data ) ;

data = delq( ) ;

printf ( "\nItem deleted = %d ", data ) ;

}

addq ( int item )

{

if ( rear == MAX - 1 )

{

printf ( "\nQueue is full" ) ;

return ;

}

rear++ ;

arr[rear] = item ;

if ( front == -1 )

front = 0 ;

}

delq( )

{

int data ;

if ( front == -1 )

{

printf ( "\nQueue is Empty" ) ;

return NULL ;

}

data = arr[front] ;

if ( front == rear )

front = rear = -1 ;

else

front++ ;

return data ;

}

Since addition of new element to the queue takes place at the rear end and deletion of an element from the queue takes place from the front, in the program we have two variables front and rear to monitor the two ends. When the queue is empty their values are set to -1. To carry out the addition and deletion operations on the queue we have implemented two functions within the queue class, namely, addq( ) and delq( ). Let us understand these functions. Here is the first one.

addq ( int item )

{

if ( rear == MAX - 1 )

{

printf ( "\nQueue is full" ) ;

return ;

}

rear++ ;

arr[rear] = item ;

if ( front == -1 )

front = 0 ;

}

While adding a new element to the queue, first it is ascertained whether such an addition is possible or not. Since the array indexing begins with 0 the maximum number of elements that can be stored in the queue are MAX - 1. If these many elements are already present in the queue then it is reported to be full. If the element can be added to the queue then the value of the variable rear is incremented and the new item is stored in the array. If the item is being added to the queue for the first time ( i.e. if the variable front has a value -1 ) then as soon as the item is added to the queue front is set to 0 indicating that the queue is no longer empty. Let us now look at the delq( ) function.

delq( )

{

int data ;

if ( front == -1 )

{

printf ( "\nQueue is Empty" ) ;

return NULL ;

}

data = arr[front] ;

if ( front == rear )

front = rear = -1 ;

else

front++ ;

return data ;

}

Before deleting an element from the queue it is first ascertained whether there are any elements available for deletion. If not then the queue is reported as empty. Otherwise, an element is deleted from arr[front]. Imagine a case where we add 5 elements to the queue. Value of rear would now be 4. Suppose we have not deleted any elements from the queue, then at this stage the value of front would be 0. Now suppose we go on deleting elements from the queue. When the fifth element is deleted the queue would fall empty. To make sure that another attempt to delete should me met with an 'empty queue' message, in such a case front and rear both are reset to -1 to indicate emptiness of the queue.