25. Design Circular Queue

리트코드

• 원형 큐를 디자인하라.

1. 배열을 이용한 풀이

class MyCircularQueue:

    def __init__(self, k: int):
        self.q = [None] * k
        self.maxlen = k
        self.p1 = 0
        self.p2 = 0
        
        
    #enQueue(): rear포인터 이동
    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(): front 포인터 이동
    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]
        #인덱스이기에 -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


# 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()

• 원형큐를 구현하는 방법에는 여러가지가 있으나 여기서는 가장 일반적인 방법인 배열로 구현해본다.

  • 배열로 구현했을 때 공간을 재활용한다는 원형의 이점을 내세울 수 있기도 하다.

• 먼저 초기화 시에는 큐의 크기 k를 입력값으로 받는다.

  • k 값은 당연히 최대 길이인 maxlen이 된다.

• front 포인터는 p1으로 정하고, rear 포인터는 p2로 정한다.

  • 둘 다 초기값은 0으로 한다.

• 다음으로 요소를 삽입하는 enQueue() 연산을 구현한다.

  • rear 포인터 p2 위치에 값을 넣고, 포인터를 한 칸 앞으로 이동한다.

    • 단, 전체 길이만큼 모튤로(나머지) 연산을 하여 포인터의 위치가 전체 길이를 벗어나지 않게 한다.

    • 만약 rear 포인터 위치가 None이 아니라면 다른 요소가 있는 공간이 꽉 찬 상태이거나 비정상적인 경우이므로 False를 리턴한다.

• deQueue() 연산을 구현할 차례다.

  • 이 문제에서 요구하는 deQueue() 연산은 요소를 꺼내지 않고 삭제만 수행하도록 정의되어 있다.

  • 큐에서 요소를 꺼내는 것은 문제의 예제에서 보듯 앞쪽은 Front()로, 뒤쪽은 Rear()로, 각기 서로 다른 연산으로 정의되어 있다.

  • front 포인터 p1의 위치에 None을 넣어 삭제를 하고, 포인터를 한 칸 앞으로 이동한다.

    • 다음으로, 마찬가지로 모듈로 연산으로 최대 길이를 넘지 않도록 한다.

    『 Introdectuon to Algorithms 』 책이나 리스트 9-1에 정리한 워싱턴 주립대학 강의 자료 수도코드를 살펴보면, 동일한 원형 큐를 구현하면서 분명히 deQueue()에는 요소 삭제 뿐만 아니라 추출도 함께 수행한다.

Enqueue(Q,x)
    Q[Q.tail] = x
    if Q.tail == Q.length
        Q.tail = 1
        
    else
        Q.tail = Q.tail + 1
        
Dequeue(Q)
    x = Q[Q.head]
    if Q.head == Q.length
        Q.head = 1
        
    else 
        Q.head = Q.head + 1
        
    return x
 

• 정리하면 enQueue()는 rear 포인터를 이동하고 데큐는 front 포인터를 이동한다.