Circular Queue Implementation Using Array in DSA Typescript

Mental Model

A circular queue uses a fixed-size array where the end connects back to the start, so we reuse empty spaces efficiently.

Analogy: Imagine a round table with fixed seats. When someone leaves, the next person can sit there without needing a bigger table.

Front -> [ ] [ ] [ ] [ ] [ ] ← Rear
Indexes -> 0   1   2   3   4
Initially: front = -1, rear = -1 (empty queue)

Dry Run Walkthrough

Input: Create a circular queue of size 5, enqueue 3 elements (10, 20, 30), dequeue 1 element, enqueue 2 more elements (40, 50), then enqueue 1 more element (60) to test full condition.

Goal: Show how elements wrap around in the array and how the queue handles full and empty states.

Step 1: Enqueue 10

Front -> [10] [ ] [ ] [ ] [ ] ← Rear
front=0, rear=0

Why: First element sets front and rear to 0.

Step 2: Enqueue 20

Front -> [10] [20] [ ] [ ] [ ] ← Rear
front=0, rear=1

Why: Rear moves forward to add new element.

Step 3: Enqueue 30

Front -> [10] [20] [30] [ ] [ ] ← Rear
front=0, rear=2

Why: Rear moves forward again.

Step 4: Dequeue (remove 10)

Front -> [ ] [20] [30] [ ] [ ] ← Rear
front=1, rear=2

Why: Front moves forward to remove element.

Step 5: Enqueue 40

Front -> [ ] [20] [30] [40] [ ] ← Rear
front=1, rear=3

Why: Rear moves forward to add element.

Step 6: Enqueue 50

Front -> [ ] [20] [30] [40] [50] ← Rear
front=1, rear=4

Why: Rear moves forward to last index.

Step 7: Enqueue 60 (wrap around)

Front -> [60] [20] [30] [40] [50] ← Rear
front=1, rear=0

Why: Rear wraps to start of array due to circular nature.

Step 8: Try enqueue 70 (queue full)

Front -> [60] [20] [30] [40] [50] ← Rear
front=1, rear=0

Why: Queue is full; cannot add more elements.

Result:

Final queue: 20 -> 30 -> 40 -> 50 -> 60 -> null
front=1, rear=0

Annotated Code

DSA Typescript

class CircularQueue {
  private queue: number[];
  private front: number;
  private rear: number;
  private size: number;

  constructor(size: number) {
    this.size = size;
    this.queue = new Array(size);
    this.front = -1;
    this.rear = -1;
  }

  enqueue(value: number): boolean {
    if ((this.rear + 1) % this.size === this.front) {
      // Queue is full
      return false;
    }
    if (this.front === -1) {
      // First element
      this.front = 0;
    }
    this.rear = (this.rear + 1) % this.size; // move rear forward circularly
    this.queue[this.rear] = value;
    return true;
  }

  dequeue(): number | null {
    if (this.front === -1) {
      // Queue is empty
      return null;
    }
    const value = this.queue[this.front];
    if (this.front === this.rear) {
      // Only one element was present
      this.front = -1;
      this.rear = -1;
    } else {
      this.front = (this.front + 1) % this.size; // move front forward circularly
    }
    return value;
  }

  printQueue(): string {
    if (this.front === -1) {
      return "Queue is empty";
    }
    let result = "";
    let i = this.front;
    while (true) {
      result += this.queue[i] + " -> ";
      if (i === this.rear) {
        break;
      }
      i = (i + 1) % this.size;
    }
    result += "null";
    return result;
  }
}

// Driver code
const cq = new CircularQueue(5);
cq.enqueue(10);
cq.enqueue(20);
cq.enqueue(30);
cq.dequeue();
cq.enqueue(40);
cq.enqueue(50);
cq.enqueue(60); // wraps around
const enqueueResult = cq.enqueue(70); // should fail
console.log(cq.printQueue());
console.log("Enqueue 70 success?", enqueueResult);

