DSA problem

Design Circular Queue

MediumData Structure DesignPattern: Data Structure Designtop600AmazonMicrosoftAppleGoogleBloomberg

Design a circular queue (also called a ring buffer). A circular queue is a linear data structure that follows FIFO ordering and where the last position is connected back to the first to form a circle. Using a fixed-size array with this wrap-around behaviour avoids the linear-time shifting that a naive array queue suffers from when the front pointer advances.

Implement MyCircularQueue with these operations: MyCircularQueue(k) constructs the queue with capacity k. enQueue(value) inserts an element at the rear and returns true if successful (false if full). deQueue() removes the element at the front and returns true if successful (false if empty). Front() returns the front element or -1 if empty. Rear() returns the rear element or -1 if empty. isEmpty() and isFull() test the current state.

The canonical implementation stores three integers — head, tail, and size — alongside a fixed array of length k. head is the index of the front element, tail is the index where the next inserted element will go (i.e., one past the rear). Enqueue writes to data[tail] then advances tail = (tail + 1) % k; dequeue reads data[head] then advances head = (head + 1) % k. The explicit size counter cleanly disambiguates "empty" from "full" — a problem you would otherwise need to solve with a wasted slot or an extra flag.

All six operations are O(1) in both time and space, which is precisely why ring buffers are used everywhere from bounded producer/consumer queues to OS scheduling to lock-free single-producer/single-consumer pipelines.

Examples

Constraints

• 1 <= k <= 1000
• 0 <= value <= 1000
• At most 3000 calls will be made to enQueue, deQueue, Front, Rear, isEmpty, and isFull.

3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.

arraylinked-listdesignqueue

Browse all DSA problems