Log inSign up
mediumLeetCodeNot Started

Design Circular Queue

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Queue
Solve on LeetCode
Lesson

Problem Statement

Design your implementation of the circular queue. The circular queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle, and the last position is connected back to the first position to make a circle. It is also called "Ring Buffer".

One of the benefits of the circular queue is that we can make use of the spaces in front of the queue. In a normal queue, once the queue becomes full, we cannot insert the next element even if there is a space in front of the queue. But using the circular queue, we can use the space to store new values.

Implement the MyCircularQueue class: - MyCircularQueue(k) Initializes the object with the size of the queue to be k. - boolean enQueue(int value) Inserts an element into the circular queue. Return true if the operation is successful. - boolean deQueue() Deletes an element from the circular queue. Return true if the operation is successful. - int Front() Gets the front item from the queue. If the queue is empty, return -1. - int Rear() Gets the last item from the queue. If the queue is empty, return -1. - boolean isEmpty() Checks whether the circular queue is empty or not. - boolean isFull() Checks whether the circular queue is full or not.

You must solve the problem without using the built-in queue data structure in your programming language.

Example 1 · Standard Circular Buffer Workflow:

Input: ["MyCircularQueue", "enQueue", "enQueue", "enQueue", "enQueue", "Rear", "isFull", "deQueue", "enQueue", "Rear"] [[3], [1], [2], [3], [4], [], [], [], [4], []]
Output: [null, true, true, true, false, 3, true, true, true, 4]
Explanation: MyCircularQueue myCircularQueue = new MyCircularQueue(3); myCircularQueue.enQueue(1); // return True myCircularQueue.enQueue(2); // return True myCircularQueue.enQueue(3); // return True myCircularQueue.enQueue(4); // return False, queue is full myCircularQueue.Rear(); // return 3 myCircularQueue.isFull(); // return True myCircularQueue.deQueue(); // return True myCircularQueue.enQueue(4); // return True (wrapped around to index 0!) myCircularQueue.Rear(); // return 4

Constraints:

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

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Array Indexing
  • Modulo Arithmetic
  • Queue FIFO Mechanics

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master circular indexing with the modulo operator: (idx + 1) % K.
  • Resolve the classic empty-vs-full ring buffer ambiguity.
  • Understand why ring buffers are the standard in OS kernels, audio drivers, and networking pipelines.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Fixed buffer size with continuous streaming producer-consumer data.
  • Hardware buffer, audio stream, or network packet queuing where reallocation is forbidden.

Algorithmic Decision Tree:

  • Track head and count: Enqueue at (head + count) % capacity, increment count.
  • Dequeue by advancing head = (head + 1) % capacity, decrement count.

Connected Patterns:

Design Circular DequeMoving Average from Data StreamSliding Window Maximum

1. Brute Force — Dynamic Array with Inefficient Shift

Intuition

Store elements in a list. When an element is removed from the front, shift all remaining elements left to maintain index 0 as head.

Algorithm

  1. Step 1: On enQueue(x), append x if size < K.
  2. Step 2: On deQueue(), remove element at index 0 and shift subsequent elements left.
  3. Step 3: Front is at index 0, Rear is at index size - 1.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class MyCircularQueue {
7private:
8 vector<int> data;
9 int capacity;
10public:
11 MyCircularQueue(int k) : capacity(k) {}
12
13 bool enQueue(int value) {
14 if (data.size() == capacity) return false;
15 data.push_back(value);
16 return true;
17 }
18
19 bool deQueue() {
20 if (data.empty()) return false;
21 data.erase(data.begin());
22 return true;
23 }
24
25 int Front() {
26 return data.empty() ? -1 : data.front();
27 }
28
29 int Rear() {
30 return data.empty() ? -1 : data.back();
31 }
32
33 bool isEmpty() {
34 return data.empty();
35 }
36
37 bool isFull() {
38 return data.size() == capacity;
39 }
40};
41
42int main() {
43 MyCircularQueue q(3);
44 cout << q.enQueue(1) << endl; // 1
45 cout << q.enQueue(2) << endl; // 1
46 cout << q.enQueue(3) << endl; // 1
47 cout << q.enQueue(4) << endl; // 0 (full)
48 cout << q.Rear() << endl; // 3
49 cout << q.deQueue() << endl; // 1
50 cout << q.enQueue(4) << endl; // 1
51 cout << q.Rear() << endl; // 4
52 return 0;
53}

