Leetcode 622: Design Circular Queue (Python)

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. 

 

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.

 

 

풀이

처음에는 deque로 신나게 풀었다가, 그러면 안 되는걸 깨닫고 '파이썬 알고리즘 인터뷰'에 제시되어 있는 __init__함수의 변수만 보고 나머지를 구현하였다. 그래서 모범적이지 않은 풀이이다...ㅎㅎ;;

투 포인터 풀이랑 비슷한 느낌이 있다. 길이 k의 배열을 선언한 후, 맨 앞을 p1, 맨 뒤(의 바로 뒤칸)을 p2가 가르키도록 한다. 이후 메소드별 요구하는 바를 적당히 구현한다.

 

틀린 점

1) isEmpty랑 isFull을 생각을 잘못해서 살짝 해맸다.

2) 해당 칸이 비어있는지를 확인하기 위해 if self.circular_queue[self.p1]이라고 코드를 짰는데, input에 0이 들어가면 값이 있음에도 불구하고 거짓이 된다. 따라서 if self.circular_queue[self.p1] == None과 같이 직접적으로 명시하자.

 

좋은 문제인 듯하다.

 

코드

class MyCircularQueue:

    def __init__(self, k: int):
        self.circular_queue = [None] * k
        self.max_len = k
        self.p1, self.p2 = 0, 0

    def enQueue(self, value: int) -> bool:
        if not self.isFull():
            self.circular_queue[self.p2] = value
            if self.p2 == self.max_len - 1:
                self.p2 = 0
            else:
                self.p2 += 1
            return True

    def deQueue(self) -> bool:
        if not self.isEmpty():
            self.circular_queue[self.p1] = None
            if self.p1 == self.max_len - 1:
                self.p1 = 0
            else:
                self.p1 += 1
            return True
        
    def Front(self) -> int:
        if self.circular_queue[self.p1] != None:
            return self.circular_queue[self.p1]
        return -1

    def Rear(self) -> int:
        if self.circular_queue[self.p2-1] != None: 
            return self.circular_queue[self.p2-1]
        return -1
    
    def isEmpty(self) -> bool:
        return self.p1 == self.p2 and not self.circular_queue[self.p1]

    def isFull(self) -> bool:
        return self.p1 == self.p2 and self.circular_queue[self.p1]