Understanding Queue Implementation Using Arrays and Circular Arrays

Kawsar Ahmed Bhuiyan — Mon, 02 Jun 2025 03:32:23 +0000

Introduction

A queue is a data structure that works like a line of people — the first to come in is the first to get served. It follows the FIFO principle: First-In, First-Out.

Implementing queues using arrays is straightforward, but it comes with some challenges. Here we will explain step-by-step why certain techniques are used, especially why circular arrays are helpful. We will also go over the common “full vs empty” confusion and the "n-1 vs n slots" issue by showing two different circular-array based queue implementations.

Part 1: Queue Using Linear Arrays

Imagine a simple array of size 5:

Index	0	1	2	3	4
Array

We can use this array to represent a Queue. We will use two pointers:

front — indicates the position from which we should remove an element. [Dequeue]
rear — indicates the position where we should insert an element. [Enqueue]

Example:

Initial state:

Index	0	1	2	3	4
Array
front	↑
rear	↑

front = 0
rear = 0

Enqueue 40, 20, 10, 30:

Index	0	1	2	3	4
Array	40	20	10	30
front	↑
rear					↑

front = 0
rear = 4

In a queue, we are allowed to insert (enqueue) elements only at the rear. So, each time we enqueue an element, we move the rear pointer forward to indicate where the next element should be inserted.

As a result, after enqueuing 40, the value of rear becomes 1; after enqueuing 20, it becomes 2; after enqueuing 10, it becomes 3; and after enqueuing 30, it becomes 4.

Dequeue twice so that 40 and 20 gets removed from the queue:

Index	2	3	4
Array	10	30
front	↑
rear			↑

front = 2
rear = 4

In a queue, we are allowed to remove (dequeue) elements only from the front. So, each time we dequeue an element, we move the front pointer forward to indicate where the next element should be removed from.

As a result, after dequeuing 40, the value of front becomes 1; and after dequeuing 20, it becomes 2.

Now, let's try to enqueue 80 and 60.

After enqueuing 80:

Index	2	3	4
Array	10	30	80
front	↑
rear

front = 2
rear = 5

After enqueing 80, the value of rear becomes 4 + 1 = 5. So, we can't enqueue any more element as there is no 5th index in a 5-sized array.
Even though space at the beginning is free we can't use it because we can only insert at the index indicated by rear. This leads to wasted space.

Part 2: Queue Using Circular Arrays

To avoid wasted space, we can treat the array as circular.

When rear or front reach the end (n-1), they will wrap around to 0.

We use the modulo operator % for this:

rear = (rear + 1) % n
front = (front + 1) % n

Why modulo?

Because array indices must stay between 0 and n-1. Using modulo lets the pointers wrap around naturally.

Using the same example:

Index	2	3	4
Array	10	30
front	↑
rear			↑

front = 2
rear = 4

Enqueue 80:

Index	0	2	3	4
Array		10	30	80
front		↑
rear	↑

front = 2
rear = 0

After enqueing 80, the value of rear becomes (4 + 1) % 5 = 0. Here, rear wrapped from 4 back to 0.

So, we can easily enqueue 60 at the 0th index represented by rear:

Index	0	1	2	3	4
Array	60		10	30	80
front			↑
rear		↑

front = 2
rear = 1

After enqueing 60, the value of rear becomes (0 + 1) % 5 = 1.

We can even enqueue one more element, let's say 70:

Index	0	1	2	3	4
Array	60	70	10	30	80
front			↑
rear			↑

front = 2
rear = 2

After enqueing 70, the value of rear becomes (1 + 1) % 5 = 2.

Now, the queue is full. So, we can not enqueue any more element without dequeing at least one element.

Therefore, we can say that if front == rear, it indicates the queue is full.

But there is a problem. Recall that when the queue was empty, both front and rear had the value of 0.
So, even when the queue was emtpy front == rear was true. This leads to the ambiguity. We can not use front == rear condition to indicate both an empty queue and a full queue.

So, what is the solution?

We can assume that the queue (circular array) is full when there is one empty slot left in the queue:

Index	0	1	2	3	4
Array	60		10	30	80
front			↑
rear		↑

front = 2
rear = 1

In other words, we use the following test to check if the queue is full:

( rear + 1 ) % n == front

So, in this case, as (rear + 1 ) % n = (1 + 1) % 5 = 2 and front = 2, we will consider this queue to be full and will not try to enqueue any more element as long as we do not dequeue at least one element.

We got rid of the ambiguity but in doing so, we had to waste one slot.

Part 3: Why Keep One Slot Empty?

If we want to use all n slots, we can track the number of elements of the queue with a size variable.
Each time we enqueue an element, apart from moving the rear pointer forward, we will also increase the value of size by 1 and each time we dequeue an element, apart from moving the front pointer forward, we will also decrease the value of size by 1.

[We will still use rear = (rear + 1) % n and front = (front + 1) % n to increment rear and front.]

To check if the queue is empty we will check if size == 0 and to check if the queue is full, we will check if size == n.

Using this implementation, we can use all n slots of the array.

Using the same example that we have discussed so far:

Initial state:

Index	0	1	2	3	4
Array
front	↑
rear	↑

front = 0
rear = 0
size = 0

Then if we

Enqueue 40, 20, 10, 30.
Dequeue twice so that 40 and 20 gets removed from the queue.
Enqueue 80 and 60.

the value of size will change from 0 to 4 to 2 to 4.

Index	0	1	2	3	4
Array	60		10	30	80
front			↑
rear		↑

front = 2
rear = 1
size = 4

And as size != n, we will still be able to enqueue 70 to the 1st index:

Index	0	1	2	3	4
Array	60	70	10	30	80
front			↑
rear			↑

front = 2
rear = 2
size = 5

And finally, at this point, as size == n, we will consider this queue to be full and will not try to enqueue any more element as long as we do not dequeue at least one element.

So, in this implementation, using only an extra variable we can use all all n slots of the array.

Summary of Difference Between the Two Circular Array Based Queue Implementations

	First Implementation (One Slot Empty)	Second Implementation (Tracking Size To Use Full Capacity)
Max Elements	`n - 1`	`n`
Full Condition	`(rear + 1) % n == front`	`size == n`
Empty Condition	`front == rear`	`size == 0`
Operations After Enqueue	`rear = (rear + 1) % n`	`rear = (rear + 1) % n` and `size = size + 1`
Operations After Dequeue	`front = (front + 1) % n`	`front = (front + 1) % n` and `size = size - 1`

DEV Community: Kawsar Ahmed Bhuiyan