Time & Space Complexity

  • Time complexity: enQueue: O(1), deQueue: O(N) — Shifting elements left on every dequeue takes O(N) linear time.
  • Space complexity: O(K) — Stores at most K elements in array.

Why Brute Force Doesn't Scale:

In real-time audio/packet processing, dynamic allocation or O(N) copying causes audio stuttering or packet loss.

Fixed array ring buffers process millions of operations per second with microsecond predictability.

2. Better — Doubly Linked List Implementation

Intuition

Use sentinel head and tail nodes in a doubly linked list to insert at tail and remove from head in O(1) time without index wrapping.

Algorithm

  1. Step 1: Maintain dummy head and tail sentinel nodes and track current count.
  2. Step 2: enQueue(val): If count < capacity, create a new Node and insert right before dummy tail.
  3. Step 3: deQueue(): If count > 0, remove the node immediately following dummy head.
  4. Step 4: Front() returns head.next.val, Rear() returns tail.prev.val.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5struct Node {
6 int val;
7 Node* next;
8 Node* prev;
9 Node(int v) : val(v), next(nullptr), prev(nullptr) {}
10};
11
12class MyCircularQueue {
13private:
14 Node* head;
15 Node* tail;
16 int capacity;
17 int count;
18
19public:
20 MyCircularQueue(int k) : capacity(k), count(0) {
21 head = new Node(0);
22 tail = new Node(0);
23 head->next = tail;
24 tail->prev = head;
25 }
26
27 bool enQueue(int value) {
28 if (count == capacity) return false;
29 Node* node = new Node(value);
30 node->prev = tail->prev;
31 node->next = tail;
32 tail->prev->next = node;
33 tail->prev = node;
34 count++;
35 return true;
36 }
37
38 bool deQueue() {
39 if (count == 0) return false;
40 Node* toDelete = head->next;
41 head->next = toDelete->next;
42 toDelete->next->prev = head;
43 delete toDelete;
44 count--;
45 return true;
46 }
47
48 int Front() {
49 return count == 0 ? -1 : head->next->val;
50 }
51
52 int Rear() {
53 return count == 0 ? -1 : tail->prev->val;
54 }
55
56 bool isEmpty() {
57 return count == 0;
58 }
59
60 bool isFull() {
61 return count == capacity;
62 }
63};
64
65int main() {
66 MyCircularQueue q(2);
67 cout << q.enQueue(5) << endl; // 1
68 cout << q.enQueue(6) << endl; // 1
69 cout << q.Front() << endl; // 5
70 cout << q.Rear() << endl; // 6
71 return 0;
72}

Time & Space Complexity

  • Time complexity: All operations O(1) — Direct pointer manipulation for head and tail updates in O(1) time.
  • Space complexity: O(K) Node Overhead — Dynamic node allocations consume pointer space per element.

3. Optimal — Fixed-Size Array with Modulo Indexing

Intuition

Use a fixed array queue[k], pointer headIndex, and counter count. New elements land at (headIndex + count) % k. Dequeue advances headIndex = (headIndex + 1) % k.

Algorithm

  1. Step 1: Initialize an array q of capacity k, head = 0, and count = 0.
  2. Step 2: enQueue(val): Check if (count == k) return false. Else place at q[(head + count) % k], increment count.
  3. Step 3: deQueue(): Check if (count == 0) return false. Else update head = (head + 1) % k, decrement count.
  4. Step 4: Front(): Return count == 0 ? -1 : q[head].
  5. Step 5: Rear(): Return count == 0 ? -1 : q[(head + count - 1) % k].

