Articles / DSA · Part 18

Circular Queues, Deques, and Priority Queues

Explore Circular Queues, Deques, and Priority Queues. Understand how they work, their operations, differences, and practical C implementations with simple examples.

Circular Queues, Deques, and Priority Queues

In the previous article, we learned how a Queue works and how it follows the FIFO (First In, First Out) principle.

However, a simple Queue has some limitations, and not every situation requires elements to be processed strictly in their arrival order.

Let’s explore three variations:

  1. Circular Queue
  2. Deque (Double-Ended Queue)
  3. Priority Queue

1. Circular Queue

In a simple array-based Queue, once the rear reaches the last position of the array, no more elements can be inserted.

This can happen even when some positions at the beginning of the array are empty.

Example:

Consider an array with a capacity of 5:

[10] [20] [30] [40] [50]

Now, remove two elements using Dequeue.

[  ] [  ] [30] [40] [50]
                  ↑
                 REAR

The first two positions are empty, but we cannot insert new elements because rear has already reached the end.

This wastes available space.

How Does a Circular Queue Solve This?

A Circular Queue connects the last position of an array back to the first position.

Think of it as a circle: after reaching the last position, we can move back to the beginning if space is available.

<AsyncImage query=”circular queue data structure array ring diagram front rear arrows blue white clean educational diagram” aspectRatio=”16:9″ width=”100%”/>

For example, after removing 10 and 20, we can insert 60 and 70 into the empty positions.

[60] [70] [30] [40] [50]

The Queue still follows FIFO. Only the way we reuse array positions has changed.

How Does It Work?

A Circular Queue uses two variables:

  • front: Tracks the first element.
  • rear: Tracks the last element.

To move to the next position, we use:

(rear + 1) % SIZE

The % operator gives the remainder after division.

For example, if the array size is 5 and rear is at index 4:

(4 + 1) % 5 = 0

So, the next position becomes index 0.

This is called <abbr title=”A method of wrapping an index back to the beginning when it reaches the end of an array.”>circular movement</abbr>.

C Implementation of Circular Queue

We’ll use a count variable to keep track of how many elements are currently stored. This allows us to use all array positions.

#include <stdio.h>

#define SIZE 5

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

