622. Design Circular Queue

Medium

Problem:

Design circular queue. You must solve the problem without using the built-in queue data structure in your programming language.

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

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.

What to learn:

Circular Queue

A circular queue has the same FIFO structure as a traditional queue. However, because its end position is connected to the starting position in a circular structure, it is also called a Ring Buffer.

The traditional queue couldn't add any more elements once the space was filled. However, if there's space left in the front, the circular queue provides a recyclable structure that allows additions to the front.

Originally, deQueue() not only deleted an element but also extracted it. However, here, Rear() and deQueue() are implemented separately. Remember, the original queue only has an operation defined as front() or peek().

Solution:

  • When you enQueue(), the rear pointer moves forward, and when you deQueue(), the front pointer moves forward.

  • If the rear pointer meets the front pointer at the same location, it means there is no available space.

  • When moving the pointer one step forward, modulo operation with the total length is performed to ensure that the pointer's position does not exceed the total length.

class MyCircularQueue:

    def __init__(self, k: int):
        self.q = [None] * k
        self.maxlen = k
        self.front_ptr = 0
        self.rear_ptr = 0
    def enQueue(self, value: int) -> bool:
        if self.q[self.rear_ptr] == None:
            self.q[self.rear_ptr] = value
            self.rear_ptr = (self.rear_ptr + 1) % self.maxlen
            return True
        else:
            return False
        
    def deQueue(self) -> bool:
        if self.q[self.front_ptr] is None:
            return False
        else:
            self.q[self.front_ptr] = None
            self.front_ptr = (self.front_ptr + 1) % self.maxlen
            return True
        
    def Front(self) -> int:
        return -1 if self.q[self.front_ptr] is None else self.q[self.front_ptr]
        
    def Rear(self) -> int:
        return -1 if  is None else self.q[self.rear_ptr -1]

    def isEmpty(self) -> bool:
        return self.front_ptr == self.rear_ptr and self.q[self.front_ptr] is None

    def isFull(self) -> bool:
        return self.front_ptr == self.rear_ptr and self.q[self.front_ptr] is not None

Last updated