Skip to main content
Talentd

Design Circular Queue - Solution & Explanation

MediumArrayLinked ListDesignQueue32 min readAsked at: Amazon, Microsoft, Apple +18
Practice this problem

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.
  • 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 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.
  • 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:

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
myCircularQueue.Rear();     // return 3
myCircularQueue.isFull();   // return True
myCircularQueue.deQueue();  // return True
myCircularQueue.enQueue(4); // return True
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.

Approach Overview

Problem Overview: Design a fixed-size circular queue that supports enQueue, deQueue, Front, Rear, isEmpty, and isFull. The key constraint is circular behavior: when the end of the storage is reached, the queue should wrap around and reuse empty space at the beginning.

Approach 1: Using an Array with Two Pointers (Time: O(1), Space: O(k))

This approach stores elements in a fixed-size array and tracks positions using two indices: front and rear. When inserting or removing elements, you update these pointers using modulo arithmetic ((index + 1) % k) so they wrap around the array. A separate counter or size variable helps determine whether the queue is full or empty. All operations—insert, delete, and peek—run in constant time because they only involve index updates. This design is common in system-level implementations of queue structures and works well when the capacity is known in advance.

Approach 2: Using a Circular Linked List (Time: O(1), Space: O(k))

Instead of a fixed array, this method uses nodes connected in a circular linked list. The tail node points back to the head, forming a loop. You maintain references to the head, tail, and a size counter. Insertion attaches a new node after the tail and updates the circular link, while deletion moves the head pointer forward. Because pointer adjustments are constant-time operations, every queue operation still runs in O(1). This approach is useful when demonstrating dynamic memory management or when implementing custom data structure design problems.

Recommended for interviews: The array-based circular buffer is the expected solution. Interviewers typically want to see correct pointer movement with modulo arithmetic and accurate handling of full vs empty states. Implementing the circular linked list shows deeper data structure understanding, but the array approach is simpler, faster in practice due to cache locality, and widely used in production systems.

Approach 1: Approach 1: Using an Array with Two Pointers

This approach utilizes a fixed-size array along with two pointers (or indices), front and rear, to maintain the positions within the queue effectively. The idea revolves around using modular arithmetic to effectively wrap around the queue once the end of the array is reached.

Operations like enQueue and deQueue are performed using these pointers, and conditions such as when the queue is full or empty are checked based on the relative position of these pointers.

This C solution defines a structure MyCircularQueue containing an array and variables to keep track of the front, rear, current size, and maximum size. myCircularQueueCreate allocates memory and initializes the queue. The enQueue function checks if the queue is full, updates the rear pointer, and inserts the element. deQueue function checks if the queue is empty and updates the front pointer. Front and rear position values are obtained by accessing respective pointers.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

The time complexity for each operation such as enQueue, deQueue, Front, and Rear is O(1) as they involve simple arithmetic operations. The space complexity is O(k) where k is the size of the queue since we're using a static array.

Try this approach in the editor →

Approach 2: Approach 2: Using a Circular Linked List

This approach employs a circular linked list to implement the queue, leveraging linked nodes instead of a fixed-size array. The circular nature simplifies the wrap-around, allowing operations with dynamic sizing. Each node in the list holds a value and a reference to the next node, with the last node pointing back to the first, forming a circle.

Such a design accommodates flexible sizing but adds complexity in managing node references for enQueue and deQueue.

This C solution uses a circular linked list wherein each Node structure holds a value and a next pointer. The MyCircularQueue structure stores front and rear Node pointers along with size information. Insertion (enQueue) and deletion (deQueue) manage node links and pointers accordingly. Circular nature is handled by pointing the last node to the front node.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

The time complexity for each operation is O(1) since they only involve rearranging node pointers. The space complexity is O(k) in the worst case if all queue slots are occupied.

Try this approach in the editor →

Approach 3: Array Simulation

We can use an array q of length k to simulate a circular queue, with a pointer front to record the position of the front element. Initially, the queue is empty, and front is 0. Additionally, we use a variable size to record the number of elements in the queue, initially size is 0.

When calling the enQueue method, we first check if the queue is full, i.e., size = k. If it is full, we return false. Otherwise, we insert the element at position (front + size) bmod k, then size = size + 1, indicating that the number of elements in the queue has increased by 1. Finally, we return true.

When calling the deQueue method, we first check if the queue is empty, i.e., size = 0. If it is empty, we return false. Otherwise, we set front = (front + 1) bmod k, indicating that the front element has been dequeued, then size = size - 1.

When calling the Front method, we first check if the queue is empty, i.e., size = 0. If it is empty, we return -1. Otherwise, we return q[front].

When calling the Rear method, we first check if the queue is empty, i.e., size = 0. If it is empty, we return -1. Otherwise, we return q[(front + size - 1) bmod k].

When calling the isEmpty method, we simply check if size = 0.

When calling the isFull method, we simply check if size = k.

In terms of time complexity, the above operations all have a time complexity of O(1). The space complexity is O(k).

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Using an Array with Two Pointers

The time complexity for each operation such as enQueue, deQueue, Front, and Rear is O(1) as they involve simple arithmetic operations. The space complexity is O(k) where k is the size of the queue since we're using a static array.

Approach 2: Using a Circular Linked List

The time complexity for each operation is O(1) since they only involve rearranging node pointers. The space complexity is O(k) in the worst case if all queue slots are occupied.

Array Simulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Array with Two PointersO(1) per operationO(k)Best choice when capacity is fixed and high performance is required
Circular Linked ListO(1) per operationO(k)Useful when demonstrating pointer-based queue design or dynamic allocation

Video Solution

Design Circular Queue - Leetcode 622 - Python • NeetCode • 40,582 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Design Circular Queue easy or hard?
Design Circular Queue is considered a medium-level problem. The logic is straightforward once you understand circular indexing, but many candidates struggle with edge cases like detecting full versus empty states and correctly updating pointers.
Design Circular Queue Python/Java solution
In Python or Java, the typical solution defines a class with an array of size k, front and rear indices, and a size counter. Methods update indices using (index + 1) % k for circular movement, ensuring all operations run in constant time.
How to solve Design Circular Queue in O(1)?
Use a fixed-size array and maintain two pointers: front and rear. Update these indices with modulo arithmetic so they wrap around the array when reaching the end. Keep a size counter to detect full and empty states, ensuring every operation executes in constant time.
What is the best approach for Design Circular Queue?
The array-based circular buffer with two pointers is the most common approach. It maintains front and rear indices and uses modulo arithmetic to wrap around the array. All operations such as enQueue, deQueue, Front, and Rear run in O(1) time with O(k) space for the queue capacity.
Is Design Circular Queue asked at Google/Amazon/Meta?
Circular queue design problems appear in interviews at companies like Amazon, Google, and Microsoft, especially for roles that test data structure fundamentals. The problem evaluates understanding of queues, modular arithmetic, and edge-case handling in data structure design.
What data structure is used in Design Circular Queue?
The problem can be implemented using either a fixed-size array acting as a circular buffer or a circular linked list. The array approach uses index arithmetic to wrap around, while the linked list version connects the tail node back to the head.
What is the time complexity of Design Circular Queue?
Each operation—enQueue, deQueue, Front, Rear, isEmpty, and isFull—runs in O(1) time. The implementation only updates indices or pointers without iterating through the structure. Space complexity is O(k), where k is the maximum capacity of the queue.

Ready to solve this problem?

Practice Design Circular Queue with our built-in code editor and test cases.

Practice on FleetCode
Previous

Design Circular Deque

Next

Design Front Middle Back Queue