Queue Implementation Using Array in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a queue in data structures?

A queue is a collection where elements are added at the back and removed from the front, following the First-In-First-Out (FIFO) principle.

beginner

What are the main operations of a queue implemented using an array?

The main operations are enqueue (add element at the back), dequeue (remove element from the front), peek/front (view the front element), and checking if the queue is empty or full.

beginner

Why do we need to check if the queue is full before enqueue in an array implementation?

Because the array has a fixed size, and if all positions are occupied, we cannot add more elements without overwriting or causing errors.

beginner

What happens when you dequeue an element from an array-based queue?

The front element is removed, and the front index moves forward to the next element. The removed element is no longer accessible.

intermediate

What is the limitation of a simple array-based queue without circular logic?

After several dequeues, the front index moves forward, and even if there is space at the start of the array, new elements cannot be enqueued, causing inefficient use of space.

In a queue implemented using an array, where do we add new elements?

A At the back (rear) of the queue

B At the front of the queue

C At any random position

D At the middle of the queue

New elements are always added at the back (rear) of the queue following FIFO.

What does the dequeue operation do in an array-based queue?

A Adds an element at the front

B Removes the element at the front

C Removes the element at the back

D Adds an element at the back

Dequeue removes the element at the front of the queue.

What condition indicates that an array-based queue is full?

A When front == rear

B When front is at index 0

C When the array is empty

D When rear reaches the last index of the array

The queue is full when the rear index reaches the last position of the array.

What is a drawback of a simple array queue without circular logic?

A It allows duplicate elements

B It cannot enqueue elements

C It wastes space after some dequeues

D It does not support dequeue

Without circular logic, space at the start of the array is wasted after dequeues.

Which of these is NOT a typical queue operation?

A Sort

B Dequeue

C Peek

D Enqueue

Sorting is not a standard operation of a queue.

Explain how enqueue and dequeue operations work in a queue implemented using an array.

Think about where elements enter and leave the queue.

Describe the limitation of a simple array queue and how it affects space usage.

Consider what happens after multiple dequeues.

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