Implement Queue Using Arrays in C++ | Complete Guide with Code, Dry Run & Complexity (Interview Ready)

1. Problem Statement

At its core, this problem asks us to design a data structure that mimics a real-world queue (like a line of people waiting for a movie) using a standard array.

What is a Queue? A queue is a linear data structure that follows the FIFO principle.

What does FIFO mean? FIFO stands for First In, First Out. The first element you put into the queue is the very first one you take out. Imagine a checkout line at a grocery store: the first person to get in line is the first person to be served.

Input A series of operations:

push(x) (or enqueue): Insert an element x at the back of the queue.
pop() (or dequeue): Remove the element from the front of the queue.
front() (or peek): Look at the element at the front without removing it.

Output

push(x) returns nothing.
pop() returns the removed element.
front() returns the front element.

Constraints & Conditions

Maximum capacity: The queue will have a predefined fixed capacity (e.g., $N$ ).
Duplicates & Negatives: Allowed.
Queue Overflow: Occurs when you try to push an element but the queue is full.
Queue Underflow: Occurs when you try to pop or get the front element, but the queue is completely empty.
Expected Time Complexity: Every single operation must run in $O(1)$ (constant) time.

Small Example Assume Capacity = 5.

push(10)
push(20)
push(30)
front()
pop()
front()

Output:101020

Why is this output correct?

We push 10, then 20, then 30. The queue from front to back is [10, 20, 30].
front() looks at the earliest inserted element. It outputs 10.
pop() removes and returns the earliest element. It outputs 10. The queue is now [20, 30].
The next front() looks at the new front element, outputting 20.

2. Intuition

If we try to implement a queue just like a stack, we run into a major issue. Suppose we add elements at the end and remove them from the front

The Naive Linear Array Approach & Why It Fails

Suppose we use an array of size 5, and track elements using two pointers: front = 0 and rear = -1.

When we enqueue, we increment rear and insert.
When we dequeue, we can either:
1. Shift all remaining elements left by 1 index: This takes $O(N)$ time per dequeue, violating our $O(1)$ constraint.
2. Increment the front pointer instead of shifting: This is $O(1)$ , but causes false overflow / memory waste.

Index:    0    1    2    3    4
Array:  [ X ][ X ][ X ][   ][   ]

If we remove the first two elements, the array looks like this:

Index:    0    1    2    3    4
Array:  [ _ ][ _ ][ X ][   ][   ]

We have empty spaces at indices 0 and 1, but our "rear" of the queue is moving towards index 4. Eventually, we will hit the end of the array and trigger an "Overflow", even though there is perfectly good empty space at the beginning of the array.

The Solution: The Circular Array To fix this, we imagine the array is a circle. When the rear reaches the end of the array, it wraps around back to index 0. We achieve this using the modulo operator (%).

We need four variables:

arr: The array itself.
front: Points to the index of the first element. Initializes to 0.
rear: Points to the index of the last element. Initializes to -1.
currentSize: Tracks the actual number of elements in the queue. Initializes to 0.

3. Key Observations

The array stores queue elements linearly, but logically it acts as a circle.
currentSize is the source of truth for checking if the queue is empty (currentSize == 0) or full (currentSize == capacity). This saves us from complex pointer math.
rear moves forward on Push: Insert at (rear + 1) % capacity.
front moves forward on Pop: Remove at front, then update to (front + 1) % capacity.
The modulo operator % prevents out-of-bounds errors and seamlessly loops pointers back to 0.

These observations naturally lead to the circular array implementation because arrays provide $O(1)$ access, and math (modulo) provides $O(1)$ index wrapping.

4. Algorithm

Push(x)

Check for overflow: If currentSize == capacity, return an error.
Increment rear circularly: rear = (rear + 1) % capacity.
Store the value: arr[rear] = x.
Increment currentSize: currentSize = currentSize + 1.

Pop()

Check for underflow: If currentSize == 0, return an error.
Retrieve the value: Store arr[front] in a temporary variable.
Increment front circularly: front = (front + 1) % capacity.
Decrement currentSize: currentSize = currentSize - 1.
Return the temporary variable.

Front()

Check for underflow.
Return arr[front].

isEmpty()

Return currentSize == 0.

isFull()

Return currentSize == capacity.

5. Complete Dry Run

Let's simulate with Capacity = 3. Initial State: front = 0, rear = -1, currentSize = 0. Array: [_, _, _]

1. push(10)

rear = (-1 + 1) % 3 = 0. arr[0] = 10. currentSize = 1.
Array: [10, _, _]

2. push(20)

rear = (0 + 1) % 3 = 1. arr[1] = 20. currentSize = 2.
Array: [10, 20, _]

