Home » Data Structure » Circular Queue Representation using Array

Circular Queue Representation using Array

Last updated:

Support this post with a reaction:

5,455 views

What Is a Circular Queue and How Is It Implemented Using an Array?

A Circular Queue is a linear data structure that follows the FIFO (First In, First Out) principle. Unlike a simple queue, a circular queue connects the last position of an array back to its first position, forming a logical circle.

This arrangement allows the queue to reuse empty spaces created after deleting elements. Therefore, it avoids the memory wastage that can occur in a linear queue implemented using an array.

A circular queue is commonly used in CPU scheduling, memory management, buffering, and operating systems.

What Is a Circular Queue?

A circular queue is a special type of queue in which the last position is logically connected to the first position.

It uses two pointers:

  • Front: Points to the first element in the queue.
  • Rear: Points to the last element in the queue.

When the rear pointer reaches the last array position, it moves back to index 0 if an empty position is available.

Similarly, when the front pointer reaches the last position during deletion, it moves back to the beginning.

This movement is called circular movement or wrap-around.

Example of Circular Queue

Consider a circular queue of size 5.

Initially, the queue is empty. After inserting five elements, the array looks like this:

Index01234
Element1020304050

Now, suppose we delete two elements (10 and 20).

The queue contains:

Index01234
ElementEmptyEmpty304050

When we insert new elements, the circular queue reuses index 0 and index 1 instead of wasting those positions.

This is the main advantage of a circular queue.

How Does a Circular Queue Work?

A circular queue works using two pointers, front and rear, and follows the FIFO principle.

The main operations are:

  1. Enqueue – Insert an element into the queue.
  2. Dequeue – Remove an element from the queue.
  3. Display – Display all elements present in the queue.

1. Enqueue Operation

Enqueue is the process of inserting a new element at the rear of the circular queue.

Steps:

  1. Check whether the queue is full.
  2. If the queue is full, display Queue Overflow.
  3. If the queue is empty, initialize front and rear to 0.
  4. Otherwise, update rear using the circular increment formula.
  5. Insert the new element at the rear position.

The formula for updating rear is:

rear=(rear+1)modn rear=(rear+1)\bmod n

Here, n represents the maximum size of the queue.

2. Dequeue Operation

Dequeue is the process of deleting an element from the front of the circular queue.

Steps:

  1. Check whether the queue is empty.
  2. If the queue is empty, display Queue Underflow.
  3. Otherwise, remove the element at the front position.
  4. If front and rear are equal, reset both to -1.
  5. Otherwise, update front using the circular increment formula.

The formula is:

front=(front+1)modn front=(front+1)\bmod n

3. Display Operation

The display operation prints all elements currently stored in the circular queue.

Steps:

  1. Check whether the queue is empty.
  2. Start from the front position.
  3. Print the current element.
  4. Move to the next index using circular increment.
  5. Continue until the rear position is reached.

How Is a Circular Queue Represented Using an Array?

A circular queue can be implemented using a one-dimensional array and two integer variables named front and rear.

Consider the following declaration in C:

#define SIZE 5

int queue[SIZE];
int front = -1;
int rear = -1;

Here:

  • queue[SIZE] stores the queue elements.
  • front stores the index of the first element.
  • rear stores the index of the last element.
  • front = -1 and rear = -1 indicate an empty queue.

The array is treated as circular using the modulo operator.

Algorithm for Circular Queue Operations

Algorithm for Enqueue in Circular Queue

Input: An element to be inserted.

Output: Element inserted successfully or Queue Overflow.

ENQUEUE(queue, value)

1. If (rear + 1) % SIZE == front
      Print "Queue Overflow"
      Return

2. If front == -1
      front = 0
      rear = 0
   Else
      rear = (rear + 1) % SIZE

3. queue[rear] = value

4. Stop

Algorithm for Dequeue in Circular Queue

Input: Circular queue.

Output: Deleted element or Queue Underflow.

DEQUEUE(queue)

1. If front == -1
      Print "Queue Underflow"
      Return

2. value = queue[front]

3. If front == rear
      front = -1
      rear = -1
   Else
      front = (front + 1) % SIZE

