Queues-1

Circular Queue Implementation

Can you imagine the limitation of our implementation of the queue?

Suppose we go on adding elements to the queue till the entire array gets filled. At this stage the value of rear would be MAX - 1. Now if we delete 5 elements from the queue, at the end of these deletions the value of front would be 5. If we now attempt to add a new element to the queue then it would be reported as full even though in reality the first five slots of the queue are empty. To overcome this situation we can implement a queue as a circular queue. That is, during addition if we reach the end of the array and if slots at the beginning of the queue are empty (as a result of a few deletions) then new elements would get added at the beginning of the array. The following program implements a circular queue. I would leave it for you to figure out its working.

#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 && front == 0 ) || ( rear + 1 == front ) )

{

printf ( "\nQueue is full" ) ;

return ;

}

if ( rear == MAX - 1 )

rear = 0 ;

else

rear++ ;

arr[rear] = item ;

if ( front == -1 )

front = 0 ;

}

delq( )

{

int data ;

if ( front == -1 )

{

printf ( "\nQueue is Empty" ) ;

return NULL ;

}

else

{

data = arr[front] ;

if ( front == rear )

front = rear = -1 ;

else

{

if ( front == MAX - 1 )

front = 0 ;

else

front++ ;

}

}

return data ;

}

The arrays that we used to implement the queues were declared to have the size MAX. This size remains fixed once the program is written, and it cannot be changed while the program is running. Thus while writing a program, we had to decide on the maximum amount of memory that would be needed for our arrays and we set this much memory aside in the declarations. If the number of elements stored in the queue is small, then much of this space would never be used. However, if we decide to store a large number of items in the queue, then we may exhaust the space set aside and encounter overflow, even when the computer memory is not fully used, simply because our original bounds on the array were too small.

Thus arrays suffer from the necessity to declare the size of the array before running the program. If we are to overcome this limitation we need to use a data structure called Linked List. The following program shows how to implement the queue using a linked list.

/* Program to implement a queue as a linked list */

#include "alloc.h"

struct node

{

int data ;

struct node *link ;

} ;

void addq ( struct node **, struct node **, int ) ;

int delq (struct node **, struct node ** ) ;

main ( )

{

struct node *front, *rear ;

int item ;

front = rear = NULL ; /*empty queue */

addq ( &front, &rear, 11 ) ;

addq ( &front, &rear, 12 ) ;

addq ( &front, &rear, 13 ) ;

addq ( &front, &rear, 14 ) ;

addq ( &front, &rear, 15 ) ;

addq ( &front, &rear, 16 ) ;

addq ( &front, &rear, 17 ) ;

clrscr( ) ;

q_display ( front ) ;

printf ( "\nNo. of items in queue = %d", count ( front ) ) ;

printf ( "\n\nItems extracted from queue : " ) ;

item = delq ( &front, &rear ) ;

printf ( "%d", item ) ;

item = delq ( &front, &rear ) ;

printf( "%d", item ) ;

item = delq ( &front, &rear ) ;

printf( "%d", item ) ;

printf ( "\n" ) ;

q_display ( front ) ;

printf ( "\nNo. of items in queue = %d", count ( front ) ) ;

}

/* adds a new element at the end of queue */

void addq ( struct node **f, struct node **r, int item )

{

struct node *q ;

/* create new node */

q = malloc ( sizeof ( struct node ) ) ;

q -> data = item ;

q -> link = NULL ;

/* if the queue is empty */

if ( *f == NULL )

*f = q ;

else

(*r) -> link = q ;

*r = q ;

}

/* removes an element from front of queue */

int delq ( struct node **f, struct node **r )

{

struct node *q ;

int item ;

/* if queue is empty */

if ( *f == NULL )

printf ( "queue is empty " ) ;

else

{

/* delete the node */

q = *f ;

item = q -> data ;

*f = q -> link ;

free ( q ) ;

/* if on deletion the queue has become empty */

if ( *f == NULL )

*r = NULL ;

return ( item ) ;

}

}

/* displays all elements of the queue */

q_display ( struct node *q )

{

printf ( "\nfront -> " ) ;

/* traverse the entire linked list */

while ( q != NULL )

{

if ( q -> link == NULL )

printf ( "<- rear" ) ;

printf ( "%2d", q -> data ) ;

q = q -> link ;

}

printf ( "\n" ) ;

}

/* counts the number of nodes present in the linked list representing a queue */

count ( struct node *q )

{

int c = 0 ;

/* traverse the entire linked list */

while ( q != NULL )

{

q = q -> link ;

c++ ;

}

return c ;

}