3. push(30)

rear = (1 + 1) % 3 = 2. arr[2] = 30. currentSize = 3.
Array: [10, 20, 30] (Queue is now full)

4. pop()

Read arr[front] -> arr[0] (10).
front = (0 + 1) % 3 = 1. currentSize = 2.
Returned: 10. Array logically: [_, 20, 30].

5. push(40) (The Wrap Around)

rear = (2 + 1) % 3 = 0. (It wraps around!)
arr[0] = 40. currentSize = 3.
Array physically: [40, 20, 30]. Array logically (from front to rear): 20 -> 30 -> 40.

6. pop()

Read arr[front] -> arr[1] (20).
front = (1 + 1) % 3 = 2. currentSize = 2.
Returned: 20. Array logically: [40, _, 30].

C++ Implementation

#include <iostream>
using namespace std;

class Queue {
private:
    int* arr;           // Pointer to dynamic array
    int capacity;       // Maximum size of the queue
    int frontIndex;     // Index of the front element
    int rearIndex;      // Index of the rear element
    int currentSize;    // Current number of elements in the queue

public:
    // Constructor to initialize the queue
    Queue(int size) {
        capacity = size;
        arr = new int[capacity];
        frontIndex = 0;
        rearIndex = -1;
        currentSize = 0;
    }

    // Destructor to free memory
    ~Queue() {
        delete[] arr;
    }

    // Push (Enqueue) operation
    void push(int x) {
        if (currentSize == capacity) {
            cout << "Queue Overflow!" << endl;
            return;
        }
        // Move rear circularly using modulo
        rearIndex = (rearIndex + 1) % capacity;
        arr[rearIndex] = x;
        currentSize++;
    }

    // Pop (Dequeue) operation
    int pop() {
        if (currentSize == 0) {
            cout << "Queue Underflow!" << endl;
            return -1; // Returning -1 as an error indicator
        }
        int poppedValue = arr[frontIndex];
        // Move front circularly using modulo
        frontIndex = (frontIndex + 1) % capacity;
        currentSize--;
        return poppedValue;
    }

    // Front (Peek) operation
    int front() {
        if (currentSize == 0) {
            cout << "Queue is Empty!" << endl;
            return -1;
        }
        return arr[frontIndex];
    }

    // Check if queue is empty
    bool isEmpty() {
        return currentSize == 0;
    }
};

6. Correctness Proof

Why does this circular array perfectly emulate a queue?

FIFO is maintained: Elements are always read from front and added at rear. Because front and rear only ever move in one direction (clockwise around the array), the oldest element is always exactly where front is pointing.
No memory is wasted: The modulo operator ensures that as long as currentSize < capacity, any physical empty space in the array will eventually be reached by rear.
Pointers never overlap invalidly: By strictly enforcing currentSize == capacity before pushes, rear can never overwrite front.

7. Complexity Analysis

Time Complexity: $O(1)$ for every single operation (push, pop, front, isEmpty). Mathematical operations (addition and modulo) and array access take constant time.
Space Complexity: $O(N)$ where $N$ is the maximum capacity, as we allocate a fixed-size array upfront. No extra memory is consumed per operation.

8. Edge Cases

Continuous push and pop: If you push one element, pop it, push another, pop it, over and over, front and rear will cycle through the array indefinitely without memory leaks.
Queue Overflow/Underflow: Safely caught by checking currentSize.
Capacity = 1: The modulo math works perfectly. front and rear will constantly sit at index 0.

9. Common Interview Mistakes

Forgetting the modulo operator: Doing rear++ without modulo will cause a segmentation fault / index out-of-bounds error as soon as the queue reaches the end of the physical array.
Shifting elements on Pop: Some candidates try to simulate a queue by moving all elements to the left by one space every time they pop. This makes pop an $O(N)$ operation instead of $O(1)$ and will fail the interview.
Relying only on pointers for full/empty checks: It is mathematically possible to check if a circular queue is full using only front and rear (e.g., (rear + 1) % capacity == front), but it requires creating a "dummy" space or complex logic. Using a currentSize variable is vastly simpler and less prone to bugs under pressure.

Variables:

arr: The dynamically allocated underlying memory block.
frontIndex & rearIndex: The active window of our circular structure.
currentSize: The guardrail that prevents overlapping pointers.

Important Lines:

rearIndex = (rearIndex + 1) % capacity; -> The "Wrap Around" logic for adding.
frontIndex = (frontIndex + 1) % capacity; -> The "Wrap Around" logic for removing.

complexity analysis

video reference:

reference video

problem link:

https://www.naukri.com/code360/problems/implement-queue-using-arrays_8390825