CIRCULAR QUEUE IMPLEMENTATION USING LINKED LIST

Article Index
CIRCULAR QUEUE IMPLEMENTATION USING LINKED LIST
SOURCE CODE
DOCUMENTATION
TEST CASE AND COMPATIBILITY
All Pages

IMPLEMENTATION OF A CIRCULAR QUEUE USING

LINKED LIST

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. 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.

A linked list is a data structure that consists of a sequence of nodes. Each node consists of two fields-information and address. The information part contains the value that the node holds. The address part contains the address of the next node. The last node contains NULL in the address part.

NODE 1 NODE 2 NODE 3

INFO ADDRESS 2000 2002

In a linked list, the nodes are logically connected but they may not be physically adjacent. This makes lists more advantageous than arrays where the data must be physically adjacent and at the same time logically connected. Here, nodes can be inserted and deleted at any point in the list unlike stacks, queues. But it is possible to implement a circular queue using a linked list.

CODE:

#include"stdio.h"

#include"stdlib.h"

typedef struct qnode

{

int a;

struct qnode *next;

}*node;

node prev,new,temp,end;

typedef node queue;

queue createqueue()

{

queue q;

q=(queue)malloc(sizeof(struct qnode));

if(q==NULL)

{

printf("\nOut of space");

return NULL;

}

q->next=q;

return q;

}

void displayq(queue q)

{

printf("\nThe contents of the queue are:");

if(isempty(q))

printf("\nNo items to delete");

else

{

printf("\n");

temp=q->next;

while(temp!=q)

{

printf("%d\t",temp->a);

temp=temp->next;

}

int isempty(queue q)

{

return(q->next==q);

}

queue insert(queue q,int x)

{

node new;

new=(node)malloc(sizeof(struct qnode));

new->a=x;

if(isempty(q))

{

new->next=q;

q->next=new;

end=new;

}

else

{

end->next=new;

new->next=q;

end=new;

}

return q;

}

void delete(queue q)

{

if(isempty(q))

printf("\nUnderflow");

else

q->next=(q->next)->next;

}

int front(queue q)

{

if(isempty(q))

{

printf("\nUnderflow");

return -1;

}

else

return ((q->next)->a);

}

int frontdel(queue q)

{

int x;

if(isempty(q))

{

printf("\nUnderflow");

return -1;

}

else

{

x=(q->next)->a;

temp=q->next;

free(temp);

q->next=(q->next)->next;

return x;

}

int main()

{

int n,x;

queue q;

q=createqueue();

printf("\nThe choices are\n1.Insert\n2.Delete\n3.Front\n4.Frontdelete\n5.Exit");

while(1)

{

printf("\nEnter your choice:");

scanf("%d",&n);

switch(n)

{

case 1:printf("\nEnter the element:");

scanf("%d",&x);

insert(q,x);

displayq(q);

break;

case 2:delete(q);

printf("\nElement deleted");

displayq(q);

break;

case 3:printf("\nFront value is %d",front(q));

displayq(q);

break;

case 4:printf("\nDeleted element is %d",frontdel(q));

displayq(q);

break;

case 5:exit(1);

default:printf("\nInvalid choice");

}

GOAL OF THE CODE:

To implement a circular queue using LINKED LIST.

VARIABLES USED:

1.a- structure variable which contains the value of the node.

2.node,next-pointers to the structure qnode.

3.new- pointer variable which points to the newly inserted node.

4.temp-variable which temporarily stores a value.

5.end-pointer variable which points to the last node.

6.x- local variable which contains the element to be inserted in the list.

7.n-variable in main() which stores the choice entered by the user.

FUNCTIONS USED:

FUNCTION	PURPOSE
createqueue()	Dynamically allocates memory for the queue.
displayq()	Displays the contents of the queue.
isempty()	Returns 1 if the queue is empty else returns 0.
insert()	Inserts elements into the queue.
delete()	Deletes elements from the queue.
front()	Returns the front most element of the queue.
frontdel()	Deletes the front most element and then returns the value pointed out by the front pointer.

IMPLEMENTAION:

Initially,the maximum no.of elements to be stored in the queue is obtained from the user.
A circular queue is created by dynamically allocating memory using createqueue() function.
Then, choices are provided to the user from which one can choose the operation to be performed.
A switch case is made use of in this code. Depending upon the choice entered by the user,the corresponding operations are performed.
After each operation,the display() function is called so that the user can better understand the implementation.
If the user enters a number that has not been specified in the cases, the default case is executed and the program terminates.

Initialization: Assign the address of the header node to the address part of the next node(also known as emptying the queue).

TEST CASE:

The choices are

1.Insert

2.Delete

3.Front

4.Frontdelete

5.Exit

Enter your choice:1

Enter the element:5