Algorithm in C – Circular Queue Data Structure

Hits: 232

Circular Queue Data Structure

 

In this tutorial, you will learn what a circular queue is. Also, you will find implementation of circular queue in C.

demonstrate how we cannot add element even after removing some element from the queue
Limitation of the regular Queue

As you can see in the above image, after a bit of enqueuing and dequeuing, the size of the queue has been reduced.

The indexes 0 and 1 can only be used after the queue is reset when all the elements have been dequeued.


How Circular Queue Works

Circular Queue works by the process of circular increment i.e. when we try to increment the pointer and we reach the end of the queue, we start from the beginning of the queue.

Here, the circular increment is performed by modulo division with the queue size. That is,

if REAR + 1 == 5 (overflow!), REAR = (REAR + 1)%5 = 0 (start of queue)
Circular increment in circular queue
Circular queue representation

Circular Queue Operations

The circular queue work as follows:

  • two pointers FRONT and REAR
  • FRONT track the first element of the queue
  • REAR track the last elements of the queue
  • initially, set value of FRONT and REAR to -1

 

1. Enqueue Operation

  • check if the queue is full
  • for the first element, set value of FRONT to 0
  • circularly increase the REAR index by 1 (i.e. if the rear reaches the end, next it would be at the start of the queue)
  • add the new element in the position pointed to by REAR

 

2. Dequeue Operation

  • check if the queue is empty
  • return the value pointed by FRONT
  • circularly increase the FRONT index by 1
  • for the last element, reset the values of FRONT and REAR to -1

However, the check for full queue has a new additional case:

  • Case 1: FRONT = 0 && REAR == SIZE - 1
  • Case 2: FRONT = REAR + 1

 

The second case happens when REAR starts from 0 due to circular increment and when its value is just 1 less than FRONT, the queue is full.

enqueue and dequeue operation of the circular queue
Enque and Deque Operations

Circular Queue Implementations in C

The most common queue implementation is using arrays, but it can also be implemented using lists.

// Circular Queue implementation in C

#include <stdio.h>

#define SIZE 5

int items[SIZE];
int front = -1, rear = -1;

// Check if the queue is full
int isFull(){
  if ((front == rear + 1) || (front == 0 && rear == SIZE - 1)) return 1;
  return 0;
}

// Check if the queue is empty
int isEmpty(){
  if (front == -1) return 1;
  return 0;
}

// Adding an element
void enQueue(int element){
  if (isFull())
    printf("n Queue is full!! n");
  else {
    if (front == -1) front = 0;
    rear = (rear + 1) % SIZE;
    items[rear] = element;
    printf("n Inserted -> %d", element);
  }
}

// Removing an element
int deQueue(){
  int element;
  if (isEmpty()) {
    printf("n Queue is empty !! n");
    return (-1);
  } else {
    element = items[front];
    if (front == rear) {
      front = -1;
      rear = -1;
    } 
    // Q has only one element, so we reset the 
    // queue after dequeing it. ?
    else {
      front = (front + 1) % SIZE;
    }
    printf("n Deleted element -> %d n", element);
    return (element);
  }
}

// Display the queue
void display(){
  int i;
  if (isEmpty())
    printf(" n Empty Queuen");
  else {
    printf("n Front -> %d ", front);
    printf("n Items -> ");
    for (i = front; i != rear; i = (i + 1) % SIZE) {
      printf("%d ", items[i]);
    }
    printf("%d ", items[i]);
    printf("n Rear -> %d n", rear);
  }
}

int main(){
  // Fails because front = -1
  deQueue();

  enQueue(1);
  enQueue(2);
  enQueue(3);
  enQueue(4);
  enQueue(5);

  // Fails to enqueue because front == 0 && rear == SIZE - 1
  enQueue(6);

  display();
  deQueue();

  display();

  enQueue(7);
  display();

  // Fails to enqueue because front == rear + 1
  enQueue(8);

  return 0;
}

Circular Queue Complexity Analysis

The complexity of the enqueue and dequeue operations of a circular queue is O(1) for (array implementations).


Applications of Circular Queue

  • CPU scheduling
  • Memory management
  • Traffic Management

 

Python Example for Beginners

Two Machine Learning Fields

There are two sides to machine learning:

  • Practical Machine Learning:This is about querying databases, cleaning data, writing scripts to transform data and gluing algorithm and libraries together and writing custom code to squeeze reliable answers from data to satisfy difficult and ill defined questions. It’s the mess of reality.
  • Theoretical Machine Learning: This is about math and abstraction and idealized scenarios and limits and beauty and informing what is possible. It is a whole lot neater and cleaner and removed from the mess of reality.

Data Science Resources: Data Science Recipes and Applied Machine Learning Recipes

Introduction to Applied Machine Learning & Data Science for Beginners, Business Analysts, Students, Researchers and Freelancers with Python & R Codes @ Western Australian Center for Applied Machine Learning & Data Science (WACAMLDS) !!!

Latest end-to-end Learn by Coding Recipes in Project-Based Learning:

Applied Statistics with R for Beginners and Business Professionals

Data Science and Machine Learning Projects in Python: Tabular Data Analytics

Data Science and Machine Learning Projects in R: Tabular Data Analytics

Python Machine Learning & Data Science Recipes: Learn by Coding

R Machine Learning & Data Science Recipes: Learn by Coding

Comparing Different Machine Learning Algorithms in Python for Classification (FREE)

Disclaimer: The information and code presented within this recipe/tutorial is only for educational and coaching purposes for beginners and developers. Anyone can practice and apply the recipe/tutorial presented here, but the reader is taking full responsibility for his/her actions. The author (content curator) of this recipe (code / program) has made every effort to ensure the accuracy of the information was correct at time of publication. The author (content curator) does not assume and hereby disclaims any liability to any party for any loss, damage, or disruption caused by errors or omissions, whether such errors or omissions result from accident, negligence, or any other cause. The information presented here could also be found in public knowledge domains.  

Google –> SETScholars