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.

Implementation the MyCircularQueue class:

  • MyCircularQueue(int 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.

Examples

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 (queue is full)
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.

Thinking Process

  1. Circular Array Approach:
    • Uses modulo arithmetic for wrapping: (index + 1) % cap
    • Tracks size to distinguish empty vs full
    • More memory efficient (fixed array)
  • Draw pointers before rewriting links.
  • Dummy head simplifies insert/delete at the head.
  • Slow/fast pointers find middle or detect cycles in one pass.
Linked list: pointer walk 1 2 3 slow → → fast (2x speed)

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Iterative pointer walk (this problem) O(n) O(1) Traversal, insertion
Dummy head node O(n) O(1) Simplify head-edge cases
Reversal (3-pointer) O(n) O(1) Reverse sublist or full list
Slow/fast pointers O(n) O(1) Middle, cycle, merge lists

Solution

class MyCircularQueue:
MyCircularQueue(k) : q(k), head(0), tail(0), size(0), cap(k) :
def enQueue(self, value):
    if(isFull()) return False
    q[tail] = value
    tail = (tail + 1) % cap
    size += 1
    return True
def deQueue(self):
    if(isEmpty()) return False
    head = (head + 1) % cap
    size -= 1
    return True
def Front(self):
    (-1 if         return isEmpty()  else q[head])
def Rear(self):
    (-1 if         return isEmpty() else q[(tail - 1 + cap) % cap])
def isEmpty(self):
    return size == 0
def isFull(self):
    return size == cap
list[int> q
head, tail, size, cap
/
 Your MyCircularQueue object will be instantiated and called as such:
 MyCircularQueue obj = new MyCircularQueue(k)
 bool param_1 = obj.enQueue(value)
 bool param_2 = obj.deQueue()
 param_3 = obj.Front()
 param_4 = obj.Rear()
 bool param_5 = obj.isEmpty()
 bool param_6 = obj.isFull()
/

Solution Explanation

Approach: Iterative pointer walk (this problem)

Key idea: 1. Circular Array Approach:

How the code works:

  1. Circular Array Approach:
    • Uses modulo arithmetic for wrapping: (index + 1) % cap
    • Tracks size to distinguish empty vs full
    • More memory efficient (fixed array)
    • Draw pointers before rewriting links.
    • Dummy head simplifies insert/delete at the head.

      Common Mistakes

  2. Empty queue: All operations return -1 or false except isEmpty() → true
  3. Full queue: enQueue() returns false
  4. Single element: After deQueue(), queue becomes empty
  5. Capacity 1: Only one element can be stored

  6. Wrap around: Array approach wraps tail from cap-1 to 0

  7. Not tracking size: Using only head and tail can’t distinguish empty from full
  8. Wrong modulo calculation: (tail - 1 + cap) % cap for rear (not tail - 1)
  9. Memory leaks: Not deleting nodes in linked list deQueue()
  10. Null pointer: Not checking tail == nullptr after deQueue() when empty
  11. Index out of bounds: Not using modulo for array indices

Key Takeaways

  1. Circular Array Approach:
    • Uses modulo arithmetic for wrapping: (index + 1) % cap
    • Tracks size to distinguish empty vs full
    • More memory efficient (fixed array)
  2. Linked List Approach:
    • Dynamic node allocation
    • Simpler logic (no modulo needed)
    • Requires memory management (delete nodes)
  3. Empty vs Full Distinction:
    • Array: Use size counter (not just head/tail positions)
    • Linked List: Use cnt counter
  4. Rear Element:
    • Array: q[(tail - 1 + cap) % cap] (previous position, wrapped)
    • Linked List: tail->val (direct access)

References

Template Reference