LeetCode #622 - Design Circular Queue(원형 큐 디자인) 풀이

문제

문제에서 나오는 원형 큐는 FIFO 정책에 따라 연산을 수행하고 마지막 위치를 첫 번째 위치에 연결하여 원을 만드는 선형 데이터 구조로, 링 버퍼라고도 한다. 원형 큐의 장점 중 하나는 공간을 활용할 수 있다는 것이다. 일반적인 큐에서는 데이터가 가득차면 큐에 공간이 있어도 다음 요소를 삽입할 수가 없다. 그러나, 원형 큐를 사용하면 공간을 사용하여 새로운 값을 저장할 수 있다. 문제에서 구현해야 할 MyCircularQueue 클래스의 메소드는 다음과 같다.

• __init__(k: int) -> None : 큐 개체의 크기를 k로 초기화
• Front() -> int : 큐의 맨 앞의 데이터를 가져오되, 비어있는 상태인 경우 -1을 반환한다.
• Rear() -> int : 큐의 맨 뒤의 데이터를 가져오되, 비어있는 상태인 경우 -1을 반환한다.
• enQueue(val: int) -> bool : 큐에 데이터를 삽입하고, 성공 여부를 반환한다.
• deQueue() -> bool : 큐의 요소를 제거하고, 성공 여부를 반환한다.
• isEmpty() -> bool : 원형 큐가 비어있으면 true, 그렇지 않으면 false를 반환한다.
• isFull() -> bool : 원형 큐가 꽉 찼으면 true, 그렇지 않으면 false를 반환한다.

단, 이 문제를 해결할 때 프로그래밍 언어에 내장된 큐를 사용하지 않고 문제를 해결하여야 한다.

풀이

문제 자체는 매우 심플한데다가 명확하다(내가 이래서 LeeCode 문제를 좋아한다). 예전에 내가 공부하던 내용 중에 링버퍼가 있었는데, 아래 내용을 참고하면 쉽게 해결 가능할 것으로 보인다.

• 🔗 자료 구조(Data Structure)의 큐(Queue) 개념 정리

다만, 주의하여야 할 점이 있다면 Rear() 메소드를 작성 시 현재 rear의 위치를 가리키는 포인터보다 한 칸 이전의 인덱스에 해당하는 값을 반환하여야 한다는 것이다.

def Rear(self) -> int:
    return -1 if self.body[self.rear-1] is None else self.body[self.rear-1]

그 이유는 euQueue()로 데이터를 추가할 때 현재 rear 포인터는 미리 다음 칸의 위치를 가리키기 때문이다.

def enQueue(self, value: int) -> bool:
    if self.isFull():
        return False

    self.body[self.rear] = value
    self.rear += 1

    if self.rear == self.size:
        self.rear = 0

    return True

전체 코드

class MyCircularQueue:
    def __init__(self, k: int):
        self.size = k
        self.body = [None]*self.size
        self.front = self.rear = 0

    def enQueue(self, value: int) -> bool:
        if self.isFull():
            return False

        self.body[self.rear] = value
        self.rear += 1

        if self.rear == self.size:
            self.rear = 0

        return True

    def deQueue(self) -> bool:
        if self.isEmpty():
            return False

        self.body[self.front] = None
        self.front += 1

        if self.front == self.size:
            self.front = 0

        return True

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

    def Rear(self) -> int:
        return -1 if self.body[self.rear-1] is None else self.body[self.rear-1]

    def isEmpty(self) -> bool:
        return self.front == self.rear and self.body[self.front] is None

    def isFull(self) -> bool:
        return self.front == self.rear and self.body[self.front] is not None