Queue Implementation Using Array in DSA Java - Execution Trace

Concept Flow - Queue Implementation Using Array

Initialize array with fixed size

↓

Set front = -1, rear = -1

↓

Enqueue Operation

↓

Check if queue is full?

Yes→Reject enqueue

No↓

If empty, set front=0

↓

Increment rear, add element

↓

Dequeue Operation

↓

Check if queue is empty?

Yes→Reject dequeue

No↓

Remove element at front

↓

If front == rear, reset front and rear to -1

↓

Else increment front

↓

Done

This flow shows how a queue uses an array with front and rear pointers to add (enqueue) and remove (dequeue) elements while checking for full or empty conditions.

Execution Sample

DSA Java

int[] queue = new int[3];
int front = -1, rear = -1;
// Enqueue 10
rear++;
queue[rear] = 10;
front = 0;

This code enqueues the number 10 into an empty queue implemented using an array.

Execution Table

Step	Operation	front	rear	Queue Array State	Notes
1	Initialize queue	-1	-1	[_, _, _]	Queue is empty
2	Enqueue 10	0	0	[10, _, _]	front set to 0, rear incremented to 0
3	Enqueue 20	0	1	[10, 20, _]	rear incremented to 1
4	Enqueue 30	0	2	[10, 20, 30]	rear incremented to 2, queue full now
5	Enqueue 40	0	2	[10, 20, 30]	Queue full, cannot enqueue 40
6	Dequeue	1	2	[10, 20, 30]	Removed 10, front incremented to 1
7	Dequeue	2	2	[10, 20, 30]	Removed 20, front incremented to 2
8	Dequeue	-1	-1	[10, 20, 30]	Removed 30, queue empty, reset front and rear
9	Dequeue	-1	-1	[10, 20, 30]	Queue empty, cannot dequeue
10	Enqueue 50	0	0	[50, 20, 30]	front set to 0, rear set to 0, enqueue 50
11	Final State	0	0	[50, 20, 30]	Queue has one element 50

💡 Execution stops after final enqueue and dequeue attempts; queue is either full or empty accordingly.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 6	After Step 8	After Step 10	Final
front	-1	0	0	0	1	-1	0	0
rear	-1	0	1	2	2	-1	0	0
queue	[_, _, _]	[10, _, _]	[10, 20, _]	[10, 20, 30]	[10, 20, 30]	[10, 20, 30]	[50, 20, 30]	[50, 20, 30]

Key Moments - 3 Insights

Why do front and rear both start at -1?

Starting front and rear at -1 means the queue is empty. This is shown in step 1 of the execution_table where both are -1 and the queue array is empty.

Why can't we enqueue when rear is at the last index?

When rear reaches the last index (2 in this case), the queue is full. Step 5 shows enqueue rejected because rear is 2 and the array size is 3.

Why do we reset front and rear to -1 after last dequeue?

After removing the last element, the queue becomes empty. Step 8 resets front and rear to -1 to indicate empty queue.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of front after step 6 (first dequeue)?

A 0

B 1

C 2

D -1

💡 Hint

Check the 'front' column in execution_table row for step 6.

At which step does the queue become empty again after enqueues and dequeues?

A Step 4

B Step 5

C Step 8

D Step 10

💡 Hint

Look for when front and rear reset to -1 in execution_table.

If we try to enqueue at step 5, what happens to rear and queue array?

A rear increments, element added

B rear stays same, element not added

C rear resets to -1

D front increments

💡 Hint

Step 5 shows enqueue rejected due to full queue; rear and array unchanged.

Concept Snapshot

Queue using array:
- Use fixed size array
- front and rear start at -1 (empty)
- Enqueue: if not full, rear++ and add element
- Dequeue: if not empty, remove front element, front++
- Reset front and rear to -1 when queue empty
- Check full: rear == size-1; empty: front == -1

Full Transcript

This visualization shows how a queue is implemented using an array with fixed size. The queue uses two pointers: front and rear, both starting at -1 to indicate an empty queue. When we enqueue, we check if the queue is full by comparing rear to the last index. If not full, we increment rear and add the element. If the queue was empty, front is set to 0. When we dequeue, we check if the queue is empty by checking if front is -1. If not empty, we remove the element at front and increment front. If after dequeue front passes rear, we reset both to -1 to mark the queue empty. The execution table traces these steps with the queue array state and pointer values. Key moments clarify why pointers start at -1, why enqueue fails when full, and why pointers reset after last dequeue. The quiz tests understanding of pointer values and queue state changes at specific steps.

Practice

