Queue Implementation Using Array in C++: Linear & Circular Queue Guide

In Step 1: Understanding Queue in C++, we learned how std::queue manages FIFO operations behind the scenes. Now it is time to open the hood and build a Queue from scratch using a fixed-size C++ array.

Part of the Queue Series: This article is Step 2 of our Queue in C++: Complete Beginner-to-Advanced Guide.

1. How an Array-Based Queue Works

When we implemented a Stack using an array, we only needed one index variable (topIndex) because both insertions and removals happened at the exact same end.

A Queue, however, inserts elements at the Rear and removes elements from the Front. To build a Queue on top of a fixed-size array arr[MAX_SIZE], our class needs two integer index trackers:

1. frontIndex: Stores the array index of the oldest element currently at the front of the line (where dequeue happens).
2. rearIndex: Stores the array index of the newest element most recently added at the back of the line (where enqueue happens).

const int MAX_SIZE = 5;

class Queue {
private:
    int arr[MAX_SIZE]; // Fixed-size storage array
    int frontIndex;    // Index of the front (oldest) element
    int rearIndex;     // Index of the rear (newest) element
};

Here is what an array-based Queue looks like when three elements (10, 20, 30) are inside:

Array Indices:     [0]     [1]     [2]     [3]     [4]
                 +-----+ +-----+ +-----+ +-----+ +-----+
Array Values:    |  10 | |  20 | |  30 | |     | |     |
                 +-----+ +-----+ +-----+ +-----+ +-----+
                    ^               ^
               frontIndex = 0  rearIndex = 2
               (Next to exit)  (Last inserted)

2. Initializing an Empty Queue (front = -1, rear = -1)

When a new Queue object is created, its constructor sets both frontIndex and rearIndex to -1:

Queue() {
    frontIndex = -1;
    rearIndex = -1;
}

Why -1 Instead of 0?

In C++, 0 is a valid array index (arr[0]). If we initialized frontIndex = 0 and rearIndex = 0, it would look like there is already 1 valid element sitting at arr[0]!

Setting both frontIndex = -1 and rearIndex = -1 provides an unmistakable signal that zero elements are currently in the Queue:

Empty Queue State (frontIndex = -1, rearIndex = -1):

   (-1)         [0]     [1]     [2]     [3]     [4]
    ^         +-----+ +-----+ +-----+ +-----+ +-----+
frontIndex &  |     | |     | |     | |     | |     |
 rearIndex    +-----+ +-----+ +-----+ +-----+ +-----+
 (Outside)

3. Enqueue Operation (Inserting at the Rear)

Adding a new element (enqueue) always happens at the Rear of the queue. However, we must handle two cases carefully:

1. Inserting into an Empty Queue (frontIndex == -1): Since this is the very first element entering the queue, it becomes both the front and the rear! So we must set frontIndex = 0 in addition to advancing rearIndex to 0.
2. Inserting into a Non-Empty Queue: frontIndex stays where it is, and we simply increment rearIndex++ and store the new value at arr[rearIndex].

// Insert an element at the rear of the queue
void enqueue(int value) {
    // 1. Check for Queue Overflow
    if (isFull()) {
        cout << "Queue Overflow! Cannot enqueue " << value << "." << endl;
        return;
    }

    // 2. If queue was empty, move frontIndex to 0
    if (frontIndex == -1) {
        frontIndex = 0;
    }

    // 3. Advance rearIndex and insert the new element
    rearIndex++;
    arr[rearIndex] = value;
    cout << value << " enqueued at index " << rearIndex << "." << endl;
}

Visual Trace of enqueue(10), enqueue(20), and enqueue(30)

1. Initial Empty Queue:
   frontIndex = -1, rearIndex = -1
   Index:    [0]   [1]   [2]   [3]   [4]
           +-----+-----+-----+-----+-----+
   arr:    |     |     |     |     |     |
           +-----+-----+-----+-----+-----+

