thesarfo

Reference

Circular Queue

How wrapping REAR and FRONT around the end of the array solves a simple queue's wasted-space problem.

views 0

In a circular queue, the last element points back to the first, forming a circular link.

The main advantage over a simple queue is better memory utilization: if the last position is full and the first position is empty, a new element can still be inserted at the first position — not possible in a simple queue, where a run of insertions and deletions leaves unusable empty space at the front.

Operations

  1. Two pointers, FRONT and REAR, are used.
  2. FRONT tracks the first element.
  3. REAR tracks the last element.
  4. Initially, both are set to -1.

Enqueue

  1. Check if the queue is full.
  2. For the first element, set FRONT to 0.
  3. Circularly increase REAR by 1 (if REAR reaches the end, it wraps to the start).
  4. Add the new element at the position pointed to by REAR.

Dequeue

  1. Check if the queue is empty.
  2. Return the value pointed to by FRONT.
  3. Circularly increase FRONT by 1.
  4. For the last element, reset FRONT and REAR to -1.

Checking Full

The full check has an extra case beyond the simple queue:

  • Case 1: FRONT == 0 && REAR == SIZE - 1
  • Case 2: FRONT == REAR + 1

Case 2 happens when REAR wraps around to 0 and its value ends up just one less than FRONT.

Complexity

Enqueue and dequeue are both O(1) for the array implementation.