Last Updated on May 9, 2023 by Prepbytes
Circular queues are a typical data structure in operating systems. It is employed to control how computer programs or procedures are carried out. To hold the processes in the order of their insertion, you use a circular queue as a buffer. When allocating resources or executing them, you then remove the processes from the queue.
What is a Circular Queue?
A circular queue is an expanded version of a linear queue that adheres to the First In First Out tenet, with the difference that it forms a circular link from the final node of the queue to the first. It is also known as a Ring Buffer as result.
The Circular Queue: How Does It Operate?
The Circular Queue is comparable to a Linear Queue in that it adheres to the FIFO (First In First Out) concept, but it varies in that the end position is linked to the first position to create a circle.
Operations in the circular queue are:
- Front – used to obtain the circular queue’s first component.
- Rear – used to obtain the circular queue’s last component.
- enQueue(value) – utilized to add a fresh value to the circular queue. This procedure begins at the end of the queue.
- deQueue() – Used to delete a value from the Circular Queue. From the head of the queue, this operation is performed.
Implementing Queue Operations
While implementing a circular queue using a linked list, the queue has two main actions, Enqueue() and Dequeue() let you control how the data flows. These operations need constant execution time, or O(1), because they are independent of the queue’s size or the number of entries it contains.
-
Enqueue(x) Operation
The steps to insert the element in the circular queue are as follows:- Step 1: Determine if the queue is full by checking (Rear + 1 % Maxsize = Front).
- Step 2: If the queue is full, an Overflow error will appear.
- Step 3: If the line is empty, verify that the Front and Rear are both set to 0.
- Step 4: Rear should be set to 0 if Rear = Maxsize – 1 & Front!= 0 (rear pointer is at the end of the queue and front is not at index 0).
- Step 5: If not, make Rear equal to (Rear + 1)% Maxsize.
- Step 6: Add the element (Queue[Rear] = x) to the queue.
- Step 7: End
-
Deque Operation
Accessing the data where the front is pointing and removing the data after access are the two subtasks that makeup getting data from the queue.- Step 1: If the front and back of the queues are both -1, the queue is empty.
- Step 2: When the queue is empty, a mistake in the underflow
- Step 3: Set Element = Queue[Front]
- Step 4: Set Front and Rear to -1 (IF Front = Rear, set Front = Rear = -1) if a queue only has one element.
- Step 5: And set Front to 0 if Front = Maxsize -1.
- Step 6: If not, change Front to Front + 1.
- Step 7: End
Implementation of Circular Queue using Linked List
The C programming language’s linked list implementation of a circular queue is shown below.
#include <stdio.h>
struct node
{
int data;
struct node *next;
};
struct node *front=-1;
struct node *rear=-1;
void enqueue(int x)
{
struct node *newnode;
newnode=(struct node *)malloc(sizeof(struct node));
newnode->data=x;
newnode->next=0;
if(rear==-1)
{
front=rear=newnode;
rear->next=front;
}
else
{
rear->next=newnode;
rear=newnode;
rear->next=front;
}
}
// function to delete the element from the queue
void dequeue()
{
struct node *temp;
temp=front;
if((front==-1)&&(rear==-1))
{
printf("\nQueue is empty");
}
else if(front==rear)
{
front=rear=-1;
free(temp);
}
else
{
front=front->next;
rear->next=front;
free(temp);
}
}
// function to get the front of the queue
int peek()
{
if((front==-1) &&(rear==-1))
{
printf("\nQueue is empty");
}
else
{
printf("\nThe front element is %d", front->data);
}
}
// function to display all the elements of the queue
void display()
{
struct node *temp;
temp=front;
printf("\n The elements in a Queue are : ");
if((front==-1) && (rear==-1))
{
printf("Queue is empty");
}
else
{
while(temp->next!=front)
{
printf("%d,", temp->data);
temp=temp->next;
}
printf("%d", temp->data);
}
}
void main()
{
enqueue(14);
enqueue(11);
enqueue(13);
display();
dequeue();
peek();
} Output
The elements in a Queue are: 14,11,13
The front element is 11Conclusion
You studied circular queue using linked lists in a data structure in this tutorial. A linear queue’s implementation problem with memory waste is solved with a circular queue. The procedures for implementing basic circular queue operations were also followed. The construction of queue activities was then explained to you using a drive-through coding example. Additionally, you came across the C programming language’s linked list-based queue coding implementation.
Frequently Asked Questions
Q1. Can a circular queue be created similarly to a circular linked list?
Ans. A type of queue data structure is a circular queue. The circular queue may be equaled by the circular linked list if we compare the linear queue to the linear single linked list. This article describes how to build a circular queue in C++ using a circular linked list.
Q2. What is the complexity of a circular queue using a linked list?
Ans. A circular linked list or an array can be used to implement it. Each operation in a queue has an O(1) time complexity.
Q3. What is the circular linked list’s logic?
Ans. A circular linked list is a type of linked list where every node points to every other node, forming a complete circle. Or to put it another way, this particular linked list variant doesn’t contain a null member at the end.
Q4. Are there two node pointers in a circular queue using linked list?
Ans. Two NULL pointers are present in a circular doubly linked list. In a doubly-linked list, the final node’s ‘Next’ attribute links to the first node. The first node’s ‘Prev’ attribute links to the final node.
Q5. In a circular queue using linked list, may any node have a null value?
Ans. There is no null pointer in a circular linked list since each node links to a different node.