2. After enqueue(10) -> First element sets frontIndex = 0, rearIndex = 0:
   Index:    [0]   [1]   [2]   [3]   [4]
           +-----+-----+-----+-----+-----+
   arr:    |  10 |     |     |     |     |
           +-----+-----+-----+-----+-----+
              ^
        frontIndex = 0
         rearIndex = 0

3. After enqueue(20) -> rearIndex++ becomes 1:
   Index:    [0]   [1]   [2]   [3]   [4]
           +-----+-----+-----+-----+-----+
   arr:    |  10 |  20 |     |     |     |
           +-----+-----+-----+-----+-----+
              ^     ^
          front=0 rear=1

4. After enqueue(30) -> rearIndex++ becomes 2:
   Index:    [0]   [1]   [2]   [3]   [4]
           +-----+-----+-----+-----+-----+
   arr:    |  10 |  20 |  30 |     |     |
           +-----+-----+-----+-----+-----+
              ^           ^
          front=0       rear=2

4. Dequeue Operation (Removing from the Front)

Removing an element (dequeue) always happens at the Front of the queue. Instead of shifting every remaining element one slot to the left (which would waste $O(n)$ time), we simply move frontIndex one step to the right (frontIndex++) in $O(1)$ time!

There is one critical edge case to watch for:

• What if we are removing the last remaining element in the Queue (frontIndex == rearIndex)? When only one element is left, frontIndex and rearIndex point to the exact same slot. Once that last element is removed, the Queue is completely empty again—so we reset both frontIndex = -1 and rearIndex = -1.

// Remove the front element from the queue
void dequeue() {
    // 1. Check for Queue Underflow
    if (isEmpty()) {
        cout << "Queue Underflow! Cannot dequeue from an empty queue." << endl;
        return;
    }

    int removedValue = arr[frontIndex];
    cout << removedValue << " dequeued from index " << frontIndex << "." << endl;

    // 2. If this was the only element left, reset queue to empty state
    if (frontIndex == rearIndex) {
        frontIndex = -1;
        rearIndex = -1;
    }
    // 3. Otherwise, advance frontIndex to the next element in line
    else {
        frontIndex++;
    }
}

Visual Trace of dequeue()

Before dequeue() (frontIndex = 0, rearIndex = 2):
   Index:    [0]   [1]   [2]   [3]   [4]
           +-----+-----+-----+-----+-----+
   arr:    |  10 |  20 |  30 |     |     |
           +-----+-----+-----+-----+-----+
              ^           ^
          front=0       rear=2

After 1st dequeue() -> 10 leaves; frontIndex++ becomes 1:
   Index:    [0]   [1]   [2]   [3]   [4]
           +-----+-----+-----+-----+-----+
   arr:    | (10)|  20 |  30 |     |     |
           +-----+-----+-----+-----+-----+
                    ^     ^
                front=1 rear=2
   (Slot [0] is now outside the active queue boundary)

After 2nd dequeue() -> 20 leaves; frontIndex++ becomes 2:
   Index:    [0]   [1]   [2]   [3]   [4]
           +-----+-----+-----+-----+-----+
   arr:    | (10)| (20)|  30 |     |     |
           +-----+-----+-----+-----+-----+
                          ^
                      front = 2
                       rear = 2 (Only 1 element left!)

After 3rd dequeue() -> 30 leaves; since front == rear, reset both to -1:
   frontIndex = -1, rearIndex = -1 (Queue is completely empty again)

5. Queue Overflow, Queue Underflow, and Boundary Helpers

To keep our array-based Queue safe from out-of-bounds memory access, we implement six clean helper functions:

1. isEmpty() (Queue Underflow Check)

bool isEmpty() {
    return frontIndex == -1;
}

Whenever frontIndex == -1, the queue holds zero elements. Calling dequeue(), front(), or rear() when isEmpty() is true triggers Queue Underflow.

2. isFull() (Queue Overflow Check)

bool isFull() {
    return rearIndex == MAX_SIZE - 1;
}

