EDUCBA

EDUCBA

MENUMENU
  • Free Tutorials
  • Free Courses
  • Certification Courses
  • 360+ Courses All in One Bundle
  • Login
Home Data Science Data Science Tutorials Data Structures Tutorial Circular queue in Data Structure
Secondary Sidebar
Data Structures Tutorial
  • Basics
    • Linked List Advantages
    • What is Data Structure
    • Heap Data Structure
    • Types of Trees in Data Structure
    • AVL Tree in Data Structure
    • B Tree in Data Structure
    • B+ Tree in Data Structure
    • DFS Algorithm
    • BFS Algorithm
    • Arrays in Data Structure
    • Graph in Data Structure
    • Graph Representation
    • Breadth First Search
    • Depth Limited Search
    • Hashing in Data Structure
    • Searching in Data Structure
    • Linear Search in Data Structure
    • Linked List in Data Structure
    • Doubly linked list in Data Structure
    • Circular Linked List in Data Structure
    • Pointers in Data Structure
    • Types of Graph in Data Structure
    • Bubble Sort in Data Structure
    • Quick Sort in Data Structure
    • Bitonic Sort
    • Merge Sort in Data Structure
    • Selection Sort in Data Structure
    • Insertion Sort in Data Structure
    • Radix Sort in Data Structure
    • Stack in Data Structure
    • Queue in Data Structure
    • Priority Queue in Data Structure
    • Asymptotic Analysis
    • Tree Traversal in Data Structure
    • Tree Traversal Techniques
    • Trie Data Structure
    • Splay Tree in Data Structure
    • Spanning Tree Algorithm
    • Sparse Matrix in Data Structure
    • Radix Sort Algorithm
    • Counting Sort Algorithm
    • Skip List Data Structure
    • Linked List Algorithm
    • Linked List Types
    • Inorder Traversal of Binary Tree
    • Kruskals Algorithm
    • Prims Algorithm
    • BFS VS DFS
    • BCNF
    • Skip List
    • Hash Table?in Data Structure
    • Data Structure Interview Questions
    • Data Structures & Algorithms Interview
    • AVL Tree Deletion
    • B+ Tree Deletion
    • Decision Tree Advantages and Disadvantages
    • Data Architect Skills
    • Data Architecture Principles
    • Data Engineer Jobs
    • Data Engineer Roadmap
    • Fundamentals of Data Structure
    • Circular queue in Data Structure
    • Spanning Tree in Data Structure
    • Tree traversal types
    • Deque in Data structure
    • Shell Sort in Data Structure
    • Heap sort in data structure
    • Heap data structure C++
    • Heap data structure in Java
    • Binary Search Tree Types
    • Binary Tree in Data Structure
    • Binary Tree Types
    • Binary search tree in data structure
    • Binary Search Tree Advantages
    • Binary Search Tree Properties
    • Binary Search in Data Structure
    • Binary Tree Deletion
    • Sparse Matrix Multiplication
    • Preorder Traversal of Binary Tree
    • Postorder traversal
    • Decision Tree Hyperparameters
    • PostOrder Traversal without Recursion
    • AVL Tree Rotation
    • Avro File Format
    • Decision Tree Types
    • Binomial heap
    • Confluence Jira Integration
    • Timm Sort
    • Depth First Search
    • Stock Span Problem

Circular queue in Data Structure

Circular queue in Data Structure

Introduction to Circular queue in Data Structure

A circular queue is a data structure that helps to store the data linearly and is similar to the normal simple queue but with functionality where the last element is connected to the first one. This facilitates the insertion of the new element in the queue even when the queue is full, provided the first place of the queue is empty. This article will learn about the circular queue, the applications and usage of the circular queue, and learn about the operations that can be performed on a circular queue and an example using the C programming language for implementation.

Structure of Circular Queue

The operations performed on the circular queue are based on a FIFO basis which stands for first in first out principle, which means that the first element which is inserted in the circular queue will also be the first one that will be removed. Thus, the circular queue is also known as the ring buffer commonly. The end of the queue from where we perform the insertion of new elements in the queue, also known as enqueue operation, is called the rear position while the end from where we perform the delete operation is called the front end. The following figure shows the visual representation of the working of the circular queue and how the data is stored in it.

Start Your Free Data Science Course

Hadoop, Data Science, Statistics & others

The circular queue right now contains five elements, and the front is pointing to the 0th element while the rear is to the 4th index element. If the insertion is made, then the rear will be increased by one, which means rear = rear + 1 while be done for en queue operation. In case if we want to perform the delete operation, then the front will be increased by one, which means that front = front + 1, and the element at the 0th index will be deleted, which is also called dequeued.

Operations on circular queue

The following operations can be made on the circular queue –

  • Rear – This operation will retrieve the last element of the circular queue.
  • Front – This operation will help in retrieving the first element of the circular queue.
  • enQueue(value) – This operation will perform the insertion of the new value, which is supplied as the argument between the parenthesis to this enQueue function. The en queue operation will always be performed from the rear end of the circular queue.

While performing the enqueue operation, the algorithm will check if the queue is already occupied or full by checking the condition rear is equal to the size of queue -1 and front is exactly equal to 0 or the condition that becomes full for the queue is rear will be equal to front -1. When we denote front by f and rear by r, the condition will be as shown below –

((r==size-1 && f==0) || (r == front-1))

Then the algorithm will display that the queue is full of the above condition evaluates to true. If the condition results in false, then a new element will get inserted from the rear side, setting the rear to 0 if the queue is already full or incrementing it by one in another case.

  • Dequeue() –

