CEG's Linux User Group

  • Increase font size
  • Default font size
  • Decrease font size
Home Labs CIRCULAR QUEUE IMPLEMENTATION USING ADT

CIRCULAR QUEUE IMPLEMENTATION USING ADT

Friday, 12 June 2009 21:05 S.AARADHANA
E-mail Print
User Rating: / 2
PoorBest 
Article Index
CIRCULAR QUEUE IMPLEMENTATION USING ADT
SOURCE CODE
DOCUMENTATION
TEST CASES AND COMPATIBILITY
All Pages

 

IMPLEMENTATION OF A CIRCULAR QUEUE USING ADT

 

The aim of this article is to implement a circular queue using abstract data type.

INTRODUCTION:

We know that a linear queue is a “first in first out “ data structure,i.e., insertion can be made only at the end and deletion can be made only at the front. In a linear queue, the traversal through the queue is possible only once,i.e.,once an element is deleted,we cannot insert another element in its position. This disadvantage of a linear queue is overcome by a circular queue, thus saving memory.

 

 

Linear queue:

img1

No more elements can be inserted in a linear queue now.

 

Circular queue:

img2

 

In a circular queue, after rear reaches the end of the queue, it can be reset to zero. This helps in refilling the empty spaces in between.

This article contains the code for implementing a circular queue using ADT. Here, we demonstrate all the functions that can be performed in a circular queue.



 

 

CODE:

#include"stdio.h"
#include"stdlib.h"
typedef struct qrec
{
int *a;
int front,rear,cap,size;
}*queue;

queue makeempty(queue q)
{
q->rear=-1;
q->front=-1;
return q;
}

queue createqueue(int max)
{
queue q;
q=(queue)malloc(sizeof(struct qrec));
q->a=(int*)malloc(sizeof(int)*max);
makeempty(q);
q->cap=max;
return q;
}

int isfull(queue q)
{
return q->rear==q->cap-1 && q->front==0 || q->front==q->rear+1;
}

int isempty(queue q)
{
return q->front==-1;
}

void enqueue(queue q,int x)
{
if(isfull(q))
printf("\n Overflow");
else
{
q->rear=(q->rear+1)%(q->cap);
q->a[q->rear]=x;
if(q->front==-1)
q->front=0;
}
}

int dequeue(queue q)
{
if(isempty(q))
printf("\n Underflow");
else
{
if(q->rear==q->front)
makeempty(q);
else
{
q->front=(q->front+1)%(q->cap);
return q->a[q->front];
}
}
}

int front(queue q)
{
if(isempty(q))
printf("\n Underflow");
else
return q->a[q->front];
}

int frontanddelete(queue q)
{
int p;
if(isempty(q))
{
printf("underflow");
return 0;
}
else
{
p=front(q);
dequeue(q);
return p;
}
}
void display(queue q)
{
int i;
printf("\n CONTENTS");
for(i=q->front;i!=q->rear;i=(i+1)%q->cap)
printf("\t%d",q->a[i]);
printf("\t%d",q->a[i]);
}
int main()
{
int m,b,c;
queue q;

printf("\nEnter the max size");
scanf("%d",&m);
q=createqueue(m);
printf("\n MENU\n1.Enqueue\n2.Dequeue\n3.Front\n4.Front and delete\n5.Exit");
while(1)
{
printf("\n ENTER UR CHOICE");
scanf("%d",&b);
switch(b)
{
case 1:
printf("\n Enter a no");
scanf("%d",&c);
enqueue(q,c);
display(q);
break;
case 2:dequeue(q);
printf("\n Deq");
display(q);
break;
case 3:printf("\n Front value is %d",front(q));
display(q);
break;
case 4:frontanddelete(q);
display(q);
break;
case 5:exit(0);
break;
default:printf("\n Invalid option");
break;
}
}

}



 

 

GOAL OF THE CODE:

To implement a circular queue using ADT.

 

VARIABLES USED:

1.a-pointer variable which stores the contents of the queue.

2.rear-pointer variable which points to the location where insertion is done.

3.front-pointer variable which points to the location where deletion is done.

4.cap-variable which indicates the maximum no.of elements that the queue can hold.

5.size-variable which indicates the no.of elements present in the queue at a particular instant.

6.queue-pointer to the structure qrec.

7.max-variable which indicates the maximun no.of elements (to be entered by the user).

8.x-local variable which stores the element to be inserted(in enqueue()).

9.p- local variable which contains the front most element(returned by frontanddelete()).

10.i-counter variable used to display the contents of the queue(in display()).

 

IN MAIN() FUNCTION:

11.m-variable which indicates the maximun no.of elements (to be entered by the user).

12.b-variable which stores the choice(to be entered by the user).

13.c-variable used in almost all the case statements to store the respective values.

FUNCTIONS USED:

FUNCTIONS

PURPOSE

createqueue()

Dynamically allocates memory for the queue.

makempty()

Initializes rear and front to -1.

isfull()

Returns 1 if the queue is full else returns 0.

isempty()

Returns 1 if the queue is empty else returns 0.

enqueue()

Inserts elements into the queue.

dequeue()

Deletes elements from the queue.

front()

Returns the front most element of the queue.

frontanddelete()

Deletes the front most element and then returns the value pointed out by the front pointer.

display()

Displays the contents of the queue.

 

IMPLEMENTATION:

1.Initially,the maximum no.of elements to be stored in the queue is obtained from the user.

2.A circular queue is created by dynamically allocating memory using createqueue() function.

3.Then, choices are provided to the user from which one can choose the operation to be performed.

4.A switch case is made use of in this code. Depending upon the choice entered by the user,the corresponding operations are performed.

5.After each operation,the display() function is called so that the user can better understand the implementation.

6.If the user enters a number that has not been specified in the cases, the default case is executed and the program terminates.

Initialization Conditions:

1.front and rear are initialised to -1.

2.size is initialised to 0.

3.capacity is assigned with the max. no.of elements.

 


 

TEST CASES:

Enter the max size 5

MENU

1.Enqueue

2.Dequeue

3.Front

4.Front and delete

5.Exit

ENTER UR CHOICE 1

Enter a no 3

CONTENTS 3


ENTER UR CHOICE 1

Enter a no 4

CONTENTS 3 4

ENTER UR CHOICE 1

Enter a no 5

CONTENTS 3 4 5

 

ENTER UR CHOICE 1

Enter a no 6

CONTENTS 3 4 5 6

ENTER UR CHOICE 2

Deq

CONTENTS 4 5 6

 

ENTER UR CHOICE 1

Enter a no 7

CONTENTS 4 5 6 7

ENTER UR CHOICE 3

Front value is 4

CONTENTS 4 5 6 7

 

ENTER UR CHOICE 2

Deq

CONTENTS 5 6 7

 

ENTER UR CHOICE 3

Front value is 5

CONTENTS 5 6 7

 

ENTER UR CHOICE 4

CONTENTS 6 7

 

ENTER UR CHOICE 5

COMPATIBILITY:

Compatible with all computers which are capable of running gcc-4.3.3-5. The program has been tested with the above version of gcc as of june 12.

 

 

< Prev   Next >
Last Updated on Saturday, 13 June 2009 08:25  
Please register or login to add your comments to this article.