In a simple linear array Queue, once rearIndex reaches the final array index (MAX_SIZE - 1), no more elements can be appended to the right. Calling enqueue() when isFull() is true triggers Queue Overflow.

3. front(), rear(), and size()

int front() {
    if (isEmpty()) {
        cout << "Queue is empty! No front element." << endl;
        return -1;
    }
    return arr[frontIndex];
}

int rear() {
    if (isEmpty()) {
        cout << "Queue is empty! No rear element." << endl;
        return -1;
    }
    return arr[rearIndex];
}

int size() {
    if (isEmpty()) {
        return 0;
    }
    return rearIndex - frontIndex + 1;
}

Look at the formula inside size(): because active elements sit contiguously from frontIndex to rearIndex inclusive, the number of elements in the queue is always rearIndex - frontIndex + 1! (For example, if frontIndex = 1 and rearIndex = 3, active indices are 1, 2, 3, and 3 - 1 + 1 = 3 elements.)

6. Complete C++ Code: Linear Array Queue

Here is the complete, compilable C++ implementation of a Queue class using a fixed-size array:

#include <iostream>

using namespace std;

const int MAX_SIZE = 5;

class Queue {
private:
    int arr[MAX_SIZE];
    int frontIndex;
    int rearIndex;

public:
    // Constructor: initialize an empty queue
    Queue() {
        frontIndex = -1;
        rearIndex = -1;
    }

    // Check if the queue is empty
    bool isEmpty() {
        return frontIndex == -1;
    }

    // Check if the linear queue has reached the end of the array
    bool isFull() {
        return rearIndex == MAX_SIZE - 1;
    }

    // Insert an element at the rear
    void enqueue(int value) {
        if (isFull()) {
            cout << "Queue Overflow! Cannot enqueue " << value << "." << endl;
            return;
        }
        if (frontIndex == -1) {
            frontIndex = 0;
        }
        rearIndex++;
        arr[rearIndex] = value;
        cout << value << " enqueued at index " << rearIndex << "." << endl;
    }

    // Remove the oldest element from the front
    void dequeue() {
        if (isEmpty()) {
            cout << "Queue Underflow! Cannot dequeue from an empty queue." << endl;
            return;
        }
        int removedValue = arr[frontIndex];
        cout << removedValue << " dequeued from index " << frontIndex << "." << endl;

        if (frontIndex == rearIndex) {
            // Queue had only 1 element; reset to empty state
            frontIndex = -1;
            rearIndex = -1;
        } else {
            frontIndex++;
        }
    }

    // Read the front element without removing it
    int front() {
        if (isEmpty()) {
            cout << "Queue is empty!" << endl;
            return -1;
        }
        return arr[frontIndex];
    }

    // Read the rear element without removing it
    int rear() {
        if (isEmpty()) {
            cout << "Queue is empty!" << endl;
            return -1;
        }
        return arr[rearIndex];
    }

    // Return the number of active elements in the queue
    int size() {
        if (isEmpty()) {
            return 0;
        }
        return rearIndex - frontIndex + 1;
    }

    // Print all active elements from Front to Rear
    void display() {
        if (isEmpty()) {
            cout << "Queue is empty." << endl;
            return;
        }
        cout << "Queue (Front to Rear): ";
        for (int i = frontIndex; i <= rearIndex; i++) {
            cout << arr[i] << " ";
        }
        cout << endl;
    }
};

int main() {
    Queue q;

    // 1. Enqueue 5 elements to fill the queue
    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);
    q.enqueue(40);
    q.enqueue(50);

    // 2. Test Queue Overflow
    q.enqueue(60);

    cout << "---" << endl;
    q.display();
    cout << "Front element: " << q.front() << endl;
    cout << "Rear element: " << q.rear() << endl;
    cout << "Current size: " << q.size() << endl;

    cout << "---" << endl;

    // 3. Dequeue 2 elements from the front
    q.dequeue();
    q.dequeue();
    q.display();
    cout << "New Front element: " << q.front() << endl;
    cout << "Current size: " << q.size() << endl;

    return 0;
}

