Design Circular Queue

Med

#0578Time: O(1) for all operations. Although the asymptotic complexity is constant time, the `enQueue` operation involves dynamic memory allocation (`new Node`), which can have a higher real-world cost than array-based implementations.Space: O(k), where k is the capacity. Each of the k elements requires a node object, which stores both the integer value and a memory pointer, leading to higher space consumption compared to a simple array.8 companies

Patterns

Design

Algorithms

Token Bucket

Data structures

Array Linked List Queue

Companies

Intuit Qualcomm Tesla Citadel

Prompt

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.

Approaches

2 approaches with complexity analysis and trade-offs.

A feasible, though less optimal, approach for a fixed-size queue is to use a singly linked list. This implementation requires pointers to the head and tail of the list to ensure O(1) enqueue and dequeue operations. We also need to manually track the current number of elements to check against the queue's capacity.

Algorithm

Node Class: Define a private inner class Node with an integer value and a Node next pointer.
Class Members: Maintain a head pointer, a tail pointer, an integer count for the current size, and an integer capacity for the maximum size.
MyCircularQueue(k): Initialize capacity to k, count to 0, and both head and tail to null.
enQueue(value):
1. Check if the queue is full (count == capacity). If so, return false.
2. Create a new Node(value).
3. If the queue is empty, set both head and tail to the new node.
4. Otherwise, set tail.next = newNode and then update tail = newNode.
5. Increment count and return true.
deQueue():
1. Check if the queue is empty (count == 0). If so, return false.
2. Move the head pointer forward: head = head.next.
3. Decrement count.
4. If the queue becomes empty after dequeuing (count == 0), set tail to null as well.
5. Return true.
Front(): If not empty, return head.value. Otherwise, return -1.
Rear(): If not empty, return tail.value. Otherwise, return -1.
isEmpty(): Return true if count == 0.
isFull(): Return true if count == capacity.

Walkthrough

This implementation uses a standard queue structure built upon a singly linked list. A Node class holds the data and a pointer to the next element. The MyCircularQueue class maintains a head pointer to the first node, a tail pointer to the last node, a count of the current elements, and the capacity.

enQueue(value): If the queue is not full (count < capacity), a new node is created. If the queue was empty, both head and tail point to this new node. Otherwise, the new node is linked after the current tail, and the tail pointer is updated to this new node. count is then incremented.
deQueue(): If the queue is not empty, the head pointer is simply advanced to the next node in the list, effectively removing the first element. count is decremented.

All operations rely on manipulating these pointers and the count variable, which allows them to be performed in constant time.

1class MyCircularQueue {2    private class Node {3        public int value;4        public Node next;5        public Node(int value) {6            this.value = value;7            this.next = null;8        }9    }10 11    private int capacity;12    private int count;13    private Node head;14    private Node tail;15 16    public MyCircularQueue(int k) {17        this.capacity = k;18        this.count = 0;19        this.head = null;20        this.tail = null;21    }22 23    public boolean enQueue(int value) {24        if (isFull()) {25            return false;26        }27        Node newNode = new Node(value);28        if (isEmpty()) {29            head = tail = newNode;30        } else {31            tail.next = newNode;32            tail = newNode;33        }34        count++;35        return true;36    }37 38    public boolean deQueue() {39        if (isEmpty()) {40            return false;41        }42        head = head.next;43        count--;44        if (isEmpty()) {45            tail = null;46        }47        return true;48    }49 50    public int Front() {51        if (isEmpty()) {52            return -1;53        }54        return head.value;55    }56 57    public int Rear() {58        if (isEmpty()) {59            return -1;60        }61        return tail.value;62    }63 64    public boolean isEmpty() {65        return count == 0;66    }67 68    public boolean isFull() {69        return count == capacity;70    }71}

Complexity

Time

O(1) for all operations. Although the asymptotic complexity is constant time, the `enQueue` operation involves dynamic memory allocation (`new Node`), which can have a higher real-world cost than array-based implementations.

Space

O(k), where k is the capacity. Each of the k elements requires a node object, which stores both the integer value and a memory pointer, leading to higher space consumption compared to a simple array.

Trade-offs

Pros

The logic is a straightforward extension of a standard unbounded queue.
Does not require complex index arithmetic with the modulo operator.

Cons

Higher memory overhead per element because each node stores both the value and a pointer.
Dynamic memory allocation for each enQueue operation can be slower in practice than a simple array write.
This implementation is a standard bounded queue, not a true 'ring buffer' where a fixed block of memory is reused circularly.

