문제

원형 큐를 디자인 하라 (상세link)

풀이

큐 Queue -> FIFO구조

• enQueue : 삽입 (존재하는 요소들의 맨 뒤에 삽입)
• deQueue : 제거,추출 (FIFO이므로 맨 처음 추가된 요소부터 first-out)

원형 큐(Circular Queue = 링버퍼 Ring Buffer)는 FIFO구조를 지니고, 마지막 위치가 시작위치에 연결되어있습니다.

기존의 큐는 공간이 꽉 차게 되면 더이상 요소를 추가할 수 가 없었습니다. deQueue로 앞쪽 요소가 빠져나가 공간이 생겨도 그쪽으로는 추가할 수가 없었습니다.
그래서 앞쪽에 공간이 남아있다면 아래 그림처럼 동그랗게 연결해 앞쪽으로 추가할 수 있도록 재활용 가능한 구조가 바로 원형 큐입니다.

동작하는 원리는 투 포인터와 비슷합니다. enQueue하여 요소를 삭제할 자리, deQueue하여 요소를 추가할 자리를 따로 저장하면 됩니다. enQueue()를 하게 되면 rear 포인터가 앞으로 이동하고, deQueue()를 하게 되면 front포인터가 앞으로 이동합니다. 이렇게 enQueue와 deQueue를 반복하게 되면 서로 동그랗게 연결되어 있기 때문에 투 포인터가 빙글빙글 돌면서 이동하는 구조가 됩니다.
만약 rear 포인터와 front 포인터가 같은 위치를 가르키게 된다면 여유공간이 없는 상황으로 공간 부족 에러를 발생시킵니다.

이제 파이썬으로 구현한 코드로 자세한 설명을 해보겠습니다.
아래 코드에서 p1이 rear포인터를, p2가 front 포인터를 의미합니다.

원형 큐의 enQueue

def enQueue(self, value: int) -> bool:
        """
        Insert an element into the circular queue. Return true if the operation is successful.
        """
        if self.q[self.p2] is None:
            self.q[self.p2] = value #rear이 가르키는 자리에 value삽입
            self.p2 = (self.p2 +1) % self.maxlen # 다음 자리로 p2포인터 이동. 길이가 넘어가면 나머지 연산자를 이용하여 한바퀴 돌아서 자리찾기
            return True
        else
            return False

rear 포인터 p2 위치에 값을 넣고, 포인터를 한 칸 앞으로 이동합니다. 단 전체 길이만큼 나머지 연산을 하여 포인터의 위치가 전체 길이를 벗어나지 않게 합니다.
만약 p2가 가르키는 값이 None이 아니라면 다른 요소가 있는 공간이 꽉 찬 상태이거나 비정상적인 경우이므로 False를 리턴합니다.

원형 큐의 deQueue

def deQueue(self) -> bool:
        """
        Delete an element from the circular queue. Return true if the operation is successful.
        """
        if self.q[self.p1] is None:
            return False #이미 내보낼것이 없는 상태 ->False
        else:
            self.q[self.p1] = None #삭제
            self.p1 = (self.p1+1) % self.maxlen
            return True

front 포인터 p1의 위치에 None을 넣어 삭제하고, 포인터를 한 칸 앞으로 이동한다.
다음으로 나머지 연산으로 최대 길이를 넘지 않도록 한다.

전체 코드

원형 큐 class의 함수들입니다.

• enQueue : rear 포인터가 지정한 위치에 요소 삽입
• deQueue : front 포인터가 지정한 위치에 요소 삭제
• Front : 큐의 맨 처음 요소를 반환
• Rear : 큐의 맨 마지막 요소를 반환 (큐에는 없는 기능이지만, 투포인터 이기 때문에 쉽게 구현 가능)
• isEmpty : 비어있는 상황이면 True를 반환
• isFull : 여유공간이 없는 상황이면 True를 반환

# https://leetcode.com/problems/design-circular-queue/submissions/
"""
Runtime: 60 ms, faster than 96.87% of Python3 online submissions for Design Circular Queue.
Memory Usage: 14.5 MB, less than 54.38% of Python3 online submissions for Design Circular Queue.
"""
class MyCircularQueue:

    def __init__(self, k: int):
        """
        Initialize your data structure here. Set the size of the queue to be k.
        """
        self.q = [None] * k
        self.maxlen = k
        self.p1 = 0
        self.p2 = 0
        

    def enQueue(self, value: int) -> bool:
        """
        Insert an element into the circular queue. Return true if the operation is successful.
        """
        if self.q[self.p2] is None:
            self.q[self.p2] = value #rear이 가르키는 자리에 value삽입
            self.p2 = (self.p2 +1) % self.maxlen # 다음 자리로 p2포인터 이동. 길이가 넘어가면 나머지 연산자를 이용하여 한바퀴 돌아서 자리찾기
            return True
        else
            return False
        

    def deQueue(self) -> bool:
        """
        Delete an element from the circular queue. Return true if the operation is successful.
        """
        if self.q[self.p1] is None:
            return False #이미 내보낼것이 없는 상태 ->False
        else:
            self.q[self.p1] = None #삭제
            self.p1 = (self.p1+1) % self.maxlen
            return True
        

    def Front(self) -> int:
        """
        Get the front item from the queue.
        """
        # p1이 가르키는 맨앞의 요소를 반환
        return -1 if self.q[self.p1] is None else self.q[self.p1]
        

    def Rear(self) -> int:
        """
        Get the last item from the queue.
        """
        # 맨 뒤의 요소를 반환 (p2는 이미 뒤에 삽입될 자리를 가르키고 있기 때문에 p2-1이 맨 뒤의 요소를 가르키고 있습니다.)
        return -1 if self.q[self.p2 -1] is None else self.q[self.p2 -1] 
        

    def isEmpty(self) -> bool:
        """
        Checks whether the circular queue is empty or not.
        """
        # p1,p2가 가르키는 자리가 같고, 그 안의 요소가 존재하지 않는다면 큐는 비어있습니다.
        return self.p1 == self.p2 and self.q[self.p1] is None
        

    def isFull(self) -> bool:
        """
        Checks whether the circular queue is full or not.
        """
        # p1,p2가 가르키는 자리가 같고, 그 안의 요소가 존재하면 공간이 다 찬것입니다.
        return self.p1 == self.p2 and self.q[self.p1] is not None
        


# Your MyCircularQueue object will be instantiated and called as such:
obj = MyCircularQueue(k)
param_1 = obj.enQueue(value)
param_2 = obj.deQueue()
param_3 = obj.Front()
param_4 = obj.Rear()
param_5 = obj.isEmpty()
param_6 = obj.isFull()