622. Design Circular Queue Solution

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

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

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

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

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

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

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

The problem

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.

Python

class MyCircularQueue:
    def __init__(self, k: int):
        self.queue = [0] * k
        self.front = 0
        self.rear = -1
        self.curSize = 0
        self.maxSize = k

    def enQueue(self, value: int) -> bool:
        if self.isFull():
            return False
        self.rear = (self.rear + 1) % self.maxSize
        self.queue[self.rear] = value
        self.curSize += 1
        return True

    def deQueue(self) -> bool:
        if self.isEmpty():
            return False
        self.front = (self.front + 1) % self.maxSize
        self.curSize -= 1
        return True

    def Front(self) -> int:
        if self.isEmpty():
            return -1
        return self.queue[self.front]

    def Rear(self) -> int:
        if self.isEmpty():
            return -1
        return self.queue[self.rear]

    def isEmpty(self) -> bool:
        return self.curSize == 0

    def isFull(self) -> bool:
        return self.curSize == self.maxSize

Java

class MyCircularQueue {
    private int[] queue;
    private int front, rear, curSize, maxSize;

    public MyCircularQueue(int k) {
        queue = new int[k];
        front = 0;
        rear = -1;
        curSize = 0;
        maxSize = k;
    }

    public boolean enQueue(int value) {
        if (isFull()) return false;
        rear = (rear + 1) % maxSize;
        queue[rear] = value;
        curSize++;
        return true;
    }

    public boolean deQueue() {
        if (isEmpty()) return false;
        front = (front + 1) % maxSize;
        curSize--;
        return true;
    }

    public int Front() {
        return isEmpty() ? -1 : queue[front];
    }

    public int Rear() {
        return isEmpty() ? -1 : queue[rear];
    }

    public boolean isEmpty() {
        return curSize == 0;
    }

    public boolean isFull() {
        return curSize == maxSize;
    }
}

C++

#include <vector>
class MyCircularQueue {
private:
    std::vector<int> queue;
    int front, rear, curSize, maxSize;
public:
    MyCircularQueue(int k) : queue(k), front(0), rear(-1), curSize(0), maxSize(k) {}

    bool enQueue(int value) {
        if (isFull()) return false;
        rear = (rear + 1) % maxSize;
        queue[rear] = value;
        curSize++;
        return true;
    }

    bool deQueue() {
        if (isEmpty()) return false;
        front = (front + 1) % maxSize;
        curSize--;
        return true;
    }

    int Front() {
        return isEmpty() ? -1 : queue[front];
    }

    int Rear() {
        return isEmpty() ? -1 : queue[rear];
    }

    bool isEmpty() {
        return curSize == 0;
    }

    bool isFull() {
        return curSize == maxSize;
    }
};

JavaScript

class MyCircularQueue {
    constructor(k) {
        this.queue = new Array(k).fill(0);
        this.front = 0;
        this.rear = -1;
        this.curSize = 0;
        this.maxSize = k;
    }

    enQueue(value) {
        if (this.isFull()) return false;
        this.rear = (this.rear + 1) % this.maxSize;
        this.queue[this.rear] = value;
        this.curSize++;
        return true;
    }

    deQueue() {
        if (this.isEmpty()) return false;
        this.front = (this.front + 1) % this.maxSize;
        this.curSize--;
        return true;
    }

    Front() {
        if (this.isEmpty()) return -1;
        return this.queue[this.front];
    }

    Rear() {
        if (this.isEmpty()) return -1;
        return this.queue[this.rear];
    }

    isEmpty() {
        return this.curSize === 0;
    }

    isFull() {
        return this.curSize === this.maxSize;
    }
}

#include <stdbool.h>

typedef struct {
    int *queue;
    int front;
    int rear;
    int maxSize;
    int curSize;
} MyCircularQueue;

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj = (MyCircularQueue*) malloc(sizeof(MyCircularQueue));
    obj->queue = (int*) malloc(k * sizeof(int));
    obj->front = 0;
    obj->rear = -1;
    obj->maxSize = k;
    obj->curSize = 0;
    return obj;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if (obj->curSize == obj->maxSize)
        return false;
    obj->rear = (obj->rear + 1) % obj->maxSize;
    obj->queue[obj->rear] = value;
    obj->curSize++;
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if (obj->curSize == 0)
        return false;
    obj->front = (obj->front + 1) % obj->maxSize;
    obj->curSize--;
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
    if (obj->curSize == 0)
        return -1;
    return obj->queue[obj->front];
}

int myCircularQueueRear(MyCircularQueue* obj) {
    if (obj->curSize == 0)
        return -1;
    return obj->queue[obj->rear];
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->curSize == 0;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return obj->curSize == obj->maxSize;
}

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->queue);
    free(obj);
}

