Design, Develop and Implement a menu driven Program in C for the following operations on Circular QUEUE
Circular Queue is also a linear data structure, which follows the principle of FIFO(First In First Out) and the last position is connected back to the first position to make a circle. It is also called ‘Ring Buffer’., but instead of ending the queue at the last position, it again starts from the first position after the last, hence making the queue behave like a circular data structure.
Deletions and insertions can only be performed at front and rear end respectively, as far as linear queue is concerned.
Some Important points to Remember :
- In case of a circular queue, head pointer will always point to the front of the queue, and tail pointer will always point to the end of the queue.
- Initially, the head and the tail pointers will be pointing to the same location, this would mean that the queue is empty.
- New data is always added to the location pointed by the tail pointer, and once the data is added, tail pointer is incremented to point to the next available location.
- In a circular queue, data is not actually removed from the queue. Only the head pointer is incremented by one position when dequeue is executed. As the queue data is only the data between head and tail, hence the data left outside is not a part of the queue anymore, hence removed.
- The head and the tail pointer will get re-initialised to 0 every time they reach the end of the queue.
- Also, the head and the tail pointers can cross each other. In other words, head pointer can be greater than the tail. Sounds odd? This will happen when we dequeue the queue a couple of times and the tail pointer gets re-initialised upon reaching the end of the queue.
Program
In the Code below there are four parts. First three function to implement three different operations like Insert a node, delete a node and display the list. The Fourth part is the main function, in that a do while loop is implemented to keep the user engaged and provide him the all the given choices, according to the choice one of the three function get called.
The First function checks whether the queue is empty, rear is at last position of queue or Queue is full. If the queue is not full it adds up the item.
The Second function checks whether the list is empty, full or it has only one item. If any node exists, it will delete the node in FIFO order.
The Third function will simply print all the elements of the Queue if exist. If not, then it will say Queue is Empty.
The Queue can hold only 5 items, for changing the capacity edit the second line.
|
#include<stdlib.h>
#include<conio.h>
# include<stdio.h>
# define MAX 5
int cqueue_arr[MAX];
int front = -1;
int rear = -1;
void insert(int item)
{
if((front == 0 && rear == MAX-1) || (front == rear+1))
{
printf("Queue Overflow \n");
return;
}
if (front == -1) /*If queue is empty */
{
front = 0;
rear = 0;
}
else
{
if(rear == MAX-1) /*rear is at last position of queue */
rear = 0;
else
rear = rear+1;
}
cqueue_arr[rear] = item ;
}
void del()
{
if (front == -1)
{
printf("Queue Underflow\n");
return ;
}
printf("Element deleted from queue is : %d\n",cqueue_arr[front]);
if(front == rear) /* queue has only one element */
{
front = -1;
rear=-1;
}
else
{
if(front == MAX-1)
front = 0;
else
front = front+1;
}
}
void display()
{
int front_pos = front,rear_pos = rear;
if(front == -1)
{
printf("Queue is empty\n");
return;
}
printf("Queue elements :\n");
if( front_pos <= rear_pos )
while(front_pos <= rear_pos)
{
printf("%d ",cqueue_arr[front_pos]);
front_pos++;
}
else
{
while(front_pos <= MAX-1)
{
printf("%d ",cqueue_arr[front_pos]);
front_pos++;
}
front_pos = 0;
while(front_pos <= rear_pos)
{
printf("%d ",cqueue_arr[front_pos]);
front_pos++;
}
}
printf("\n");
}
int main()
{
int choice,item;
do
{
printf("1.Insert\n");
printf("2.Delete\n");
printf("3.Display\n");
printf("4.Quit\n");
printf("Enter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1 :
printf("Input the element for insertion in queue : ");
scanf("%d", &item);
insert(item);
break;
case 2 :
del();
break;
case 3:
display();
break;
case 4:
break;
default:
printf("Wrong choice\n");
}
}while(choice!=4);
return 0;
}
|
Output
For more Visvesvaraya Technological University(VTU) CSE-III Sem Data Structure Lab Experiments Click Here
| 
| 
