Scribd
Upload
2K views4 pages

Circular Queue Implementation in C

A circular queue is a linear data structure that is similar to a regular queue but with the last node connected back to the first node, forming a circle. This solves limitations of the normal queue by making better use of unused memory locations. Common operations on a circular queue are enqueue, dequeue, front, and rear. Circular queues are useful for applications like memory management, traffic light systems, and CPU scheduling where processes wait to be executed.

Uploaded by

akurathikotaiah
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
2K views4 pages

Circular Queue Implementation in C

A circular queue is a linear data structure that is similar to a regular queue but with the last node connected back to the first node, forming a circle. This solves limitations of the normal queue by making better use of unused memory locations. Common operations on a circular queue are enqueue, dequeue, front, and rear. Circular queues are useful for applications like memory management, traffic light systems, and CPU scheduling where processes wait to be executed.

Uploaded by

akurathikotaiah
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Circular Queue

A circular queue in C stores the data in a very practical manner. It is a linear data structure. It is very
similar to the queue. The only difference is that the last node is connected back to the first node. Thus it
is called a circular queue.

Circular Queue In C

A circular queue solved the limitations of the normal queue. Thus making it a
better pick than the normal queue. It also follows the first come first serve
algorithm. Circular Queue is also called ring Buffer.

Operations On A Circular Queue

Enqueue- adding an element in the queue if there is space in the queue.

Dequeue- Removing elements from a queue if there are any elements in


the queue

Front- get the first item from the queue.

Rear- get the last item from the queue.

isEmpty/isFull- checks if the queue is empty or full.

Applications:

1. Memory Management: The unused memory locations in the case of ordinary queues
can be utilized in circular queues.
2. Traffic system: In computer controlled traffic system, circular queues are used to switch
on the traffic lights one by one repeatedly as per the time set.
3. CPU Scheduling: Operating systems often maintain a queue of processes that are ready
to execute or that are waiting for a particular event to occur.
#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)
{
front = 0;
rear = 0;
}
else
{
if(rear == MAX-1)
rear = 0;
else
rear = rear+1;
}
cqueue_arr[rear] = item ;
}
void deletion()
{
if(front == -1)
{
printf("Queue Underflown");
return ;
}
printf("Element deleted from queue is : %dn",cqueue_arr[front]);
if(front == rear)
{
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 emptyn");
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");
}
void main()
{
int choice,item;
do
{
printf("[Link]");
printf("[Link]");
printf("[Link]");
printf("[Link]");
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 :
deletion();
break;
case 3:
display();
break;
case 4:
break;
default:
printf("Wrong choicen");
}
}
while(choice!=4);
getch();
}

Common questions

Powered by AI

In a circular queue, the front pointer indicates the position of the first element, ready for removal, whereas the rear pointer shows where the next element will be inserted. These pointers help manage the queue's wrap-around nature, ensuring that elements can be added or removed cyclically over the queue's array without redundancy. Both pointers are critical for maintaining the integrity and operation of the queue, preventing data overwriting at the boundary condition when processing continuous enqueue-dequeue operations .

The deletion operation in a circular queue is handled by removing the element at the position indicated by the front pointer. If the front matches the rear pointer, meaning the queue only contains one element, both front and rear pointers are reset to -1, making the queue empty, indicating underflow. If the front is at the end of the queue array, it wraps around to index 0 in the array to continue deletion seamlessly from the start of the queue .

Circular queues are more beneficial than regular queues in scenarios where memory efficiency and cyclic resource management are required. Examples include memory management systems that need to effectively utilize available memory space, traffic systems that require cyclic activation of traffic lights, and CPU scheduling where processes need to be cyclically managed in an operating system .

The primary advantage of a circular queue over a linear queue is its ability to reuse unused memory, thereby solving the memory underutilization problem seen in linear queues. In a linear queue, once the queue's rear reaches the end of the queue, no more elements can be inserted even if there are empty spaces at the front. A circular queue links the last position back to the first position, thus allowing insertion into previously used and now free positions, effectively utilizing all available space in the data structure .

The circular nature of queues aids in traffic system management by allowing the seamless rotation or cycling of control signals like traffic lights. The queue cyclically moves through traffic signals, turning them on and off in a pre-defined time sequence. This ensures an even distribution of control times for each direction, promoting smooth traffic flow and reducing congestion and wait times at intersections .

Circular queues enhance the efficiency and reliability of memory management by ensuring that all allocated memory space is used optimally. Unused memory locations in other structures such as linear queues can result in inefficient memory usage. By implementing a circular queue, memory locations at the beginning of the queue can be cyclically reused for new entries once they are freed, thus preventing memory wastage and increasing overall application efficiency .

The wrapping around of the rear pointer is crucial in a circular queue as it allows the queue to utilize the entirety of the pre-allocated space. When the rear pointer reaches the end of the array, it wraps back to the beginning of the array (if positions are free), enabling efficient use of all available slots in the array. This mechanism allows new elements to be added even though the end of the array has been reached, preventing wastage of space .

Despite its advantages, circular queues have limitations such as a fixed size, leading to potential overflows if not sized correctly for the application's needs. It also requires more complex implementation and management than linear queues due to the need to handle wrapping of indices. In scenarios requiring dynamic memory allocation or where varying-sized data blocks need to be managed, circular queues may not be optimal. Additionally, for applications that don't benefit from the cyclic nature of processes, a linear queue may suffice .

Circular queues play a crucial role in CPU scheduling by allowing processes to be managed in a fair and efficient manner. Operating systems utilize circular queues to cycle through waiting processes efficiently. Each process is queued in a circular fashion, ensuring they all get executed in the order they are queued without starving any processes while also utilizing the computing resources fully by executing all processes periodically .

In a circular queue, the enqueue operation involves adding an element at the position of the rear pointer. The main concern is preventing overflow, which happens when the queue is full. This is checked by observing if the next position of the rear is the front, indicating no free space is available. If overflow is detected, the operation is aborted. If the rear is at the last position of the queue array, it wraps around to the first position (index 0) when more insertions are needed .

You might also like