Queue Implementation Using Array in DSA C++

Mental Model

A queue is a line where the first person in is the first person out. Using an array, we keep track of where the line starts and ends.

Analogy: Imagine a line of people waiting to buy tickets. The first person to get in line is the first to get the ticket and leave. The line is like an array, and we remember who is at the front and who is at the back.

front -> [ ] [ ] [ ] [ ] [ ] ← rear
indexes  0   1   2   3   4

Dry Run Walkthrough

Input: Create queue with size 5, enqueue 10, enqueue 20, dequeue, enqueue 30

Goal: Show how elements enter and leave the queue using array indexes

Step 1: enqueue 10 at rear

front=0, rear=0, array=[10, _, _, _, _]

Why: Add first element at start of array

Step 2: enqueue 20 at rear+1

front=0, rear=1, array=[10, 20, _, _, _]

Why: Add next element after the first

Step 3: dequeue element at front

front=1, rear=1, array=[10, 20, _, _, _]

Why: Remove first element by moving front forward

Step 4: enqueue 30 at rear+1

front=1, rear=2, array=[10, 20, 30, _, _]

Why: Add new element after last one

Result:

front=1, rear=2, array=[10, 20, 30, _, _]
Queue elements from front to rear: 20 -> 30 -> null

Annotated Code

DSA C++

#include <iostream>
using namespace std;

class Queue {
private:
    int *arr;
    int capacity;
    int front;
    int rear;
    int count;

public:
    Queue(int size) {
        arr = new int[size];
        capacity = size;
        front = 0;
        rear = -1;
        count = 0;
    }

    void enqueue(int item) {
        if (count == capacity) {
            cout << "Queue is full\n";
            return;
        }
        rear = (rear + 1) % capacity; // move rear forward circularly
        arr[rear] = item;
        count++;
    }

    void dequeue() {
        if (count == 0) {
            cout << "Queue is empty\n";
            return;
        }
        front = (front + 1) % capacity; // move front forward circularly
        count--;
    }

    void display() {
        if (count == 0) {
            cout << "Queue is empty\n";
            return;
        }
        int i = front;
        int c = count;
        while (c > 0) {
            cout << arr[i] << " -> ";
            i = (i + 1) % capacity;
            c--;
        }
        cout << "null\n";
    }

    ~Queue() {
        delete[] arr;
    }
};

int main() {
    Queue q(5);
    q.enqueue(10); // enqueue 10
    q.enqueue(20); // enqueue 20
    q.dequeue();   // dequeue front element (10)
    q.enqueue(30); // enqueue 30
    q.display();   // display queue
    return 0;
}

rear = (rear + 1) % capacity; // move rear forward circularly

advance rear index circularly to next position for enqueue

arr[rear] = item;

store new item at rear position

count++;

increase count of elements in queue

front = (front + 1) % capacity; // move front forward circularly

advance front index circularly to remove element

count--;

decrease count of elements after dequeue

while (c > 0) { cout << arr[i] << " -> "; i = (i + 1) % capacity; c--; }

iterate from front to rear circularly to print queue elements

Output

20 -> 30 -> null

Complexity Analysis

Time: O(1) for enqueue and dequeue because we use fixed index moves without shifting elements

Space: O(n) because we store up to n elements in the array

vs Alternative: Compared to linked list queue, array queue uses fixed space and faster indexing but needs circular logic to reuse space

Edge Cases

enqueue when queue is full

prints 'Queue is full' and does not add element

DSA C++

if (count == capacity) { cout << "Queue is full\n"; return; }

dequeue when queue is empty

prints 'Queue is empty' and does nothing

DSA C++

if (count == 0) { cout << "Queue is empty\n"; return; }

enqueue and dequeue wrap around array end

front and rear indexes wrap using modulo to reuse array space

DSA C++

rear = (rear + 1) % capacity; front = (front + 1) % capacity;

When to Use This Pattern

When you need a first-in-first-out order with fixed size and fast access, use a circular array queue to efficiently manage elements.

Common Mistakes

Mistake: Not using modulo to wrap rear and front indexes causing out-of-bound errors
Fix: Use modulo operator (%) with capacity to wrap indexes circularly

Mistake: Not checking if queue is full before enqueue leading to overwriting data
Fix: Check count against capacity before adding new element

Mistake: Not updating count correctly causing wrong empty/full detection
Fix: Increment count on enqueue and decrement on dequeue properly

Summary

Implements a queue using a fixed-size array with front and rear pointers moving circularly.

Use when you want a simple queue with fixed capacity and fast enqueue/dequeue operations.

Remember to wrap front and rear indexes using modulo to reuse array space efficiently.

Practice

1. What is the main purpose of using an array to implement a queue?

easy

A. To store elements in a fixed-size linear order for FIFO operations

B. To store elements randomly for quick access

C. To sort elements automatically

D. To store elements in a LIFO order

Solution

1. Step 1: Understand queue behavior

   A queue follows FIFO (First In First Out), meaning elements are processed in the order they arrive.

