Python Algorithm Q25

Q25 Design Circular Queue

---

Q

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(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.

Sample Input

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.

1. My own Solution

class MyCircularQueue:

    def __init__(self, k: int):
        self.q = [None] * k
        self.maxlen = k
        self.front = 0 #front pointer
        self.rear = -1 #rear pointer
        #At the first insertion, pushed back one step.
        self.cnt = 0
        
    def enQueue(self, value: int) -> bool: 
        #only rear pointer moves when the insertion
        if self.isFull():
            return False
        else:
            #push rear to the back. Consider maxlen.
            self.rear = (self.rear + 1)%(self.maxlen)
            self.q[self.rear] = value
            self.cnt += 1
            return True

    def deQueue(self) -> bool:
        if self.isEmpty():
            return False
        else:
            self.q[self.front] = None
            #push front to the back. Consider maxlen.
            self.front = (self.front + 1)%(self.maxlen)
            self.cnt -= 1
            return True

    def Front(self) -> int:
        a = self.q[self.front]
        if a == None:
            return -1
        else:
            return a

    def Rear(self) -> int:
        b = self.q[self.rear]
        if b == None:
            return -1
        else:
            return b
        
    def isEmpty(self) -> bool:
        if self.cnt == 0:
            return True
        else:
            return False

    def isFull(self) -> bool:
        if self.cnt == self.maxlen:
            return True
        else:
            return False

#For test,
obj = MyCircularQueue(8)
p1 = obj.enQueue(3)
print(p1, obj.front,obj.rear)
p2 = obj.enQueue(9)
print(p2, obj.front,obj.rear)
p3 = obj.enQueue(5)
print(p3, obj.front,obj.rear)
p4 = obj.enQueue(0)
print(p4, obj.front,obj.rear)
p5 = obj.deQueue()
print(p5, obj.front,obj.rear)
p6 = obj.deQueue()
print(p6, obj.front,obj.rear)
p7 = obj.Rear()
print(p7)
print(obj.q)

Let me introduce the variables.

• q(list) is for the basis of Circular Queue.
• maxlen and cnt is for the function “isEmpty” and “isFull”.
• front and rear is for the function “Front” and “Rear”.

Start with the functions.

1. enQueue : check if the Queue is full. If not, push rear pointer first and then insert the value. When pushing the pointer, consider whether pointer exceeds the maxlen. In this code, using % operator. cnt++ lastly.

2. deQueue : check if the Queue is empty. If not, delete value(by inserting None) and push front pointer. The rest process is same as before.

3. Front, Rear : check if that value exists.

4. isEmpty, isFull : check with the variable, cnt.

2. Given Solution

class MyCircularQueue:

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

    def deQueue(self) -> bool:
        if self.q[self.p1] is None:
            return False
        else:
            self.q[self.p1] = None
            self.p1 = (self.p1 + 1) % self.maxlen
            return True

    def Front(self) -> int:
        return -1 if self.q[self.p1] is None else self.q[self.p1]

    def Rear(self) -> int:
        #we already pushed rear pointer, so pull one step when using rear index.
        return -1 if self.q[self.p2 - 1] is None else self.q[self.p2 - 1]
        
    def isEmpty(self) -> bool:
        #both pointer overlap and that value is none.
        return self.p1 == self.p2 and self.q[self.p1] is None

    def isFull(self) -> bool:
        #both pointer overlap and that value is not none.
        return self.p1 == self.p2 and self.q[self.p1] is not None

Let’s explain it briefly. Other codes are almost same except two.

1. In “Front” and “Rear” function, the given code pull one step when return instead of using the saved variable, rear(p2), itself. I need to start rear pointer at -1 to fit the function…

2. The variable, cnt, is useless. Instead, the given code use the simple principle that when empty or full case, front p == rear p. In empty case, front==rear AND that value is None. The other case is the same but that value is not None.

Overall Review

Designing data type like Queue and Stack is quiet strange experience to me. Get used to solving PS, implementing structure by myself is not that easy. I’m really looking forward to exploring the next step of algorithm such as sorting and searching after learning basic data structure in this chapter.