Modulo Ring Buffer Execution Trace

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
head=0, count=3
Visual state
Values and pointers at this exact step
queue
FRONT → REAR
1 (idx 0)
2 (idx 1)
3 (idx 2)
Enqueue adds at the rear · Dequeue removes from the front
Decision / next transition
enQueue(1), enQueue(2), enQueue(3)
Why this step matters

head=0, count=3. Ring buffer full.

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class MyCircularQueue {
7private:
8 vector<int> q;
9 int head;
10 int count;
11 int capacity;
12
13public:
14 MyCircularQueue(int k) : capacity(k), head(0), count(0), q(k) {}
15
16 bool enQueue(int value) {
17 if (isFull()) return false;
18 q[(head + count) % capacity] = value;
19 count++;
20 return true;
21 }
22
23 bool deQueue() {
24 if (isEmpty()) return false;
25 head = (head + 1) % capacity;
26 count--;
27 return true;
28 }
29
30 int Front() {
31 if (isEmpty()) return -1;
32 return q[head];
33 }
34
35 int Rear() {
36 if (isEmpty()) return -1;
37 return q[(head + count - 1) % capacity];
38 }
39
40 bool isEmpty() {
41 return count == 0;
42 }
43
44 bool isFull() {
45 return count == capacity;
46 }
47};
48
49int main() {
50 MyCircularQueue cq(3);
51 cout << cq.enQueue(1) << endl; // 1 (true)
52 cout << cq.enQueue(2) << endl; // 1 (true)
53 cout << cq.enQueue(3) << endl; // 1 (true)
54 cout << cq.enQueue(4) << endl; // 0 (false)
55 cout << cq.Rear() << endl; // 3
56 cout << cq.isFull() << endl; // 1 (true)
57 cout << cq.deQueue() << endl; // 1 (true)
58 cout << cq.enQueue(4) << endl; // 1 (true)
59 cout << cq.Rear() << endl; // 4
60 return 0;
61}

Time & Space Complexity

  • Time complexity: All operations O(1) — Every operation computes direct array indices using arithmetic operations in O(1) time.
  • Space complexity: O(K) (Contiguous Memory) — Pre-allocates an array of fixed size K with zero dynamic node overhead.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Dynamic Array with ShiftingenQueue: O(1), deQueue: O(N)O(K)Use a regular array. On deQueue, shift all remaining elements left by 1 position.Linear shifting on dequeue.
2.Better — Doubly Linked List with Sentinel NodesAll operations O(1)O(K) (Node Allocation Overhead)Store elements in dynamic doubly linked list nodes up to capacity K.Heap memory allocation per node.
3.Optimal — Fixed Array with Modulo Indexing & CountOptimalAll operations O(1)O(K) (Contiguous Memory)Pre-allocate a fixed array of size K. Compute head and rear via modulo arithmetic with count tracking.None. Direct index arithmetic.

Common Pitfalls & Crucial Edge Cases

Using (head == tail) for both empty and full

Without a count variable or an extra empty slot, head == tail is ambiguous between 0 elements and K elements.

Negative modulo in C++

In C++, -1 % k is -1, not k - 1. Always add k before modulo: (idx + k) % k.

Crucial Edge Cases to Validate:

  • Queue with capacity k = 1 — Must handle single-element push, pop, full, and empty transitions without index out of bounds.
  • Rear() calculation when rear wraps around index 0 — (head + count - 1 + capacity) % capacity avoids negative indices in languages like C++/Java.
  • Repeated enQueue and deQueue cycles — Validates that head pointer continuously cycles indefinitely.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Clarify whether thread safety is needed: ring buffers are popular for lock-free single-producer single-consumer queues (SPSC).
  2. Explain the choice of count variable vs wasting one slot ((tail + 1) % capacity == head).
  3. Point out that this data structure is the foundation of network socket buffers, Linux ring buffers, and circular logging.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the formula for the rear element index when tracking head and count?

2.Why does the fixed-array modulo approach outperform the doubly linked list?

3.What happens during deQueue() in a circular queue?

Back to DSA Sheet