[LeetCode] #622. Design Circular Queue

리트코드 #622. 원형 큐 디자인

문제

문제 링크

원형 큐의 기본 연산을 구현한다.

enQueue() : 원형 큐에 요소 삽입
deQueue() : 원형 큐에서 요소 삭제
Front() : 원형 큐의 첫번째 요소 반환
Rear() : 원형 큐의 마지막 요소 반환
isEmpty() : 원형 큐가 비어있으면 True
isFull() : 원형 큐가 꽉 차있으면 True

풀이

원형 큐는 위의 그림처럼 원 모양의 큐로, 큐 안의 요소를 삭제했을 때 생기는 빈 공간을 사용할 수 있다는 장점이 있다.
하지만 컴퓨터 메모리는 원 모양이 아니기 때문에 linear data structure로 구현해야 한다.

__init__() : 원형 큐는 큐의 크기(k)가 정해져있다.
원형 큐는 2개의 포인터를 가지는데, 큐의 시작을 가리키는 포인터 front. 끝을 가리키는 rear로 이루어진다.

enQueue()
1) 큐에 요소를 삽입할 공간이 남았는지, isFull()을 검사한다.
2) 큐의 끝을 가리키는 rear포인터의 위치에 요소를 삽입한다.
3) rear포인터를 1칸 이동시킨다.

deQueue()
1) 큐에 삭제할 요소가 있는지, isEmpty()을 검사한다.
2) 큐의 시작을 가리키는 front포인터의 위치의 요소를 삭제한다.
3) front포인터를 1칸 이동시킨다.

enQueue()에서 원형 큐에 요소를 삽입한 후 rear 포인터를 다음칸으로 이동시킨다. 처음에 헷갈렸는데 rear포인터가 가리키는 곳은 큐의 마지막 요소가 아니라, 마지막 요소 다음 칸이다. (위의 그림과 다름)
rear포인터가 큐의 마지막 요소를 가리키는 구현 방법도 있을 수 있지만, 여기서는 다음칸을 가리킨다고 설정했다.
따라서 Rear() 을 구현할 때는 self.q[self.rear]가 아닌 self.q[self.rear-1]를 검사해야 한다.

코드

github link

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

    def enQueue(self, value: int) -> bool:
        # rear 포인터 위치가 None이 아니면 다른 요소로 인해 공간이 꽉찬 상태
        if self.q[self.rear] is None:
            self.q[self.rear] = value  # rear 포인터에 값 넣기
            self.rear = (self.rear + 1) % self.maxlen  # rear 포인터 1칸 이동
            return True  # 성공
        else:
            return False  # 실패

    def deQueue(self) -> bool:
        # 삭제할 요소가 없으면 dequeue 실패
        if self.q[self.front] is None:
            return False
        else:
            self.q[self.front] = None  # 요소 삭제
            self.front = (self.front + 1) % self.maxlen  # front 포인터 1칸 이동
            return True

    # 큐의 첫번째 요소를 반환, 큐가 비어있으면 -1 반환
    def Front(self) -> int:
        return -1 if self.q[self.front] is None else self.q[self.front]

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

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

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