The most efficient and standard approach is to use a fixed-size array as a ring buffer. We use two pointers, head and tail, to mark the front of the queue and the next available insertion spot, respectively. The circular nature is achieved by using the modulo operator to wrap the pointers around the array's boundaries. A separate counter variable is used to easily distinguish between full and empty states.

Algorithm

Class Members: Use a fixed-size integer array queue, an integer capacity, two integer pointers head and tail, and an integer count to track the number of elements.
MyCircularQueue(k): Initialize the queue array with size k, set capacity to k, and initialize head, tail, and count to 0.
enQueue(value):
1. Check if the queue is full (count == capacity). If so, return false.
2. Store the value at the tail index: queue[tail] = value.
3. Advance the tail pointer, wrapping around if necessary: tail = (tail + 1) % capacity.
4. Increment count and return true.
deQueue():
1. Check if the queue is empty (count == 0). If so, return false.
2. Advance the head pointer, wrapping around: head = (head + 1) % capacity.
3. Decrement count and return true.
Front(): If not empty, return the element at the head index: queue[head].
Rear(): If not empty, return the element at the index before tail. This is calculated as queue[(tail - 1 + capacity) % capacity] to correctly handle wrap-around.
isEmpty(): Return true if count == 0.
isFull(): Return true if count == capacity.

Walkthrough

This method is the canonical implementation of a circular queue or ring buffer. It relies on a pre-allocated array and integer indices, making it very fast and memory-efficient.

queue: A fixed-size array that holds the queue elements.
head: An index that points to the first element in the queue.
tail: An index that points to the next open slot for insertion.
count: The current number of elements in the queue. Using a count variable is a simple and robust way to differentiate between an empty queue and a full queue, which can otherwise be ambiguous when head == tail.

The core of the circular logic is the modulo operator (%). When a pointer is incremented, we take it modulo the capacity ((pointer + 1) % capacity). This ensures that if the pointer goes past the last index, it wraps around to index 0.

enQueue: Adds an element at the tail index and advances tail.
deQueue: Advances the head index, effectively 'removing' the element without needing to shift other elements.
Rear: The last element added is located at the index right before the tail pointer. The expression (tail - 1 + capacity) % capacity correctly finds this index, even when tail is 0.