2. Step 2: Role of array in queue

   An array stores elements in a fixed linear order, which helps maintain the FIFO order by using front and rear indices.

3. Final Answer:

   To store elements in a fixed-size linear order for FIFO operations -> Option A

4. Quick Check:

   Queue uses array for FIFO storage = C [OK]

Hint: Queue means FIFO; array stores elements linearly [OK]

Common Mistakes:

• Confusing queue with stack (LIFO)
• Thinking array sorts elements automatically
• Assuming random access is main goal

2. Which of the following is the correct way to declare a queue array of size 5 in C++?

easy

A. array queue(5);

B. int queue[5];

C. int[5] queue;

D. queue int[5];

Solution

1. Step 1: Recall C++ array declaration syntax

   In C++, arrays are declared as: type name[size]; so int queue[5]; is correct.

2. Step 2: Check other options

   Options A, B, and C do not follow valid C++ syntax for array declaration.

3. Final Answer:

   int queue[5]; -> Option B

4. Quick Check:

   C++ array syntax = type name[size] [OK]

Hint: Remember C++ arrays: type name[size]; [OK]

Common Mistakes:

• Placing size before name
• Using wrong keywords like 'array'
• Incorrect order of type and name

3. What will be the output after performing these operations on an empty queue of size 3 implemented using array?
enqueue(10); enqueue(20); dequeue(); enqueue(30); display();
Assume enqueue adds at rear and dequeue removes from front.

medium

A. 10 -> 30 -> null

B. 10 -> 20 -> 30 -> null

C. 30 -> null

D. 20 -> 30 -> null

Solution

1. Step 1: Perform enqueue(10) and enqueue(20)

   Queue becomes: 10 -> 20 -> null

2. Step 2: Perform dequeue()

   Removes 10 from front, queue becomes: 20 -> null

3. Step 3: Perform enqueue(30)

   Add 30 at rear, queue becomes: 20 -> 30 -> null

4. Step 4: Display queue

   Output is: 20 -> 30 -> null

5. Final Answer:

   20 -> 30 -> null -> Option D

6. Quick Check:

   After dequeue and enqueue, queue = 20, 30 [OK]

Hint: Track front and rear after each operation [OK]

Common Mistakes:

• Not removing element on dequeue
• Adding new element at front instead of rear
• Confusing order of elements

4. Identify the error in this queue implementation snippet using array:

int queue[3], front = -1, rear = -1;
void enqueue(int x) {
  if (rear == 3) {
    cout << "Queue Full";
    return;
  }
  rear++;
  queue[rear] = x;
  if (front == -1) front = 0;
}

medium

A. front should be incremented in enqueue

B. rear should be initialized to 0

C. Condition should be rear == 2 to check full queue

D. No error, code is correct

Solution

1. Step 1: Understand array indexing for size 3

   Array indices are 0, 1, 2. So rear should not exceed 2.

2. Step 2: Check condition for full queue

   Condition rear == 3 is wrong because index 3 is out of bounds. It should be rear == 2.

3. Final Answer:

   Condition should be rear == 2 to check full queue -> Option C

4. Quick Check:

   Array max index = size-1 = 2 [OK]

Hint: Array max index = size - 1, check boundary carefully [OK]

Common Mistakes:

• Using size instead of size-1 for index check
• Incrementing front in enqueue
• Initializing rear incorrectly

5. Given a queue implemented using an array of size 4, initially empty, what will be the state of the queue after these operations?
enqueue(5); enqueue(10); dequeue(); enqueue(15); enqueue(20); dequeue(); enqueue(25); display();
Assume no circular queue and enqueue fails if rear reaches size-1.

hard

A. 15 -> 20 -> null

B. 10 -> 15 -> 20 -> 25 -> null

C. 15 -> 20 -> 25 -> null

D. 5 -> 10 -> 15 -> 20 -> null

Solution

1. Step 1: Perform enqueue(5), enqueue(10)

   Queue: 5 -> 10 -> null; front=0, rear=1

2. Step 2: Perform dequeue()

   Remove 5; Queue: 10 -> null; front=1, rear=1

3. Step 3: Perform enqueue(15), enqueue(20)

   Queue: 10 -> 15 -> 20 -> null; front=1, rear=3

4. Step 4: Perform dequeue()

   Remove 10; Queue: 15 -> 20 -> null; front=2, rear=3

5. Step 5: Perform enqueue(25)

   rear=3 (max index), cannot enqueue 25; operation fails, queue unchanged

6. Step 6: Display queue

   Queue elements from front=2 to rear=3: 15 -> 20 -> null

7. Final Answer:

   15 -> 20 -> null -> Option A

8. Quick Check:

   Check enqueue failure at full rear index [OK]

Hint: No circular queue means no wrap-around; watch rear limit [OK]

Common Mistakes:

• Assuming enqueue works after rear reaches max
• Not updating front after dequeue
• Confusing queue order after operations