Circular Queue Implementation Using Array in DSA Java - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a circular queue?

A circular queue is a type of queue where the last position is connected back to the first position to make a circle. This helps use the array space efficiently by reusing empty spots after dequeue operations.

beginner

How do you check if a circular queue is full?

The queue is full when the next position of rear is equal to front. In formula: (rear + 1) % size == front.

beginner

How do you check if a circular queue is empty?

The queue is empty when front and rear are both -1 or front == -1. This means no elements are in the queue.

beginner

What happens to front and rear pointers when you enqueue in an empty circular queue?

Both front and rear are set to 0 because the first element is added at the start of the array.

beginner

Why is modulo (%) operator used in circular queue implementation?

Modulo operator helps wrap around the array index to the start when the end is reached, making the queue circular.

What condition indicates that a circular queue is full?

A rear == -1

B front == rear

C (rear + 1) % size == front

D front == -1

A circular queue is full when the next position of rear is front, meaning no space to add new elements.

What is the initial value of front and rear in an empty circular queue?

A front = -1, rear = -1

B front = 1, rear = 1

C front = 0, rear = 0

D front = size, rear = size

Both front and rear are set to -1 to indicate the queue is empty.

When enqueuing the first element in a circular queue, what happens?

A front and rear both set to 0

B front and rear remain -1

C rear set to size - 1

D front set to size - 1

Both front and rear are set to 0 to point to the first element's position.

Why do we use modulo operator (%) in circular queue?

A To increase the size of the queue

B To wrap around the index to the start of the array

C To check if queue is empty

D To check if queue is full

Modulo operator wraps the index to the start when it reaches the end, making the queue circular.

What happens to front pointer when you dequeue the last element in a circular queue?

A front becomes equal to rear

B front moves forward by 1

C front stays the same

D front becomes -1 indicating empty queue

When the last element is dequeued, front and rear are reset to -1 to show the queue is empty.

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

Think about how the pointers move and wrap around the array.

Describe why a circular queue is more efficient than a simple linear queue when using arrays.

Consider what happens when elements are removed from the front in a linear queue.

Practice

1. What is the main advantage of using a circular queue over a simple linear queue when implemented using an array?

easy

A. It allows storing different data types in the same queue.

B. It efficiently utilizes the array space by reusing empty slots after dequeue operations.

C. It automatically sorts the elements in the queue.

D. It uses less memory than a linear queue.

Solution

1. Step 1: Understand linear queue limitation

   In a linear queue using an array, once the rear reaches the end, no more elements can be added even if there are empty slots at the front due to dequeues.

2. Step 2: Circular queue advantage

   A circular queue connects the end of the array back to the front, allowing reuse of empty slots and efficient space usage.

3. Final Answer:

   It efficiently utilizes the array space by reusing empty slots after dequeue operations. -> Option B

4. Quick Check:

   Space reuse = Advantage [OK]

Hint: Circular queue reuses space after dequeue, unlike linear queue [OK]

Common Mistakes:

• Thinking circular queue sorts elements
• Believing circular queue uses less memory
• Confusing data type flexibility with queue type

2. Which of the following is the correct condition to check if a circular queue is full when using an array of size n with front and rear pointers?

easy

A. front == (rear + 1) % n

B. rear == (front + 1) % n

C. front == rear

D. rear == n - 1

Solution

1. Step 1: Understand circular queue full condition

   In a circular queue, the queue is full when the next position of rear (rear + 1 modulo n) is equal to front.

2. Step 2: Apply modulo for wrap-around

   Using modulo ensures the rear wraps to the start of the array, so full condition is front == (rear + 1) % n.

3. Final Answer:

   front == (rear + 1) % n -> Option A

4. Quick Check:

   Full if next rear equals front [OK]

Hint: Full when front is just ahead of rear in circular manner [OK]

Common Mistakes:

• Using rear == (front + 1) % n (wrong direction)
• Checking front == rear (means empty, not full)
• Ignoring modulo wrap-around

3. Consider a circular queue of size 5 (indices 0 to 4). Initially, front = -1 and rear = -1. The following operations are performed:
enqueue(10), enqueue(20), enqueue(30), dequeue(), enqueue(40), enqueue(50), enqueue(60)
What will be the values of front and rear after these operations?

medium

A. front = 2, rear = 1

B. front = 0, rear = 4

C. front = 1, rear = 3

D. front = 1, rear = 0

Solution

1. Step 1: Trace each operation step-by-step

   Start: front = -1, rear = -1
   enqueue(10): front=0, rear=0
   enqueue(20): rear=1
   enqueue(30): rear=2
   dequeue(): front=1 (removes 10)
   enqueue(40): rear=3
   enqueue(50): rear=4
   enqueue(60): rear wraps to 0 (since (4+1)%5=0)

2. Step 2: Final front and rear values

   After last enqueue, front=1, rear=0

3. Final Answer:

   front = 1, rear = 0 -> Option D

4. Quick Check:

   Wrap rear with modulo, front moves on dequeue [OK]

Hint: Update rear with modulo; front moves on dequeue [OK]

Common Mistakes:

• Not wrapping rear index after reaching array end
• Not updating front after dequeue
• Confusing initial front and rear values

4. Given the following snippet of a circular queue enqueue method, identify the bug:

void enqueue(int value) {
  if ((rear + 1) % size == front) {
    System.out.println("Queue is full");
    return;
  }
  if (front == -1) front = 0;
  rear = (rear + 1) % size;
  queue[rear] = value;
}

medium

A. The front pointer should be updated after enqueue.

B. The condition to check full queue is incorrect.

C. The rear pointer is updated before inserting the value.

D. The method does not handle empty queue initialization.

Solution

1. Step 1: Identify standard enqueue order

   In standard circular queue implementations (wasting one slot to distinguish empty/full), the value is inserted at the current rear first: queue[rear] = value; then rear = (rear + 1) % size.

2. Step 2: Problem with given code

   This code updates rear first, then inserts. This causes false positives in the full check after dequeue operations make the queue empty, as front == (old rear + 1) % size, matching the full condition.

3. Final Answer:

   The rear pointer is updated before inserting the value. -> Option C

4. Quick Check:

   Standard order: insert then increment rear [OK]

Hint: Check pointer updates order carefully in enqueue method [OK]

Common Mistakes:

• Confusing front and rear updates
• Misunderstanding full condition logic
• Ignoring initial empty queue setup

5. You have a circular queue of size 6. After performing several enqueue and dequeue operations, the front is at index 4 and rear is at index 2. Which of the following statements is true about the queue's current state?

hard

A. The queue has elements from index 4 to 5 and 0 to 2.

B. The queue is full.

C. The queue is empty.

D. The queue has elements only between indices 2 and 4.

Solution

1. Step 1: Understand circular queue indexing

   With front at 4 and rear at 2 in a size 6 queue, the queue wraps around the end of the array.

2. Step 2: Identify occupied indices

   Elements are from front (4) to end (5), then from start (0) to rear (2), so indices 4,5,0,1,2 hold elements.

3. Final Answer:

   The queue has elements from index 4 to 5 and 0 to 2. -> Option A

4. Quick Check:

   Wrap-around means elements split across array ends [OK]

Hint: Front > rear means queue wraps around array end [OK]

Common Mistakes:

• Assuming front > rear means empty queue
• Thinking queue is full when front > rear
• Ignoring wrap-around in circular queue