1class MyCircularQueue {2    private int[] queue;3    private int head;4    private int tail;5    private int count;6    private int capacity;7 8    public MyCircularQueue(int k) {9        this.capacity = k;10        this.queue = new int[k];11        this.head = 0;12        this.tail = 0;13        this.count = 0;14    }15 16    public boolean enQueue(int value) {17        if (isFull()) {18            return false;19        }20        queue[tail] = value;21        tail = (tail + 1) % capacity;22        count++;23        return true;24    }25 26    public boolean deQueue() {27        if (isEmpty()) {28            return false;29        }30        // The element at head is overwritten on a future enqueue31        head = (head + 1) % capacity;32        count--;33        return true;34    }35 36    public int Front() {37        if (isEmpty()) {38            return -1;39        }40        return queue[head];41    }42 43    public int Rear() {44        if (isEmpty()) {45            return -1;46        }47        // The last element is at the index before the current tail48        int rearIndex = (tail - 1 + capacity) % capacity;49        return queue[rearIndex];50    }51 52    public boolean isEmpty() {53        return count == 0;54    }55 56    public boolean isFull() {57        return count == capacity;58    }59}

Complexity

Time

O(1) for all operations. Each operation involves a few arithmetic calculations and direct array accesses, which are fundamental constant-time operations.

Space

O(k), where k is the capacity. This is the minimal space required to store k elements.

Trade-offs

Pros

Extremely fast due to direct, contiguous memory access (cache-friendly) and simple arithmetic operations.
Highly space-efficient, as it only requires memory for the array and a few integer variables.
No overhead from dynamic memory allocation during enqueue/dequeue operations.
Perfectly embodies the 'ring buffer' concept by reusing a fixed block of memory.

Cons

The size of the queue is fixed at initialization and cannot be changed later.

Solutions

Solution

1public class Design_Circular_Queue { class MyCircularQueue { int [] arr ; int size ; int capacity ; int front ; int back ; /** * Initialize your data structure here. Set the size of the queue to be k. */ public MyCircularQueue ( int k ) { arr = new int [ k ]; capacity = k ; size = 0 ; front = 0 ; back = - 1 ; } /** * Insert an element into the circular queue. Return true if the operation is successful. */ public boolean enQueue ( int value ) { if ( size == capacity ) { return false ; } ++ back ; arr [ back % arr . length ] = value ; ++ size ; return true ; } /** * Delete an element from the circular queue. Return true if the operation is successful. */ public boolean deQueue () { if ( size == 0 ) return false ; ++ front ; -- size ; return true ; } /** * Get the front item from the queue. */ public int Front () { if ( size == 0 ) return - 1 ; return arr [ front % arr . length ]; } /** * Get the last item from the queue. */ public int Rear () { if ( size == 0 ) return - 1 ; return arr [ back % arr . length ]; } /** * Checks whether the circular queue is empty or not. */ public boolean isEmpty () { return size == 0 ; } /** * Checks whether the circular queue is full or not. */ public boolean isFull () { return size == capacity ; } } } ############ class MyCircularQueue { private int [] q ; private int front ; private int size ; private int capacity ; public MyCircularQueue ( int k ) { q = new int [ k ]; capacity = k ; } public boolean enQueue ( int value ) { if ( isFull ()) { return false ; } int idx = ( front + size ) % capacity ; q [ idx ] = value ; ++ size ; return true ; } public boolean deQueue () { if ( isEmpty ()) { return false ; } front = ( front + 1 ) % capacity ; -- size ; return true ; } public int Front () { if ( isEmpty ()) { return - 1 ; } return q [ front ]; } public int Rear () { if ( isEmpty ()) { return - 1 ; } int idx = ( front + size - 1 ) % capacity ; return q [ idx ]; } public boolean isEmpty () { return size == 0 ; } public boolean isFull () { return size == capacity ; } } /** * Your MyCircularQueue object will be instantiated and called as such: * MyCircularQueue obj = new MyCircularQueue(k); * boolean param_1 = obj.enQueue(value); * boolean param_2 = obj.deQueue(); * int param_3 = obj.Front(); * int param_4 = obj.Rear(); * boolean param_5 = obj.isEmpty(); * boolean param_6 = obj.isFull(); */

1class MyCircularQueue : def __init__ ( self , k : int ): self . q = [ 0 ] * k self . front = 0 self . size = 0 self . capacity = k def enQueue ( self , value : int ) -> bool : if self . isFull (): return False idx = ( self . front + self . size ) % self . capacity self . q [ idx ] = value self . size += 1 return True def deQueue ( self ) -> bool : if self . isEmpty (): return False self . front = ( self . front + 1 ) % self . capacity self . size -= 1 return True def Front ( self ) -> int : return - 1 if self . isEmpty () else self . q [ self . front ] def Rear ( self ) -> int : if self . isEmpty (): return - 1 idx = ( self . front + self . size - 1 ) % self . capacity return self . q [ idx ] def isEmpty ( self ) -> bool : return self . size == 0 def isFull ( self ) -> bool : return self . size == self . capacity # Your MyCircularQueue object will be instantiated and called as such: # obj = MyCircularQueue(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() ############ class MyCircularQueue ( object ): def __init__ ( self , k ): """ Initialize your data structure here. Set the size of the queue to be k. :type k: int """ self . queue = [] self . size = k self . front = 0 self . rear = 0 def enQueue ( self , value ): """ Insert an element into the circular queue. Return true if the operation is successful. :type value: int :rtype: bool """ if self . rear - self . front < self . size : self . queue . append ( value ) self . rear += 1 return True else : return False def deQueue ( self ): """ Delete an element from the circular queue. Return true if the operation is successful. :rtype: bool """ if self . rear - self . front > 0 : self . front += 1 return True else : return False def Front ( self ): """ Get the front item from the queue. :rtype: int """ if self . isEmpty (): return - 1 else : return self . queue [ self . front ] def Rear ( self ): """ Get the last item from the queue. :rtype: int """ if self . isEmpty (): return - 1 else : return self . queue [ self . rear - 1 ] def isEmpty ( self ): """ Checks whether the circular queue is empty or not. :rtype: bool """ return self . front == self . rear def isFull ( self ): """ Checks whether the circular queue is full or not. :rtype: bool """ return self . rear - self . front == self . size # Your MyCircularQueue object will be instantiated and called as such: # obj = MyCircularQueue(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()

1// OJ: https://leetcode.com/problems/design-circular-queue/ // Time: O(1) for all // Space: O(K) class MyCircularQueue { private: vector < int > v ; int start = 0 , len = 0 ; public: MyCircularQueue ( int k ) : v ( k ) {} bool enQueue ( int value ) { if ( isFull ()) return false ; v [( start + len ++ ) % v . size ()] = value ; return true ; } bool deQueue () { if ( isEmpty ()) return false ; start = ( start + 1 ) % v . size (); -- len ; return true ; } int Front () { if ( isEmpty ()) return - 1 ; return v [ start ]; } int Rear () { if ( isEmpty ()) return - 1 ; return v [( start + len - 1 ) % v . size ()]; } bool isEmpty () { return ! len ; } bool isFull () { return len == v . size (); } };

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem