# Design Circular Queue
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/design-circular-queue)
Canonical: https://scaleengineer.com/dsa/problems/design-circular-queue
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design)
**Algorithms:** [Token Bucket](https://scaleengineer.com/algorithms/token-bucket)
**Data structures:** Array, Linked List, Queue
**Companies:** [Intuit](https://scaleengineer.com/companies/intuit), [Qualcomm](https://scaleengineer.com/companies/qualcomm), [Tesla](https://scaleengineer.com/companies/tesla), [Citadel](https://scaleengineer.com/companies/citadel), [Cloudflare](https://scaleengineer.com/companies/cloudflare), [Zoox](https://scaleengineer.com/companies/zoox), [Applied Intuition](https://scaleengineer.com/companies/applied-intuition), [Datadog](https://scaleengineer.com/companies/datadog)
---
## 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`.

# Approaches
## Linked List with Size Tracking
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.
**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.
**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.
### Explanation
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.

```java
class MyCircularQueue {
    private class Node {
        public int value;
        public Node next;
        public Node(int value) {
            this.value = value;
            this.next = null;
        }
    }

    private int capacity;
    private int count;
    private Node head;
    private Node tail;

    public MyCircularQueue(int k) {
        this.capacity = k;
        this.count = 0;
        this.head = null;
        this.tail = null;
    }

    public boolean enQueue(int value) {
        if (isFull()) {
            return false;
        }
        Node newNode = new Node(value);
        if (isEmpty()) {
            head = tail = newNode;
        } else {
            tail.next = newNode;
            tail = newNode;
        }
        count++;
        return true;
    }

    public boolean deQueue() {
        if (isEmpty()) {
            return false;
        }
        head = head.next;
        count--;
        if (isEmpty()) {
            tail = null;
        }
        return true;
    }

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

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

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

    public boolean isFull() {
        return count == 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`.

## Array with Head/Tail Pointers and Size Counter
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.
**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.
**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.
### Explanation
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`.

```java
class MyCircularQueue {
    private int[] queue;
    private int head;
    private int tail;
    private int count;
    private int capacity;

    public MyCircularQueue(int k) {
        this.capacity = k;
        this.queue = new int[k];
        this.head = 0;
        this.tail = 0;
        this.count = 0;
    }

    public boolean enQueue(int value) {
        if (isFull()) {
            return false;
        }
        queue[tail] = value;
        tail = (tail + 1) % capacity;
        count++;
        return true;
    }

    public boolean deQueue() {
        if (isEmpty()) {
            return false;
        }
        // The element at head is overwritten on a future enqueue
        head = (head + 1) % capacity;
        count--;
        return true;
    }

    public int Front() {
        if (isEmpty()) {
            return -1;
        }
        return queue[head];
    }

    public int Rear() {
        if (isEmpty()) {
            return -1;
        }
        // The last element is at the index before the current tail
        int rearIndex = (tail - 1 + capacity) % capacity;
        return queue[rearIndex];
    }

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

    public boolean isFull() {
        return count == capacity;
    }
}
```
### 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`.

# Solutions
### Java

```java
public 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(); */
```

### Python

```python
class 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()
```

### CPP

```cpp
// 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 (); } };
```