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 | 0 | 1 | 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 | 0 | 1 | 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 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| Array | 10 | 30 | |||
| front | ↑ | ||||
| rear | ↑ |
front = 2
rear = 4
Enqueue 80:
| Index | 0 | 1 | 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
|
Top comments (0)