void enqueue(int value) {
    if (count == SIZE) {
        printf("Queue is full\n");
        return;
    }

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

void dequeue() {
    if (count == 0) {
        printf("Queue is empty\n");
        return;
    }

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

    front = (front + 1) % SIZE;
    count--;
}

void display() {
    if (count == 0) {
        printf("Queue is empty\n");
        return;
    }

    for (int i = 0; i < count; i++) {
        printf("%d ", queue[(front + i) % SIZE]);
    }

    printf("\n");
}

int main() {
    enqueue(10);
    enqueue(20);
    enqueue(30);
    enqueue(40);
    enqueue(50);

    display();

    dequeue();
    dequeue();

    enqueue(60);
    enqueue(70);

    display();

    return 0;
}

Output:

10 20 30 40 50
Removed: 10
Removed: 20
30 40 50 60 70

Notice that after removing two elements, the Queue reused the empty positions at the beginning of the array.

This is the main advantage of a Circular Queue.

2. Deque (Double-Ended Queue)

A normal Queue allows insertion at the rear and deletion at the front.

But what if we want to insert or remove elements from both ends?

This is where a Deque comes in.

A Deque (pronounced “deck”) is a Double-Ended Queue that allows insertion and deletion at both the front and rear.

<AsyncImage query=”double ended queue deque data structure diagram insertion deletion arrows both front rear blue white educational illustration” aspectRatio=”16:9″ width=”100%”/>

Basic Operations

A Deque supports four main operations:

Operation Purpose
Insert Front Adds an element at the front
Insert Rear Adds an element at the rear
Delete Front Removes an element from the front
Delete Rear Removes an element from the rear

Example:

Initially:

[10] [20] [30]

Insert 5 at the front:

[5] [10] [20] [30]

Insert 40 at the rear:

[5] [10] [20] [30] [40]

Now, delete an element from the rear:

[5] [10] [20] [30]

We can perform these operations at either end.

Types of Deque

There are two restricted variations:

1. Input-Restricted Deque

Insertion is allowed only at the rear, but deletion is allowed at both ends.

2. Output-Restricted Deque

Insertion is allowed at both ends, but deletion is allowed only at the front.

These restrictions create different ways of managing elements.

Applications of Deques

  • Palindrome Checking: We can compare characters from both ends to check whether a word reads the same forward and backward.
  • Sliding Window Problems: Deques help efficiently maintain elements within a moving range of an array.
  • Task Management: Elements can be added or removed from either end depending on the requirements.

3. Priority Queue

In a normal Queue, elements are processed in the order they arrive.

But consider an emergency room in a hospital.

A patient with a serious condition may need immediate attention, even if other patients arrived earlier.

A Priority Queue handles such situations.

A Priority Queue is a data structure in which each element is assigned a priority, and elements are processed according to their priority rather than simply their arrival order.

<AsyncImage query=”priority queue data structure diagram three patients different priority levels emergency high medium low blue white educational illustration” aspectRatio=”16:9″ width=”100%”/>

How Does It Work?

Suppose three tasks arrive in this order:

Task Priority
Task A 3
Task B 1
Task C 2

Assume that a smaller priority number represents a higher priority, where 1 is the highest.

Although Task A arrived first, Task B will be processed first because it has the highest priority.

The processing order becomes:

Task B → Task C → Task A

Important: If two elements have the same priority, they can be processed in their arrival order when the implementation follows a FIFO rule for equal priorities.

Basic Operations

Operation Purpose
Insert Adds an element with a priority
Delete Removes the element with the highest priority
Peek Displays the highest-priority element

C Implementation Using an Array

For simplicity, let’s implement a Priority Queue using an array.

We’ll use a structure to store each value along with its priority.

#include <stdio.h>

struct Item {
    int value;
    int priority;
};

struct Item queue[5];
int size = 0;

void insert(int value, int priority) {
    if (size == 5) {
        printf("Queue is full\n");
        return;
    }

    int i = size;

    while (i > 0 &&
           queue[i - 1].priority > priority) {
        queue[i] = queue[i - 1];
        i--;
    }

    queue[i].value = value;
    queue[i].priority = priority;

    size++;
}

void delete() {
    if (size == 0) {
        printf("Queue is empty\n");
        return;
    }

    printf("Removed: %d\n", queue[0].value);

    for (int i = 0; i < size - 1; i++) {
        queue[i] = queue[i + 1];
    }

    size--;
}

void display() {
    for (int i = 0; i < size; i++) {
        printf("Value: %d, Priority: %d\n",
               queue[i].value,
               queue[i].priority);
    }
}

int main() {
    insert(100, 3);
    insert(200, 1);
    insert(300, 2);

    display();

    delete();

    return 0;
}

Output:

Value: 200, Priority: 1
Value: 300, Priority: 2
Value: 100, Priority: 3

Removed: 200

The elements are stored according to their priority, so the highest-priority element is always at the beginning.

This is a simple implementation. More efficient Priority Queues are commonly implemented using a Heap, which we’ll study in a later article.

4. Comparison of Queue Variations

Feature Circular Queue Deque Priority Queue
Main idea Reuses empty array positions Works at both ends Processes by priority
Insertion Rear Front or Rear According to implementation
Deletion Front Front or Rear Highest priority
Processing order FIFO Depends on operations Priority-based
Common application Buffer management Sliding window problems Task scheduling

We explored three variations of the basic Queue:

  • Circular Queue: Reuses empty positions by connecting the end of an array to its beginning.
  • Deque: Allows insertion and deletion from both ends.
  • Priority Queue: Processes elements according to their assigned priority.

Each variation solves a different problem while building on the basic idea of managing elements in an organized way.

In the next article, we’ll explore Heaps: Representation and Implementation of Priority Queues, where we’ll learn how heaps make priority-based operations more efficient.


Further reading: GeeksforGeeks – Circular Queue · GeeksforGeeks – Deque · GeeksforGeeks – Priority Queue

Keep a copy

Read offline as a printout or PDF.

farhanpaal.com

Keep reading

DSA · Part 11

Linear Search vs. Binary Search

Learn how Linear Search and Binary Search work, compare their efficiency, and understand when to use each method with simple examples and…

4 min read

Ask Farhan

Ask anything about Farhan