Circular Queue
A circular queue, also known as a circular buffer, is an abstract data type that represents a linear collection of elements with a fixed size. Unlike a traditional linear queue (also called a linear buffer), a circular queue allows elements to be inserted and removed from both ends efficiently. It achieves this by treating the underlying storage as a circular data structure, where the rear and front ends of the queue wrap around to the beginning when they reach the end of the allocated storage.
Fixed Size: It has a predetermined fixed size or capacity that cannot be exceeded.
Circular Behavior: When the rear end reaches the end of the storage, it wraps around to the beginning, creating a circular effect.
Efficient Space Usage: Circular queues efficiently utilize memory by reusing space that becomes available after elements are dequeued (removed).
Now, let's look at the algorithms for common operations in a circular queue:
Components of a Circular Queue:
Array: The underlying data structure of a circular queue is typically an array of fixed size, which holds the elements.
Front: An index pointing to the front (or the first element) of the queue.
Rear: An index pointing to the rear (or the last element) of the queue.
Size: The maximum capacity or size of the circular queue, which remains constant once initialized.
Initialization: Creating an empty circular queue with the specified size.
Enqueue (Insertion): Adding an element to the rear of the circular queue.
Dequeue (Deletion): Removing an element from the front of the circular queue.
IsEmpty: Checking if the circular queue is empty.
IsFull: Checking if the circular queue is full.
Applications:
Circular queues are commonly used in computer systems, such as scheduling processes in an operating system.
They are used for managing data buffers in devices like keyboards, mice, and network routers.
Circular queues can be found in various algorithms and data structures like Breadth-First Search (BFS) traversal in graphs.
Algorithms
1. Initialization :
The initialization algorithm sets up the circular queue data structure with the following steps:
InitializeCircularQueue():
1. Create an array 'queue' of fixed size to store elements.
2. Initialize 'front' and 'rear' to -1 to indicate an empty queue.
2.Enqueue (Insertion) :
The enqueue algorithm adds an element to the rear of the circular queue:
3.Dequeue (Deletion) :
The dequeue algorithm removes and returns an element from the front of the circular queue:
4.IsEmpty :
The isEmpty algorithm checks if the circular queue is empty:
5.IsFull :
The isFull algorithm checks if the circular queue is full:
The enqueue algorithm adds an element to the rear of the circular queue:
Enqueue(queue, item):
1. Check if the queue is full by using the IsFull() function.
2. If the queue is full, return an error message or resize the queue (if allowed).
3. If the queue is empty (front and rear are both -1), set front and rear to 0.
4. If the queue is not empty, increment 'rear' using modular arithmetic to wrap around:
rear = (rear + 1) % queue.size
5. Place the 'item' at the new 'rear' position in the 'queue' array:
queue[rear] = item
The dequeue algorithm removes and returns an element from the front of the circular queue:
Dequeue(queue):
1. Check if the queue is empty by using the IsEmpty() function.
2. If the queue is empty, return an error message or handle the empty queue condition.
3. If the queue has only one element (front and rear are the same), save the element in 'temp':
- temp = queue[front]
- Set 'front' and 'rear' to -1 to indicate an empty queue.
4. If the queue has more than one element:
- Save the element at the 'front' position in 'temp':
temp = queue[front]
- Increment 'front' using modular arithmetic to wrap around:
front = (front + 1) % queue.size
5. Return 'temp', which is the dequeued element.
The isEmpty algorithm checks if the circular queue is empty:
IsEmpty(queue):
1. Check if 'front' is equal to -1. If yes, the queue is empty; return True.
2. Otherwise, return False.
The isFull algorithm checks if the circular queue is full:
IsFull(queue):
1. Check if the next position after 'rear' using modular arithmetic is equal to 'front'.
( rear +1 % queue.size == front)
2. If they are equal, the queue is full; return True.
3. Otherwise, return False.
These detailed algorithms describe how to initialize, enqueue, dequeue, and check the status of a circular queue. The use of modular arithmetic in incrementing 'rear' and 'front' ensures that the circular behaviour of the queue is correctly implemented.
C Program Implementation- Circular Queue
/*******************************************************************************/
#include <stdio.h>
#include<stdlib.h>
#include <stdbool.h>
#define MAX 10
// initilazing queue
int cqueue[MAX];
int rear = - 1;
int front = -1;
// Function to check if the cqueue is empty
bool isEmpty() {
return front==-1 ;
}
// Function to check if the cqueue is full
bool isFull() {
return (rear+1)%MAX == front;
}
void insert() // enqueue
{
int item;
if (isFull())
printf("Queue Overflow \n");
else
{
printf("\nInset the element in queue : ");
scanf("%d", &item);
if(isEmpty())
front=rear=0;
else
rear = (rear + 1)%MAX;
cqueue[rear] = item;
}
} /*End of insert()*/
void delete() //dequeue
{
if(isEmpty())
{
printf("\nQueue Underflow \n");
return ;
}
printf("\nElement deleted from queue is : %d\n", cqueue[front]);
if ( rear == front )
{
front=rear=-1;//make it empty
}
else
{
front = (front + 1) %MAX;
}
} /*End of delete() */
void display()// print queue
{
int i;
if (isEmpty() )
printf("\nQueue is empty \n");
else
{ printf("\nQueue is : ");
if(front==rear)
printf("%d\n", cqueue[front]);
else
{
for (i = front; i != rear; i=(i+1)%MAX)
printf("%d ", cqueue[i]);
printf("%d ", cqueue[i]); //print the element at rear
printf("\n");
}
}
}
// Function to peek at the front item
int peek() {
if (isEmpty()) {
printf("Queue is empty. Nothing to peek.\n");
return -1; // Error value
} else {
return cqueue[front];
}
}
// Function to get the size of the queue
int size() {
if (isEmpty()) {
return 0;
} else {
if (rear >= front ) return rear - front + 1;
else return MAX-front+rear-0+1;
}
}
int main()
{
int choice;
while (1)
{
printf("\n1.Insert element to queue \n");
printf("2.Delete element from queue \n");
printf("3.Display all elements of queue \n");
printf("4.Peek \n");
printf("5.Size of the queue\n");
printf("6.Quit \n");
printf("\nEnter your choice : ");
scanf("%d", &choice);
switch (choice)
{
case 1:
insert();
break;
case 2:
delete();
break;
case 3:
display();
break;
case 4:
int x=peek();
if(x!=-1) printf("\nfront element is=%d\n",x);
break;
case 5:
printf("\nsize of the queue is =%d\n",size());
break;
case 6:
exit(1);
default:
printf("\nWrong choice \n");
} /*End of switch*/
} /*End of while*/
return 0;
} /*End of main()*/
A simple queue and a circular queue are both data structures used to organize elements in a linear order. However, they differ in terms of their underlying implementation and certain characteristics. Let's explore the differences between a simple queue and a circular queue:
Implementation:
Simple Queue: In a simple queue, elements are stored in a linear manner, and when the queue is full, no more elements can be added until some elements are dequeued (removed).
Circular Queue: A circular queue also stores elements in a linear manner, but it uses a circular arrangement of the underlying array or linked list. When the last position is reached, the next position is the first one, creating a circular structure.
Handling Overflow:
Simple Queue: When a simple queue is full, attempting to enqueue (add) more elements will result in an overflow condition, and the enqueue operation will fail.
Circular Queue: In a circular queue, if the rear pointer reaches the end and there is space available at the beginning, the next element can be inserted at the beginning of the queue, effectively making it a circular structure and avoiding overflow.
Handling Underflow:
Simple Queue: In a simple queue, when attempting to dequeue (remove) an element from an empty queue, an underflow condition occurs, and the dequeue operation will fail.
Circular Queue: In a circular queue, if the front and rear pointers meet, the queue is considered empty. To distinguish between an empty queue and a full queue, an additional condition (such as keeping one position empty) may be used.
Memory Utilization:
Simple Queue: In a simple queue, the memory allocated for the queue may not be fully utilized if there are dequeued positions that remain empty.
Circular Queue: A circular queue can make more efficient use of memory as positions become available for reuse once elements are dequeued.
Traversal:
Simple Queue: Traversal in a simple queue is straightforward, as elements are stored linearly from front to rear.
Circular Queue: Traversal in a circular queue requires handling the circular nature, ensuring that the traversal process wraps around from the end to the beginning.
In summary, while both simple queues and circular queues are used for managing data in a first-in-first-out (FIFO) manner, circular queues offer advantages in terms of better memory utilization and the ability to handle a dynamic circular arrangement of elements.
Comments
Post a Comment