Course contentsShow
← Computer Science
Lesson 380 of 2,8729. Stacks and QueuesFree lesson

Circular Queue Implementation Details

Implementing enqueue and dequeue in a circular queue, handling full and empty conditions.

Circular Queue Implementation Details

You'll learn: How to implement enqueue and dequeue operations in a circular queue while correctly detecting when it's full or empty.

The Core Challenge

In a circular queue using an array, both front and rear pointers wrap around to the beginning when they reach the array's end. The tricky part? Determining whether the queue is full or empty, since both conditions can look identical when front == rear.

Handling Full and Empty Conditions

There are two common approaches:

1. Sacrifice One Slot

Keep one array slot permanently unused. The queue is:

  • Empty when front == rear
  • Full when (rear + 1) % capacity == front

This wastes one slot but makes the logic simple.

2. Use a Counter

Track the number of elements separately. The queue is:

  • Empty when count == 0
  • Full when count == capacity

Implementing Enqueue

To add an element:

  1. Check if the queue is full
  2. Insert the element at rear
  3. Move rear forward using rear = (rear + 1) % capacity
  4. If using a counter, increment count

Implementing Dequeue

To remove an element:

  1. Check if the queue is empty
  2. Retrieve the element at front
  3. Move front forward using front = (front + 1) % capacity
  4. If using a counter, decrement count

The Modulo Magic

The % capacity operation is what makes it circular—when a pointer reaches the end (index capacity - 1), adding 1 and taking modulo wraps it back to 0.

Key Takeaway: Circular queues use modulo arithmetic to wrap pointers and require special logic (sacrificed slot or counter) to distinguish between full and empty states.