- What is a Data Structure & Types of Data Structures
- What is an Algorithm & It's Characteristics
- Asymptotic Notations
- What is Space Complexity
- Array in Data Structure
- Algorithm for Insertion in Array
- Sparse Matrix
- Introduction to a Linked List
- Algorithm to Insert a Node at the End of the Linked list
- Algorithm to Insert a Node at the Front of the Linked List
- Algorithm to Delete a Node from Linked list
- Circular Linked List
- Algorithm to Insert a Node in the Circular Linked list
- Algorithm to Delete a Node from the Circular Linked list
- Doubly Linked List
- Algorithm to Insert a Node at the End of the Doubly Linked list
- Algorithm to Delete a Node from the Doubly Linked List
- Stack Data Structure
- Algorithm to convert Infix to Postfix
- Queue Data Structure
- Circular Queue in Data Structure
Circular Queue in Data Structure
A circular queue is the extended version of a simple queue where the
last element is connected to the first element. The operations are performed based on
FIFO (First In First Out) principle. It is also called ‘Ring Buffer’.
The major drawback of using a linear Queue is that insertion is done
only from the rear end. If the first three elements are deleted from the Queue,
we cannot insert more elements even though the space is available in a Linear
Queue. In this case, the linear Queue shows the overflow condition as the rear
is pointing to the last element of the Queue.
Now
using a circular queue we can easily insert new elements using
Rear=(Rear+1)%MAX
Algorithm to insert an element in a
circular queue
Step 1: IF
((REAR+1)%MAX == FRONT)
Write " OVERFLOW "
Goto step 4
[End OF IF]
Step 2: IF FRONT =
-1 and REAR = -1
SET FRONT = REAR = 0
ELSE IF REAR = MAX - 1 and FRONT ! = 0
SET REAR = 0
ELSE
SET REAR = (REAR + 1) % MAX
[END OF IF]
Step 3: SET
QUEUE[REAR] = VAL
Step 4: EXIT
Algorithm to delete an element from the
circular queue
Step 1: IF FRONT =
-1
Write " UNDERFLOW "
Goto Step 4
[END of IF]
Step 2: SET VAL =
QUEUE[FRONT]
Step 3: IF FRONT =
REAR
SET FRONT = REAR = -1
ELSE
IF FRONT = MAX -1
SET FRONT = 0
ELSE
SET FRONT = FRONT + 1
[END of IF]
[END OF IF]
Step 4: EXIT
Applications
of Circular Queue
1. CPU scheduling
2. Memory management
3. Traffic Management
Program
to implement circular queue using array in C:
#include <stdio.h>
int queue[4],n=4,front=-1,rear=-1;
void enqueue();
int dequeue();
void display();
void main()
{
int choice;
printf("\n 1: Insert an element into queue");
printf("\n 2: Delete an element from queue");
printf("\n 3: Display the queue elements");
printf("\n 4. exit");
while(1)
{
printf("\n Enter your choice: ");
scanf("%d", &choice);
switch(choice)
{
case 1:
enqueue();
break;
case 2:
dequeue();
break;
case 3:
display();
break;
case 4:
exit(0);
break;
default:
printf("\n Invalid choice");
}
}
}
void enqueue()
{
int ele;
printf("\n enter the element: ");
scanf("%d",&ele);
if((rear+1)%n==front)
{
printf("Queue is overflow");
}
else
if(front==-1 && rear==-1)
{
front=0;
rear=0;
queue[rear]=ele;
}
else
{
rear=(rear+1)%n;
queue[rear]=ele;
}
}
int dequeue()
{
if(front==-1)
{
printf("\nQueue is underflow");
}
else
if(front==rear)
{
printf("\nThe dequeued element is %d\n ", queue[front]);
front=-1;
rear=-1;
}
else
{
printf("\nThe dequeued element is %d\n ", queue[front]);
front=(front+1)%n;
}
}
void display()
{
if (front ==
-1)
{
printf("\nQueue is Empty");
return;
}
printf("\n Elements in Circular Queue are: ");
if (rear
>= front)
{
for (int i = front; i <= rear; i++)
printf("%d ",queue[i]);
}
else
{
for (int
i = front; i < n; i++)
printf("%d ", queue[i]);
for (int
i = 0; i <= rear; i++)
printf("%d ", queue[i]);
}
}