[LEET CODE] 622. Design Circular Queue

# Problem

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.   Constraints: 1 <= k <= 1000 0 <= value <= 1000 At most 3000 calls will be made to enQueue, deQueue, Front, Rear, isEmpty, and isFull.

 

# My Answer

class MyCircularQueue:

    def __init__(self, k: int):
        self.k = k
        self.q = [None]*k
        self.front = 0
        self.rear = -1
    def enQueue(self, value: int) -> bool:
        if self.isFull(): # 꽉 차있으면 false 반환
            return False
        else:
            if self.rear==self.k-1: # 마지막 칸까지 차있는 경우
                self.rear=0 # 인덱스 0으로 이동
                self.q[self.rear] = value
                return True
            else:
                self.rear+=1
                self.q[self.rear] = value
                return True

    def deQueue(self) -> bool:
        if self.isEmpty(): # 비어있으면 False 반환
            return False
        else:
            if self.front==self.k-1:# front 가 맨 끝이면 다음칸은 인덱스 0
                self.q[self.front]=None
                self.front=0
                return True
            else:
                self.q[self.front]=None
                self.front +=1
                return True

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

    def Rear(self) -> int:
        if self.isEmpty():
            return -1
        else:
            return self.q[self.rear]

    def isEmpty(self) -> bool:
        if self.q[self.front] is None :
            return True
        else:
            return False

    def isFull(self) -> bool:
        if None in self.q:
            return False
        else:
            return True

 

# Solution 1 - 배열을 이용한 풀이

class MyCircularQueue:
    def __init__(self, k: int):
        self.q = [None] * k
        self.maxlen = k
        self.p1 = 0
        self.p2 = 0

    # enQueue(): 리어 포인터 이동
    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

    # deQueue(): 프론트 포인터 이동
    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:
        return -1 if self.q[self.p2 - 1] is None else self.q[self.p2 - 1]

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

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

투포인터와 비슷 front, rear 포인터 사용