Circular Queue Implementation Using Array in DSA Java - Build from Scratch

Circular Queue Implementation Using Array

📖 Scenario: You are building a simple ticketing system where people join a queue to get service. To manage the queue efficiently, you will use a circular queue implemented with an array.

🎯 Goal: Create a circular queue using an array with fixed size 5. You will add elements (enqueue), remove elements (dequeue), and finally print the queue's current state.

📋 What You'll Learn

Create an integer array called queue with size 5

Create integer variables front and rear initialized to -1

Create an integer variable size set to 5

Write a method enqueue to add elements to the queue

Write a method dequeue to remove elements from the queue

Print the queue elements from front to rear in circular order

💡 Why This Matters

🌍 Real World

Circular queues are used in real-world systems like CPU scheduling, buffering data streams, and managing resources in a fixed-size buffer.

💼 Career

Understanding circular queues helps in roles involving system programming, embedded systems, and performance-critical applications where efficient memory use is important.

1

Create the Circular Queue Data Structure

Create an integer array called queue with size 5, and integer variables front and rear both set to -1. Also create an integer variable size set to 5.

DSA Java

// Your code here

Hint

Use int[] queue = new int[5]; to create the array and initialize front and rear to -1.

2

Add Enqueue Method to Insert Elements

Add a method called enqueue that takes an integer value and adds it to the circular queue. Update rear and front accordingly. Handle the case when the queue is full by printing "Queue is full".

DSA Java

public class CircularQueue {
    int[] queue = new int[5];
    int front = -1;
    int rear = -1;
    int size = 5;

    // Add enqueue method below
    // Your code here
}

Hint

Check if queue is full by comparing (rear + 1) % size with front. If empty, set front to 0. Then update rear and insert the value.

3

Add Dequeue Method to Remove Elements

Add a method called dequeue that removes and returns the front element from the circular queue. Update front and rear accordingly. If the queue is empty, print "Queue is empty" and return -1.

DSA Java

public class CircularQueue {
    int[] queue = new int[5];
    int front = -1;
    int rear = -1;
    int size = 5;

    public 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;
    }

    // Add dequeue method below
    // Your code here
}

Hint

Check if queue is empty by front == -1. Save the front value, then update front. If queue becomes empty after removal, reset front and rear to -1.

4

Print the Current Queue Elements

Write a method called printQueue that prints the elements of the circular queue from front to rear in order, separated by spaces. If the queue is empty, print "Queue is empty". Then, in the main method, enqueue 10, 20, 30, dequeue one element, enqueue 40 and 50, and finally call printQueue.

DSA Java

public class CircularQueue {
    int[] queue = new int[5];
    int front = -1;
    int rear = -1;
    int size = 5;

    public 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;
    }

    public int dequeue() {
        if (front == -1) {
            System.out.println("Queue is empty");
            return -1;
        }
        int value = queue[front];
        if (front == rear) {
            front = -1;
            rear = -1;
        } else {
            front = (front + 1) % size;
        }
        return value;
    }

    // Add printQueue method and main method below
    // Your code here
}

Hint

Use a loop starting from front to rear using modulo to print elements. In main, follow the enqueue and dequeue steps exactly, then print the 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