public class MyCircularQueue {
    private int[] queue;
    private int front, rear, curSize, maxSize;

    public MyCircularQueue(int k) {
        queue = new int[k];
        front = 0;
        rear = -1;
        curSize = 0;
        maxSize = k;
    }

    public bool EnQueue(int value) {
        if (IsFull()) return false;
        rear = (rear + 1) % maxSize;
        queue[rear] = value;
        curSize++;
        return true;
    }

    public bool DeQueue() {
        if (IsEmpty()) return false;
        front = (front + 1) % maxSize;
        curSize--;
        return true;
    }

    public int Front() {
        return IsEmpty() ? -1 : queue[front];
    }

    public int Rear() {
        return IsEmpty() ? -1 : queue[rear];
    }

    public bool IsEmpty() {
        return curSize == 0;
    }

    public bool IsFull() {
        return curSize == maxSize;
    }
}

This Python solution implements the circular queue using a list. The queue is initialized with a fixed size [0] * k. The enQueue method adds values, and deQueue removes them, both utilizing modular arithmetic to wrap around. Methods Front and Rear return the first and last elements, respectively.

Complexity

The time complexity for operations such as enQueue, deQueue, Front, and Rear is O(1) because they involve simple pointer arithmetic. The space complexity is O(k) due to the array used to store the elements.

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.

Python

class Node:
    def __init__(self, value=None):
        self.value = value
        self.next = None

class MyCircularQueue:
    def __init__(self, k: int):
        self.front = None
        self.rear = None
        self.maxSize = k
        self.curSize = 0

    def enQueue(self, value: int) -> bool:
        if self.isFull():
            return False
        newNode = Node(value)
        if self.curSize == 0:
            self.front = self.rear = newNode
            self.rear.next = self.front
        else:
            self.rear.next = newNode
            self.rear = newNode
            self.rear.next = self.front
        self.curSize += 1
        return True

    def deQueue(self) -> bool:
        if self.isEmpty():
            return False
        if self.front == self.rear:
            self.front = self.rear = None
        else:
            self.front = self.front.next
            self.rear.next = self.front
        self.curSize -= 1
        return True

    def Front(self) -> int:
        if self.isEmpty():
            return -1
        return self.front.value

    def Rear(self) -> int:
        if self.isEmpty():
            return -1
        return self.rear.value

    def isEmpty(self) -> bool:
        return self.curSize == 0

    def isFull(self) -> bool:
        return self.curSize == self.maxSize

Java

class Node {
    int value;
    Node next;
    Node(int value) {
        this.value = value;
    }
}

class MyCircularQueue {
    private Node front, rear;
    private int maxSize;
    private int curSize;

    public MyCircularQueue(int k) {
        front = rear = null;
        maxSize = k;
        curSize = 0;
    }

    public boolean enQueue(int value) {
        if (isFull()) return false;
        Node newNode = new Node(value);
        if (curSize == 0) {
            front = rear = newNode;
            rear.next = front;
        } else {
            rear.next = newNode;
            rear = newNode;
            rear.next = front;
        }
        curSize++;
        return true;
    }

    public boolean deQueue() {
        if (isEmpty()) return false;
        if (front == rear) {
            front = rear = null;
        } else {
            front = front.next;
            rear.next = front;
        }
        curSize--;
        return true;
    }

    public int Front() {
        if (isEmpty()) return -1;
        return front.value;
    }

    public int Rear() {
        if (isEmpty()) return -1;
        return rear.value;
    }

    public boolean isEmpty() {
        return curSize == 0;
    }

    public boolean isFull() {
        return curSize == maxSize;
    }
}

C++

#include <cstddef>

class Node {
public:
    int value;
    Node* next;
    Node(int val) : value(val), next(nullptr) {}
};

class MyCircularQueue {
private:
    Node* front;
    Node* rear;
    int maxSize;
    int curSize;

public:
    MyCircularQueue(int k) : front(nullptr), rear(nullptr), maxSize(k), curSize(0) {}

    bool enQueue(int value) {
        if (isFull()) return false;
        Node* newNode = new Node(value);
        if (curSize == 0) {
            front = rear = newNode;
            rear->next = front;
        } else {
            rear->next = newNode;
            rear = newNode;
            rear->next = front;
        }
        curSize++;
        return true;
    }

    bool deQueue() {
        if (isEmpty()) return false;
        if (front == rear) {
            delete front;
            front = rear = nullptr;
        } else {
            Node* temp = front;
            front = front->next;
            rear->next = front;
            delete temp;
        }
        curSize--;
        return true;
    }

    int Front() {
        if (isEmpty()) return -1;
        return front->value;
    }