4. Print deleted value

5. Stop

Algorithm for Display in Circular Queue

DISPLAY(queue)

1. If front == -1
      Print "Queue is Empty"
      Return

2. i = front

3. Repeat
      Print queue[i]
      If i == rear
          Break
      i = (i + 1) % SIZE

4. Stop

C Program to Implement Circular Queue Using Array

The following C program implements a circular queue using an array. It supports three important operations: enqueue, dequeue and display.

#include <stdio.h>
#include <stdlib.h>

#define SIZE 5

int queue[SIZE];
int front = -1;
int rear = -1;

// Insert an element into the circular queue
void enqueue(int value) {

    if ((rear + 1) % SIZE == front) {
        printf("Queue Overflow\n");
        return;
    }

    if (front == -1) {
        front = 0;
    }

    rear = (rear + 1) % SIZE;
    queue[rear] = value;

    printf("%d inserted successfully\n", value);
}

// Delete an element from the circular queue
void dequeue() {

    if (front == -1) {
        printf("Queue Underflow\n");
        return;
    }

    printf("Deleted element: %d\n", queue[front]);

    if (front == rear) {
        front = -1;
        rear = -1;
    } else {
        front = (front + 1) % SIZE;
    }
}

// Display all queue elements
void display() {

    if (front == -1) {
        printf("Queue is Empty\n");
        return;
    }

    int i = front;

    printf("Queue elements: ");

    while (1) {
        printf("%d ", queue[i]);

        if (i == rear) {
            break;
        }

        i = (i + 1) % SIZE;
    }

    printf("\n");
}

// Main function
int main() {

    int choice, value;

    while (1) {

        printf("\n1. Enqueue");
        printf("\n2. Dequeue");
        printf("\n3. Display");
        printf("\n4. Exit");

        printf("\nEnter your choice: ");
        scanf("%d", &choice);

        switch (choice) {

            case 1:
                printf("Enter value: ");
                scanf("%d", &value);
                enqueue(value);
                break;

            case 2:
                dequeue();
                break;

            case 3:
                display();
                break;

            case 4:
                exit(0);

            default:
                printf("Invalid choice\n");
        }
    }

    return 0;
}

Output of Circular Queue Program in C

  1. Enqueue
  2. Dequeue
  3. Display
  4. Exit
    Enter your choice: 1
    Enter value: 10
    10 inserted successfully

Enter your choice: 1
Enter value: 20
20 inserted successfully

Enter your choice: 1
Enter value: 30
30 inserted successfully

Enter your choice: 3
Queue elements: 10 20 30

Enter your choice: 2
Deleted element: 10

Enter your choice: 3
Queue elements: 20 30

Enter your choice: 1
Enter value: 40
40 inserted successfully

Enter your choice: 3
Queue elements: 20 30 40

Dry Run of a Circular Queue

Consider a circular queue with a maximum capacity of 5.

Perform the following operations:

  1. Enqueue(10)
  2. Enqueue(20)
  3. Enqueue(30)
  4. Dequeue()
  5. Enqueue(40)
  6. Enqueue(50)
  7. Enqueue(60)

The queue changes as follows:

OperationFrontRearQueue elements
Initial-1-1Empty
Enqueue(10)0010
Enqueue(20)0110, 20
Enqueue(30)0210, 20, 30
Dequeue()1220, 30
Enqueue(40)1320, 30, 40
Enqueue(50)1420, 30, 40, 50
Enqueue(60)1020, 30, 40, 50, 60

Notice that after inserting 60, the rear pointer moves from index 4 to index 0.

This demonstrates how a circular queue reuses the empty position created by the dequeue operation.

Time and Space Complexity of a Circular Queue

The circular queue implementation using an array has efficient insertion and deletion operations.

OperationTime ComplexityExplanation
EnqueueO(1)Inserts an element at the rear
DequeueO(1)Removes an element from the front
Peek/FrontO(1)Accesses the front element
DisplayO(n)Traverses all queue elements

Space Complexity: O(n)

The queue uses an array of size n, so the total space required is proportional to the capacity of the queue.