This operation will result in the deletion of one element from the element which was pointed by the front resulting in decreasing the value of the front by 1 in the circular queue. While performing the deletion, the algorithm checks whether the queue is empty using the condition front is exactly equal to -1, that is, f == -1. If the condition evaluates to true, then it will display that the circular queue is empty, and if not, then it will check if the front is exactly equal to the rear and, if so, set the front value as rear minus 1, i.e. f= =r-1. If not, then the check whether the front is equal to the size minus 1 is done, i.e. f == r-1, and if it results in true, then the front is set to 0, f= 0, and the deleted element value is returned.

Implementation of the circular queue

The operations which we discussed previously on the circular queue can be used using any programming language. Let us see how we can implement a circular queue using a C programming language. The following program implements the circular queue, and the names of the functions are self-defining.

#include<bits/stdc++.h>
using namespace std;
struct CircularQueue
{
// Initialize the value of front and rear ends
int r, f;
// Specifications of Circular Queue
int size;
int *arr;
CircularQueue(int s)
{
f = r = -1;
size = s;
arr = new int[s];
}
void  insertInCircularQueueORenQueue(int value);
int  deleteFromCircularQueueORdeQueue();
void showQueue();
};
/* Function to create Circular queue */
void CircularQueue:: insertInCircularQueueORenQueue(int value)
{
if ((f == 0 && r == size-1) ||
(r == (f-1)%(size-1)))
{
printf("\nQueue is completely occupied or Full");
return;
}
else if (f == -1) /* Add First value*/
{
f = r = 0;
arr[r] = value;
}
else if (r == size-1 && f != 0)
{
r = 0;
arr[r] = value;
}
else
{
r++;
arr[r] = value;
}
}
int CircularQueue:: deleteFromCircularQueueORdeQueue()
{
if (f == -1)
{
printf("\nCircular Queue is Empty");
return INT_MIN;
}
int data = arr[f];
arr[f] = -1;
if (f == r)
{
f = -1;
r = -1;
}
else if (f == size-1)
f = 0;
else
f++;
return data;
}
void CircularQueue::showQueue()
{
if (f == -1)
{
printf("\nCircular Queue is Empty");
return;
}
printf("\nCircular queue currently contains the following elements : ");
if (r >= f)
{
for (int i = f; i <= r; i++)
printf("%d ",arr[i]);
}
else
{
for (int i = f; i < size; i++)
printf("%d ", arr[i]);
for (int i = 0; i <= r; i++)
printf("%d ", arr[i]);
}
}
int main()
{
CircularQueue q(5);
// Insert few elements in Queue
1. insertInCircularQueueORenQueue(14);
2. insertInCircularQueueORenQueue(22);
3. insertInCircularQueueORenQueue(13);
4. insertInCircularQueueORenQueue(-6);
// Show all the current elements present in the circular queue
q.showQueue();
// Delete the elements from the queue
printf("\nElement deleted from circular queue  = %d", q. deleteFromCircularQueueORdeQueue());
printf("\nElement deleted from circular queue  = %d", q. deleteFromCircularQueueORdeQueue());
q.showQueue();
1. insertInCircularQueueORenQueue(9);
2. insertInCircularQueueORenQueue(20);
3. insertInCircularQueueORenQueue(5);
q.showQueue();
1 insertInCircularQueueORenQueue(20);
return 0;
}

The output of the above code is as shown below –

Circular queue in Data Structure output

Conclusion

The circular queue is a linear data structure whose end is connected to the start and is used in the traffic system, memory management, and CPU scheduling.

Recommended Articles

This is a guide to the Circular queue in Data Structure. Here we discuss the operations that can be performed on a circular queue, along with an example. You may also have a look at the following articles to learn more –

  1. DB2 Data Types
  2. Data Link Layer Services
  3. Data Warehouse Software
  4. Heap Data Structure
Popular Course in this category
Data Scientist Training (85 Courses, 67+ Projects)
  85 Online Courses |  67 Hands-on Projects |  660+ Hours |  Verifiable Certificate of Completion
4.8
Price

View Course

Related Courses

All in One Data Science Bundle (360+ Courses, 50+ projects)4.9
Oracle DBA Database Management System Training (2 Courses)4.8
SQL Training Program (10 Courses, 8+ Projects)4.7
Primary Sidebar
Footer
About Us
  • Blog
  • Who is EDUCBA?
  • Sign Up
  • Live Classes
  • Corporate Training
  • Certificate from Top Institutions
  • Contact Us
  • Verifiable Certificate
  • Reviews
  • Terms and Conditions
  • Privacy Policy
  •  
Apps
  • iPhone & iPad
  • Android
Resources
  • Free Courses
  • Database Management
  • Machine Learning
  • All Tutorials
Certification Courses
  • All Courses
  • Data Science Course - All in One Bundle
  • Machine Learning Course
  • Hadoop Certification Training
  • Cloud Computing Training Course
  • R Programming Course
  • AWS Training Course
  • SAS Training Course

ISO 10004:2018 & ISO 9001:2015 Certified

© 2023 - EDUCBA. ALL RIGHTS RESERVED. THE CERTIFICATION NAMES ARE THE TRADEMARKS OF THEIR RESPECTIVE OWNERS.

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you

Let’s Get Started

By signing up, you agree to our Terms of Use and Privacy Policy.

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you
EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you
EDUCBA Login

Forgot Password?

By signing up, you agree to our Terms of Use and Privacy Policy.

This website or its third-party tools use cookies, which are necessary to its functioning and required to achieve the purposes illustrated in the cookie policy. By closing this banner, scrolling this page, clicking a link or continuing to browse otherwise, you agree to our Privacy Policy

Loading . . .
Quiz
Question:

Answer:

Quiz Result
Total QuestionsCorrect AnswersWrong AnswersPercentage

Explore 1000+ varieties of Mock tests View more