1. What is the main purpose of using an array in a queue implementation?

easy

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

B. To allow random access to elements anywhere in the queue

C. To sort elements automatically when inserted

D. To store elements in a tree structure

Solution

1. Step 1: Understand queue storage

   A queue stores elements in order, so an array can hold them in a fixed linear sequence.

2. Step 2: Compare other options

   Random access and sorting are not queue properties; tree structure is unrelated.

3. Final Answer:

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

4. Quick Check:

   Queue uses array for linear storage [OK]

Hint: Queue uses array for fixed linear storage [OK]

Common Mistakes:

• Thinking queue allows random access
• Assuming array sorts elements automatically
• Confusing queue with tree structures

2. Which of the following is the correct way to check if a queue implemented using an array is empty?

easy

A. if (front == rear) return true;

B. if (rear == size) return true;

C. if (front == -1) return true;

D. if (front > rear) return true;

Solution

1. Step 1: Understand empty queue condition

   In array queue, front = -1 means no elements have been enqueued yet.

2. Step 2: Analyze other conditions

   front == rear means queue is full or empty depending on implementation; rear == size means full; front > rear is invalid.

3. Final Answer:

   if (front == -1) return true; -> Option C

4. Quick Check:

   Empty queue check uses front == -1 [OK]

Hint: Empty queue usually has front at -1 [OK]

Common Mistakes:

• Using front == rear to check empty (can be full)
• Checking rear == size for empty instead of full
• Using front > rear which is invalid

3. What will be the output after the following operations on a queue of size 5 implemented using an array?

enqueue(10); enqueue(20); dequeue(); enqueue(30); enqueue(40); dequeue(); enqueue(50); display();

medium

A. 30 -> 40 -> 50 -> null

B. 20 -> 30 -> 40 -> 50 -> null

C. 10 -> 20 -> 30 -> 40 -> 50 -> null

D. 40 -> 50 -> null

Solution

1. Step 1: Trace enqueue and dequeue operations

   enqueue(10), enqueue(20) adds 10,20; dequeue removes 10; enqueue(30), enqueue(40) adds 30,40; dequeue removes 20; enqueue(50) adds 50.

2. Step 2: Determine queue content after operations

   Remaining elements are 30, 40, 50 in order.

3. Final Answer:

   30 -> 40 -> 50 -> null -> Option A

4. Quick Check:

   Queue after operations = 30,40,50 [OK]

Hint: Track enqueue/dequeue stepwise to find queue content [OK]

Common Mistakes:

• Not removing correct elements on dequeue
• Assuming queue resets after full
• Confusing order of elements after operations

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

if (rear == size) {
  System.out.println("Queue is full");
} else {
  rear++;
  queue[rear] = value;
}

medium

A. rear should be incremented after assigning value

B. queue array size is not checked before insertion

C. front pointer is not updated when queue is empty

D. Condition should be rear == size - 1 to check full

Solution

1. Step 1: Analyze full queue condition

   Array index goes from 0 to size-1, so rear == size means out of bounds; full condition is rear == size - 1.

2. Step 2: Check rear increment and assignment

   Incrementing rear before assignment is correct if rear starts at -1.

3. Final Answer:

   Condition should be rear == size - 1 to check full -> Option D

4. Quick Check:

   Full queue check uses rear == size - 1 [OK]

Hint: Array index max is size - 1, not size [OK]

Common Mistakes:

• Checking rear == size instead of size - 1
• Incrementing rear after assignment causing overwrite
• Ignoring front pointer update on empty queue

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); enqueue(25); dequeue(); enqueue(30); display();

Assume the queue does not support circular wrapping and front and rear start at -1.

hard

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

B. Queue Overflow error occurs

C. 20 -> 25 -> 30 -> null

D. 15 -> 20 -> 25 -> null

Solution

1. Step 1: Trace each operation stepwise

   enqueue(5) adds 5; enqueue(10) adds 10; dequeue removes 5; enqueue(15) adds 15; enqueue(20) adds 20; enqueue(25) attempts to add but queue size is 4 and rear is at last index.

2. Step 2: Check for overflow due to no circular wrap

   Since queue is full at rear index 3, enqueue(25) causes overflow; subsequent operations cannot proceed.

3. Final Answer:

   Queue Overflow error occurs -> Option B

4. Quick Check:

   No circular wrap causes overflow at full array [OK]

Hint: Without circular queue, overflow occurs when rear reaches end [OK]

Common Mistakes:

• Assuming queue wraps around without circular logic
• Ignoring overflow condition on enqueue
• Miscounting elements after dequeue