Output

10 enqueued at index 0.
20 enqueued at index 1.
30 enqueued at index 2.
40 enqueued at index 3.
50 enqueued at index 4.
Queue Overflow! Cannot enqueue 60.
---
Queue (Front to Rear): 10 20 30 40 50
Front element: 10
Rear element: 50
Current size: 5
---
10 dequeued from index 0.
20 dequeued from index 1.
Queue (Front to Rear): 30 40 50
New Front element: 30
Current size: 3

7. Complete Step-by-Step Dry Run

Let’s trace a sequence of operations on a linear array Queue with MAX_SIZE = 3:

8. The Limitation of a Simple Linear Queue (“False Overflow”)

Look closely at Step 5 in the dry run above, or look at what happens in main() after we dequeued 10 and 20:

State after 5 enqueues and 2 dequeues (MAX_SIZE = 5):

   Index:     [0]     [1]     [2]     [3]     [4]
            +-----+ +-----+ +-----+ +-----+ +-----+
   arr:     |Empty| |Empty| |  30 | |  40 | |  50 |
            +-----+ +-----+ +-----+ +-----+ +-----+
              ^^^     ^^^      ^               ^
            Vacated slots!  front=2         rear=4 (MAX_SIZE - 1)

Notice the problem:

• The Queue currently holds only 3 elements (30, 40, 50).
• Slots [0] and [1] are completely unoccupied because 10 and 20 were already dequeued.
• Yet if we try to call q.enqueue(60), isFull() checks rearIndex == MAX_SIZE - 1 (4 == 4) and rejects it with Queue Overflow!

Why? Because in a simple linear Queue, frontIndex and rearIndex only move rightward. Unless the entire queue becomes completely empty (which resets both to -1), the vacated slots to the left of frontIndex can never be reused. This flaw is called False Overflow.

9. Improvement: Circular Queue (Ring Buffer)

How can we reuse those empty slots at the beginning of the array without shifting elements? By connecting the last index (MAX_SIZE - 1) back to index 0 in a circle—creating a Circular Queue!

How Modulo Arithmetic (% MAX_SIZE) Creates a Circle

In a Circular Queue, instead of incrementing indices with rearIndex++, we advance both pointers using the modulo operator (%):

$\text{nextIndex} = (\text{currentIndex} + 1) \bmod \text{MAX\_SIZE}$

Look at what (index + 1) % 5 produces when MAX_SIZE = 5:

• When rearIndex = 0 $\rightarrow$ (0 + 1) % 5 = 1
• When rearIndex = 1 $\rightarrow$ (1 + 1) % 5 = 2
• When rearIndex = 2 $\rightarrow$ (2 + 1) % 5 = 3
• When rearIndex = 3 $\rightarrow$ (3 + 1) % 5 = 4
• When rearIndex = 4 $\rightarrow$ (4 + 1) % 5 = 0 (Wraps right back to index 0!)

Wrapping Around in a Circular Queue (MAX_SIZE = 5):

   enqueue(60) wraps rearIndex from 4 -> (4 + 1) % 5 = 0!
                  +---------------------------------------+
                  v                                       |
   Index:        [0]     [1]     [2]     [3]     [4]      |
               +-----+ +-----+ +-----+ +-----+ +-----+    |
   arr:        |  60 | |Empty| |  30 | |  40 | |  50 | ---+
               +-----+ +-----+ +-----+ +-----+ +-----+
                  ^               ^
               rear=0          front=2
        (Newest element)   (Oldest element)

Complete Circular Queue Class in C++

By maintaining a currentSize counter alongside frontIndex and rearIndex, a Circular Queue becomes remarkably clean to write and eliminates False Overflow completely:

#include <iostream>

using namespace std;

const int MAX_SIZE = 5;

class CircularQueue {
private:
    int arr[MAX_SIZE];
    int frontIndex;
    int rearIndex;
    int currentSize;

public:
    CircularQueue() {
        frontIndex = 0;
        rearIndex = -1;
        currentSize = 0;
    }