if ((this.rear + 1) % this.size === this.front) {

Check if queue is full by seeing if next rear position equals front

if (this.front === -1) { this.front = 0; }

Set front to 0 when adding first element

this.rear = (this.rear + 1) % this.size;

Move rear pointer forward circularly

if (this.front === -1) { return null; }

Check if queue is empty before dequeue

if (this.front === this.rear) { this.front = -1; this.rear = -1; } else { this.front = (this.front + 1) % this.size; }

Update front pointer or reset queue if last element removed

while (true) { ... i = (i + 1) % this.size; }

Traverse queue circularly from front to rear for printing

Output

20 -> 30 -> 40 -> 50 -> 60 -> null

Enqueue 70 success? false

Complexity Analysis

Time: O(1) for enqueue and dequeue because we use fixed-size array and pointers without shifting elements

Space: O(n) because we allocate fixed-size array of size n

vs Alternative: Compared to a normal queue using array with shifting, circular queue avoids O(n) shifts making operations faster

Edge Cases

Empty queue dequeue

Returns null indicating no elements to remove

DSA Typescript

if (this.front === -1) { return null; }

Enqueue on full queue

Returns false indicating queue is full and cannot add element

DSA Typescript

if ((this.rear + 1) % this.size === this.front) { return false; }

Single element dequeue

Resets front and rear to -1 indicating queue becomes empty

DSA Typescript

if (this.front === this.rear) { this.front = -1; this.rear = -1; }

When to Use This Pattern

When you need a fixed-size queue that efficiently reuses space without shifting elements, use a circular queue with modular arithmetic to wrap pointers.

Common Mistakes

Mistake: Not using modulo operation to wrap rear and front pointers causing index out of bounds
Fix: Always update pointers using (pointer + 1) % size to wrap around

Mistake: Confusing full and empty conditions leading to incorrect enqueue or dequeue
Fix: Use the condition (rear + 1) % size == front for full and front == -1 for empty

Summary

Implements a queue using a fixed-size array where rear wraps to start to reuse space.

Use when you want a queue with fixed capacity and efficient enqueue/dequeue without shifting.

The key is to move front and rear pointers circularly using modulo to manage wrap-around.

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 uses all available space by wrapping around the array.

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 is free space at the front.

2. Step 2: Circular queue advantage

   A circular queue connects the end of the array back to the front, allowing reuse of empty spaces and efficient use of the array.

3. Final Answer:

   It efficiently uses all available space by wrapping around the array. -> Option B

4. Quick Check:

   Circular queue = efficient space use [OK]

Hint: Circular queue reuses space by wrapping indices [OK]

Common Mistakes:

• Thinking circular queue sorts elements
• Believing it uses less memory than linear queue
• Assuming it stores different data types automatically

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

easy

A. if (rear === front)

B. if (front === -1)

C. if ((rear + 1) % size === front)

D. if (rear === size - 1)

Solution

1. Step 1: Understand full condition in circular queue

   The queue is full when the next position of rear (rear + 1) modulo size equals front, meaning no space to insert.

2. Step 2: Apply modulo for wrap-around

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

3. Final Answer:

   if ((rear + 1) % size === front) -> Option C

4. Quick Check:

   Full condition = (rear + 1) % size === front [OK]

Hint: Full when next rear wraps to front [OK]

Common Mistakes:

• Checking rear === front means empty, not full
• Using rear === size - 1 ignores wrap-around
• Checking front === -1 is for empty queue

3. Consider a circular queue of size 5 (indices 0 to 4). Initially, front = 0 and rear = 3. After performing enqueue(10) and dequeue(), what are the new values of front and rear?

medium

A. front = 0, rear = 4

B. front = 1, rear = 3

C. front = 0, rear = 3

D. front = 1, rear = 4

Solution

1. Step 1: Perform enqueue(10)

   rear moves from 3 to (3 + 1) % 5 = 4. So rear = 4, front remains 0.

2. Step 2: Perform dequeue()

   front moves from 0 to (0 + 1) % 5 = 1. So front = 1, rear remains 4.

3. Final Answer:

   front = 1, rear = 4 -> Option D

4. Quick Check:

   Enqueue rear+1=4, Dequeue front+1=1 [OK]

Hint: Update rear on enqueue, front on dequeue with modulo [OK]

Common Mistakes:

• Not applying modulo for wrap-around
• Updating front on enqueue instead of rear
• Confusing initial and final pointer positions

4. Given the following TypeScript snippet for dequeue operation in a circular queue, identify the bug:

function dequeue() {
  if (front === -1) return null;
  const value = queue[front];
  if (front === rear) {
    front = rear = -1;
  } else {
    front = front + 1;
  }
  return value;
}

medium

A. Missing modulo operation when updating front, causing index overflow.

B. Incorrect check for empty queue; should check rear instead of front.

C. Should update rear instead of front after dequeue.

D. Returning value before updating front causes wrong output.

Solution

1. Step 1: Analyze front update in dequeue

   The code updates front as front = front + 1 without modulo, which can exceed array bounds.

2. Step 2: Correct update with modulo

   To wrap around in circular queue, front should be updated as front = (front + 1) % size.

3. Final Answer:

   Missing modulo operation when updating front, causing index overflow. -> Option A

4. Quick Check:

   Front update needs modulo [OK]

Hint: Always use modulo when moving front or rear [OK]

Common Mistakes:

• Forgetting modulo causes index errors
• Confusing front and rear updates
• Wrong empty queue condition check

5. You have a circular queue of size 4. You perform these operations in order: enqueue(5), enqueue(10), enqueue(15), dequeue(), enqueue(20), enqueue(25). What will be the final state of the queue array (index 0 to 3) and the positions of front and rear?

hard

A. Queue: [25, 10, 15, 20], front = 1, rear = 0

B. Queue: [5, 10, 15, 20], front = 1, rear = 3

C. Queue: [20, 25, 15, 10], front = 0, rear = 1

D. Queue: [10, 15, 20, 25], front = 0, rear = 3

Solution

1. Step 1: Perform enqueues and dequeue step-by-step

   Start: front = -1, rear = -1, queue size = 4 - enqueue(5): front=0, rear=0, queue=[5,_,_,_] - enqueue(10): rear=1, queue=[5,10,_,_] - enqueue(15): rear=2, queue=[5,10,15,_] - dequeue(): front=1, queue unchanged - enqueue(20): rear=3, queue=[5,10,15,20] - enqueue(25): rear=(3+1)%4=0, queue[0]=25, queue=[25,10,15,20]

2. Step 2: Final front and rear positions

   front=1 (pointing to 10), rear=0 (pointing to 25). Queue array is [25,10,15,20].

3. Final Answer:

   Queue: [25, 10, 15, 20], front = 1, rear = 0 -> Option A

4. Quick Check:

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

Hint: Track front/rear with modulo after each operation [OK]

Common Mistakes:

• Not wrapping rear index on enqueue
• Not updating front on dequeue
• Mixing up front and rear positions