Leetcode 622. Design Circular Queue

Problem

Leetcode 622 - Design Circular Queue

Example:

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

Approach

We can implement this using LinkedList, all the functions are self explanatory.

There are few edge cases that we have to consider:

• enQueue: if count == k, we just return False
• deQueue: if count == 0, then we return False
• deQueue: if there’s only 1 element, head and tail should be None

Here is the Python code for the solution:

class ListNode:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next
    
class MyCircularQueue:

    def __init__(self, k: int):
        self.head = None
        self.tail = None
        self.k = k
        self.count = 0

    def enQueue(self, value: int) -> bool:
        if self.count + 1 > self.k:
            return False
        
        if self.count == 0:
            self.head = ListNode(value, None)
            self.tail = self.head
            self.count += 1
            return True
        
        self.tail.next = ListNode(value, None)
        self.tail = self.tail.next
        self.count += 1
        return True

    def deQueue(self) -> bool:
        if self.count == 0:
            return False
        
        if self.head == None:
            return False
        
        if self.head == self.tail:
            self.tail = None
            
        self.head = self.head.next
        self.count -= 1
        return True

    def Front(self) -> int:
        if self.head:
            return self.head.val
        return -1

    def Rear(self) -> int:
        if self.tail:
            return self.tail.val
        return -1

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

    def isFull(self) -> bool:
        return self.count == self.k

Time Complexity and Space Complexity

Time Complexity: $O(1)$ for each operation

Space Complexity: $O(n)$