    bool isEmpty() {
        return currentSize == 0;
    }

    bool isFull() {
        return currentSize == MAX_SIZE;
    }

    void enqueue(int value) {
        if (isFull()) {
            cout << "Circular Queue Overflow! All " << MAX_SIZE << " slots are in use." << endl;
            return;
        }
        // Wrap rearIndex around using modulo arithmetic
        rearIndex = (rearIndex + 1) % MAX_SIZE;
        arr[rearIndex] = value;
        currentSize++;
        cout << value << " enqueued at index " << rearIndex << "." << endl;
    }

    void dequeue() {
        if (isEmpty()) {
            cout << "Circular Queue Underflow!" << endl;
            return;
        }
        cout << arr[frontIndex] << " dequeued from index " << frontIndex << "." << endl;
        // Wrap frontIndex around using modulo arithmetic
        frontIndex = (frontIndex + 1) % MAX_SIZE;
        currentSize--;
    }

    int front() {
        if (isEmpty()) return -1;
        return arr[frontIndex];
    }

    int rear() {
        if (isEmpty()) return -1;
        return arr[rearIndex];
    }

    void display() {
        if (isEmpty()) {
            cout << "Queue is empty." << endl;
            return;
        }
        cout << "Circular Queue (Front to Rear): ";
        for (int count = 0; count < currentSize; count++) {
            int index = (frontIndex + count) % MAX_SIZE;
            cout << arr[index] << " ";
        }
        cout << endl;
    }
};

int main() {
    CircularQueue cq;

    // Fill all 5 slots (indices 0..4)
    cq.enqueue(10);
    cq.enqueue(20);
    cq.enqueue(30);
    cq.enqueue(40);
    cq.enqueue(50);

    // Free up indices 0 and 1
    cq.dequeue();
    cq.dequeue();

    // Reuse indices 0 and 1 by wrapping around!
    cq.enqueue(60);
    cq.enqueue(70);

    cq.display();
    cout << "Front: " << cq.front() << " | Rear: " << cq.rear() << endl;

    return 0;
}

Output

10 enqueued at index 0.
20 enqueued at index 1.
30 enqueued at index 2.
40 enqueued at index 3.
50 enqueued at index 4.
10 dequeued from index 0.
20 dequeued from index 1.
60 enqueued at index 0.
70 enqueued at index 1.
Circular Queue (Front to Rear): 30 40 50 60 70
Front: 30 | Rear: 70

10. Time and Space Complexity

Both the Linear Array Queue and the Circular Array Queue perform all core operations in $O(1)$ constant time:

• Space Complexity: $O(\text{MAX\_SIZE})$, as the fixed array reserves MAX_SIZE contiguous integer slots up front.

Summary

• An array-based Queue tracks two indices: frontIndex (oldest element) and rearIndex (newest element), both initialized to -1.
• enqueue(x) inserts at rearIndex; if the queue was empty (frontIndex == -1), it also sets frontIndex = 0.
• dequeue() removes from frontIndex by advancing frontIndex++; if frontIndex == rearIndex, it resets both to -1.
• A simple linear Queue suffers from False Overflow when rearIndex hits MAX_SIZE - 1 even if earlier slots were vacated.
• A Circular Queue uses modulo arithmetic (index + 1) % MAX_SIZE to wrap around and reuse every vacated array slot.

Continue Learning in the Queue Series

What if you don’t know the maximum number of elements ahead of time and want to use a dynamic C++ std::vector? In Step 3, we will build a Queue using std::vector and uncover a crucial performance trap with vector.erase()!

• Topic Hub: Queue in C++: Complete Beginner-to-Advanced Guide
• Previous Article (Step 1): Understanding Queue in C++: Complete Beginner’s Guide
• Next Article (Step 3): Queue Implementation Using Vector in C++
• Step 4: Queue Implementation Using Linked List in C++
• Step 5: Most Famous Queue Problems in Competitive Programming
• Step 6: Queue vs Stack in C++: Complete Comparison