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.
| | 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 ;
}
No comments:
Post a Comment