    int Rear() {
        if (isEmpty()) return -1;
        return rear->value;
    }

    bool isEmpty() {
        return curSize == 0;
    }

    bool isFull() {
        return curSize == maxSize;
    }
};

JavaScript

class Node {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}

class MyCircularQueue {
    constructor(k) {
        this.front = null;
        this.rear = null;
        this.maxSize = k;
        this.curSize = 0;
    }

    enQueue(value) {
        if (this.isFull()) return false;
        const newNode = new Node(value);
        if (this.curSize === 0) {
            this.front = this.rear = newNode;
            this.rear.next = this.front;
        } else {
            this.rear.next = newNode;
            this.rear = newNode;
            this.rear.next = this.front;
        }
        this.curSize++;
        return true;
    }

    deQueue() {
        if (this.isEmpty()) return false;
        if (this.front === this.rear) {
            this.front = this.rear = null;
        } else {
            this.front = this.front.next;
            this.rear.next = this.front;
        }
        this.curSize--;
        return true;
    }

    Front() {
        if (this.isEmpty()) return -1;
        return this.front.value;
    }

    Rear() {
        if (this.isEmpty()) return -1;
        return this.rear.value;
    }

    isEmpty() {
        return this.curSize === 0;
    }

    isFull() {
        return this.curSize === this.maxSize;
    }
}

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct Node {
    int value;
    struct Node* next;
} Node;

typedef struct {
    Node* front;
    Node* rear;
    int maxSize;
    int curSize;
} MyCircularQueue;

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->front = obj->rear = NULL;
    obj->maxSize = k;
    obj->curSize = 0;
    return obj;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if (obj->curSize == obj->maxSize)
        return false;
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->value = value;
    newNode->next = NULL;
    if (obj->curSize == 0) {
        obj->front = obj->rear = newNode;
        obj->rear->next = obj->front;
    } else {
        obj->rear->next = newNode;
        obj->rear = newNode;
        obj->rear->next = obj->front;
    }
    obj->curSize++;
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if (obj->curSize == 0)
        return false;
    Node* temp = obj->front;
    if (obj->front == obj->rear) {
        obj->front = obj->rear = NULL;
    } else {
        obj->front = obj->front->next;
        obj->rear->next = obj->front;
    }
    free(temp);
    obj->curSize--;
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) {
    if (obj->curSize == 0)
        return -1;
    return obj->front->value;
}

int myCircularQueueRear(MyCircularQueue* obj) {
    if (obj->curSize == 0)
        return -1;
    return obj->rear->value;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->curSize == 0;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return obj->curSize == obj->maxSize;
}

void myCircularQueueFree(MyCircularQueue* obj) {
    while (obj->curSize != 0) 
        myCircularQueueDeQueue(obj);
    free(obj);
}

public class Node {
    public int value;
    public Node next;
    public Node(int value) {
        this.value = value;
    }
}

public class MyCircularQueue {
    private Node front, rear;
    private int maxSize;
    private int curSize;

    public MyCircularQueue(int k) {
        front = rear = null;
        maxSize = k;
        curSize = 0;
    }

    public bool EnQueue(int value) {
        if (IsFull()) return false;
        Node newNode = new Node(value);
        if (curSize == 0) {
            front = rear = newNode;
            rear.next = front;
        } else {
            rear.next = newNode;
            rear = newNode;
            rear.next = front;
        }
        curSize++;
        return true;
    }

    public bool DeQueue() {
        if (IsEmpty()) return false;
        if (front == rear) {
            front = rear = null;
        } else {
            front = front.next;
            rear.next = front;
        }
        curSize--;
        return true;
    }

    public int Front() {
        if (IsEmpty()) return -1;
        return front.value;
    }

    public int Rear() {
        if (IsEmpty()) return -1;
        return rear.value;
    }

    public bool IsEmpty() {
        return curSize == 0;
    }

    public bool IsFull() {
        return curSize == maxSize;
    }
}

This Python implementation uses a class Node for each node in the queue, with logic to manage linkage within MyCircularQueue. The dynamic nature of the circular linked list allows flexible sizing, managed by node reference updates in methods. The circular reference is maintained by next pointers.

Complexity

With consistent O(1) operations, time complexity remains efficient, and a space complexity of O(k) allows flexibility in memory usage compared to arrays.

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).

TypeScript

class MyCircularQueue {
    private queue: number[];
    private left: number;
    private right: number;
    private capacity: number;

    constructor(k: number) {
        this.queue = new Array(k);
        this.left = 0;
        this.right = 0;
        this.capacity = k;
    }

    enQueue(value: number): boolean {
        if (this.isFull()) {
            return false;
        }
        this.queue[this.right % this.capacity] = value;
        this.right++;
        return true;
    }

