Faangprep Logo
Log inStart free
Browse curriculum

Circular Queue

A circular queue is a fixed-size queue that reuses empty slots at the beginning when the end is reached.

0 / 8 used

READY

 

Empty queue. Both front and rear sit at -1 until something is enqueued.

 

Value

Intuition

A standard array-based queue has a major flaw: as you dequeue items, the 'front' moves forward, leaving unused empty space at the beginning. A Circular Queue connects the end back to the beginning, forming a circle. This ensures no space is wasted.

Think of it as a Ring Buffer used in traffic light controllers or CPU scheduling.

Concept

It utilizes modular arithmetic logic: next_index = (current_index + 1) % capacity.

  • Front: Index of the first element.
  • Rear: Index of the last element.
  • Full Condition: (rear + 1) % capacity == front
  • Empty Condition: front == -1

How it Works

When you seek to enqueue an element:

  • Check if full. If not, calculate new rear: (rear + 1) % size.
  • Insert data.

When you dequeue:

  • Check if empty. If not, retrieve data at front.
  • Move front: (front + 1) % size.
  • If front passes rear (queue becomes empty), reset both to -1.

Step-by-Step Breakdown

  1. Enqueue 10: Rear moves from -1 to 0. Arr[0] = 10.
  2. Enqueue 20: Rear moves to 1. Arr[1] = 20.
  3. Dequeue: Front moves to 1. Space at 0 is potentially reusable.
  4. Wrap Around: If Rear is at index N-1 and index 0 is free, Rear wraps to 0.

When to Use

  • Memory Management: Buffering data streams (e.g., video buffering).
  • Traffic Systems: Cyclic round-robin scheduling.
  • Fixed Resource Pools: When total capacity is strictly limited.

When NOT to Use

  • When you need dynamically growing storage (use a Linked List or dynamic Deque).
  • When random access to the middle of the queue is required.

How to Identify

Problems asking for 'design a buffer', 'round robin', or 'moving average' over a fixed window size usually imply a Circular Queue/Buffer.

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description
Previous

Deque

Next

Priority Queue (ADT)

Frequently Asked Questions

Why use a Circular Queue?

A Circular Queue solves the "wasted space" problem in linear queues by reusing empty slots at the front through pointer wrap-around.

How do pointers wrap around?

Using the modulo operator (pointer + 1) % size, the pointers naturally wrap back to index 0 when they reach the end of the array.

Circular Queue vs Linear Queue?

Circular Queues provide better memory utilization for fixed-size buffers, making them ideal for streaming data.