    deQueue(): boolean {
        if (this.isEmpty()) {
            return false;
        }
        this.left++;
        return true;
    }

    Front(): number {
        if (this.isEmpty()) {
            return -1;
        }
        return this.queue[this.left % this.capacity];
    }

    Rear(): number {
        if (this.isEmpty()) {
            return -1;
        }
        return this.queue[(this.right - 1) % this.capacity];
    }

    isEmpty(): boolean {
        return this.right - this.left === 0;
    }

    isFull(): boolean {
        return this.right - this.left === this.capacity;
    }
}

/**
 * Your MyCircularQueue object will be instantiated and called as such:
 * var obj = new MyCircularQueue(k)
 * var param_1 = obj.enQueue(value)
 * var param_2 = obj.deQueue()
 * var param_3 = obj.Front()
 * var param_4 = obj.Rear()
 * var param_5 = obj.isEmpty()
 * var param_6 = obj.isFull()
 */

type MyCircularQueue struct {
	front    int
	size     int
	capacity int
	q        []int
}

func Constructor(k int) MyCircularQueue {
	q := make([]int, k)
	return MyCircularQueue{0, 0, k, q}
}

func (this *MyCircularQueue) EnQueue(value int) bool {
	if this.IsFull() {
		return false
	}
	idx := (this.front + this.size) % this.capacity
	this.q[idx] = value
	this.size++
	return true
}

func (this *MyCircularQueue) DeQueue() bool {
	if this.IsEmpty() {
		return false
	}
	this.front = (this.front + 1) % this.capacity
	this.size--
	return true
}

func (this *MyCircularQueue) Front() int {
	if this.IsEmpty() {
		return -1
	}
	return this.q[this.front]
}

func (this *MyCircularQueue) Rear() int {
	if this.IsEmpty() {
		return -1
	}
	idx := (this.front + this.size - 1) % this.capacity
	return this.q[idx]
}

func (this *MyCircularQueue) IsEmpty() bool {
	return this.size == 0
}

func (this *MyCircularQueue) IsFull() bool {
	return this.size == this.capacity
}

/**
 * Your MyCircularQueue object will be instantiated and called as such:
 * obj := Constructor(k);
 * param_1 := obj.EnQueue(value);
 * param_2 := obj.DeQueue();
 * param_3 := obj.Front();
 * param_4 := obj.Rear();
 * param_5 := obj.IsEmpty();
 * param_6 := obj.IsFull();
 */

Rust

struct MyCircularQueue {
    q: Vec<i32>,
    size: usize,
    capacity: usize,
    front: usize,
}

impl MyCircularQueue {
    fn new(k: i32) -> Self {
        MyCircularQueue {
            q: vec![0; k as usize],
            size: 0,
            capacity: k as usize,
            front: 0,
        }
    }

    fn en_queue(&mut self, value: i32) -> bool {
        if self.is_full() {
            return false;
        }
        let rear = (self.front + self.size) % self.capacity;
        self.q[rear] = value;
        self.size += 1;
        true
    }

    fn de_queue(&mut self) -> bool {
        if self.is_empty() {
            return false;
        }
        self.front = (self.front + 1) % self.capacity;
        self.size -= 1;
        true
    }

    fn front(&self) -> i32 {
        if self.is_empty() {
            -1
        } else {
            self.q[self.front]
        }
    }

    fn rear(&self) -> i32 {
        if self.is_empty() {
            -1
        } else {
            let rear = (self.front + self.size - 1) % self.capacity;
            self.q[rear]
        }
    }

    fn is_empty(&self) -> bool {
        self.size == 0
    }

    fn is_full(&self) -> bool {
        self.size == self.capacity
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Approach 1: Using an Array with Two Pointers	The time complexity for operations such as `enQueue`, `deQueue`, `Front`, and `Rear` is O(1) because they involve simple pointer arithmetic. The space complexity is O(k) due to the array used to store the elements.
Approach 2: Using a Circular Linked List	With consistent O(1) operations, time complexity remains efficient, and a space complexity of O(k) allows flexibility in memory usage compared to arrays.
Array Simulation	–

Complexity analysis

Approach	Time	Space	When to Use
Array with Two Pointers	O(1) per operation	O(k)	Best choice when capacity is fixed and high performance is required
Circular Linked List	O(1) per operation	O(k)	Useful when demonstrating pointer-based queue design or dynamic allocation

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.

Design Circular Queue solution and explanation

The problem

Approach overview

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

Approach 2: Approach 2: Using a Circular Linked List

Approach 3: Array Simulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Design Circular Queue solution and explanation

The problem

Approach overview

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

Approach 2: Approach 2: Using a Circular Linked List

Approach 3: Array Simulation

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems