[leetcode] 25. 원형 큐 디자인 (Design Circular Queue)

들어가며

본 포스팅은 <파이썬 알고리즘 인터뷰> 책에서 다룬 리트코드 문제들을 다루고 있습니다. 

문제들은 모두 리트코드에서 출제된 문제들이며, 문제 풀이의 많은 부분을 책의 힌트와 해설을 참고하였습니다. 

 

포스팅되는 모든 문제들의 목록과 풀이는 파이썬 알고리즘 인터뷰에서 제공하는 깃허브에서 확인하실 수 있습니다.

 

---

문제

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.

You must solve the problem without using the built-in queue data structure in your programming language. 

 

원형 큐를 디자인하라.

• MyCircularQueue(k) - k를 사이즈로 초기화
• Front() - 큐에서 처음 요소를 가져온다. 큐가 비어있다면 -1을 반환할 것
• Rear() - 큐에서 마지막 요소를 가져온다. 큐가 비어있다면 -1을 반환할 것
• enQueue(value) - 원형 큐에 요소를 삽입. 수행이 성공한다면  True를 반환할 것
• deQueue() - 원형 큐의 요소를 삭제. 수행이 성공한다면  True를 반환할 것
• isEmpty() - 큐가 비어있는 지 확인
• isFull() - 큐가 가득 차 있는 지 확인

 

 

입출력 예시

Example 1:

Input
["MyCircularQueue", "enQueue", "enQueue", "enQueue", "enQueue", "Rear", "isFull", "deQueue", "enQueue", "Rear"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
Output
[null, true, true, true, false, 3, true, true, true, 4]

Explanation
MyCircularQueue myCircularQueue = new MyCircularQueue(3);
myCircularQueue.enQueue(1); // return True
myCircularQueue.enQueue(2); // return True
myCircularQueue.enQueue(3); // return True
myCircularQueue.enQueue(4); // return False
myCircularQueue.Rear();     // return 3
myCircularQueue.isFull();   // return True
myCircularQueue.deQueue();  // return True
myCircularQueue.enQueue(4); // return True
myCircularQueue.Rear();     // return 4

 

 

생각과정

원형 큐를 얼핏 보기만 하고 제대로 공부한 건 처음이다. 연결 리스트 만큼은 아니지만 개념을 잡고 가는게 좋을 것 같아서 이번 문제는 풀이보다는 개념 정리와 구현 위주로 보고 공부하는게 좋을 것 같다.

 

원형 큐( = 링 버퍼, Ring buffer)

원형 큐는 마지막 위치가 시작 위치와 연결되는 원형 구조를 띠기 때문에 링 버퍼(Ring Buffer)라고도 불리는 원형 큐는 기존 큐의 단점을 보완하여 나온 큐의 형태이다.

기존의 큐는 배열처럼 미리 공간을 할당해두는데 공간이 꽉차게 되면 더이상 요소를 추가할 수 없고, 또, 디큐를 하면 배열의 요소를 앞쪽으로 옮겨줬어야한다. 원형 큐는 맨 앞과 끝이 연결되어 있기 때문에 디큐를 했을 때 생긴 공간을 재활용할 수가 있고, 요소를 앞으로 옮겨줄 필요가 없다.

 

원형 큐의 삽입과 삭제 원리는 다음과 같다.

 

그림에 나오는 front와 rear 변수가 어떤 요소가 첫 번째 요소이고 어떤 요소가 마지막 요소인지 판별하게 하는 역할을 한다.

• 프런트(front) - 맨 처음 요소의 인덱스
• 리어(rear) - 맨 끝 요소의 하나 뒤의 인덱스 ( 다음 요소를 인큐할 위치를 미리 지정)

원형 큐의 동작 원리는 투포인터와 비슷하다.

마지막 위치와 시작 위치를 연결하는 원형 구조를 만들고, 요소의 시작점과 끝점을 따라 투 포인터가 움직인다. 위 그림처럼 인큐를 하게 되면 리어 포인터가 앞으로 이동하고, 디큐를 하게 되면 프런트 포인터가 앞으로 이동한다. 연결리스트와 스택, 큐에서 앞으로 이동한다는 말이 혼용해서 사용되어서 헷갈리는데, 앞으로 이동한다는 말은 인덱스가 작은 쪽으로 이동한다는 말이다.

 

이렇게 인큐와 디큐를 반복하게 되면 서로 동그랗게 연결되어 있기 때문에 투 포인터가 빙글빙글 돌면서 이동하는 구조가 된다.

만약 리어 포인터와 프런트 포인터가 같은 위치에서 서로 만나게 된다면, 그때는 정말고 여유 공간이 하나도 없다는 얘기가 되므로 공간 부족 에러를 발생시킨다.

 

풀이

해설지 풀이

class MyCircularQueue:
    def __init__(self, k: int):
        self.q = [None] * k # 공간 설정
        self.maxlen = k # 최대 길이
        self.front = 0
        self.rear = 0

    # rear 포인터 이동
    def enQueue(self, value: int) -> bool:
        # rear 포인터의 위치에 값이 없다면 추가해준다.
        if self.q[self.rear] is None:
            self.q[self.rear] = value
            # rear가 다음 포인터로 이동해준다 (self.rear), 만약 rear가 전체길이를 초과하면 % 모듈로 나머지를 계산해 넣어준다. 그러면 결국 rear는 맨 앞으로 돌아오게 된다.
            # ex) maxlen = 3, rear = 2 -> rear = (2 + 1) % 3 = 0
            self.rear = (self.rear + 1) % self.maxlen
            return True
        else:
            # rear포인터 위치가 None이 아니면 (앞으로 한칸 이동 시켰기 때문에 요소가 가득 차지 않았다면 None이어야한다.), 비정상적인 상태이므로 False를 리턴한다.
            return False

    # front 포인터 이동
    def deQueue(self) -> bool:
        # front 포인터 위치에 값이 없을 때는 삭제할 요소가 없으므로 False 리턴
        if self.q[self.front] is None:
            return False
        else:
            self.q[self.front] = None # front가 가리키는 요소를 삭제해준다.
            self.front = (self.front + 1) % self.maxlen
            return True

문제는 Front()와 Rear() 등등이 있지만 일반적으로 사용하는 방식은 아니라고 하니, 중요한 부분을 짚고 넘어가자!

 

# rear 포인터 이동
def enQueue(self, value: int) -> bool:
    # rear 포인터의 위치에 값이 없다면 추가해준다.
    if self.q[self.rear] is None:
        self.q[self.rear] = value
        # rear가 다음 포인터로 이동해준다 (self.rear), 만약 rear가 전체길이를 초과하면 % 모듈로 나머지를 계산해 넣어준다. 그러면 결국 rear는 맨 앞으로 돌아오게 된다.
        # ex) maxlen = 3, rear = 2 -> rear = (2 + 1) % 3 = 0
        self.rear = (self.rear + 1) % self.maxlen
        return True
    else:
        # rear포인터 위치가 None이 아니면 (앞으로 한칸 이동 시켰기 때문에 요소가 가득 차지 않았다면 None이어야한다.), 비정상적인 상태이므로 False를 리턴한다.
        return False

인큐 부분이다.

가장 먼저 조건문으로 rear 포인터에 요소가 있는 지 없는 지 판별해준다. 비어있다면 바로 요소를 추가해주고

 

Rear가 큐에 요소가 추가될 때 앞으로 이동된다고 앞에서 설명했는데, 여기에서 그 개념을 확인할 수 있다.

 

if self.q[self.rear] is None:

Rear 포인터는 맨 끝 요소의 뒷 인덱스를 가리키고 있다고 써놨었는데, 이걸 기억한다면 이 조건문을 이해할 수 있다.

큐가 가득 차있는 경우가 아니라면 self.q[self.rear]는 비어있다. 이 말은 뒤에 요소를 추가할 수 있다는 말이다.

 

self.rear = (self.rear + 1) % self.maxlen

 

self.rear + 1 이 부분이 rear 포인터를 한칸 옮겨주는 부분이다. 그럼 나머지를 구해주는 % self.maxlen은 무엇일까? 

 

rear 포인터를 계속 하나씩 뒤로(마지막 인덱스 쪽으로) 옮겨주다보면 언젠가는 front 포인터랑 만나는 순간이 생기게 된다. 이때, rear 포인터가 가리키는 공간에 요소를 집어넣으려고 하더라도 기존에 할당해준 공간보다 넘치기 때문에 해당 인덱스를 다시 처음으로 되돌려줘야한다. 

 

만약 현재 큐에 할당된 크기가 7(마지막 인덱스는 6)인데, 현재 rear가 6을 가리키는 상태로 위 코드에 들어왔다면 큐의 마지막에 요소를 넣어주고 다음 인덱스로 포인터를 옮길 것이다. (rear = 7) 이렇게 되면 할당해준 마지막 인덱스를 넘어서기 때문에 에러를 뱉어내므로 다시 rear를 맨 처음으로 이동시켜줘야한다. 이해가 안된다면 그림을 다시 보고 오자!

 

rear가 7일 때 할당된 크기인 maxlen으로 나눈 나머지를 구하면 0이 나온다. 어! 이건 첫번째 인덱스이다. 우린 원형 큐의 시작점으로 돌아오게 되었다. 

 

이렇게 빙글빙글 돌아가면서 인덱스를 추가해주는 코드이다. 

 

 

자, 길고 긴 인큐 함수가 끝났다. 이번엔 디큐로 넘어가자!

 

# front 포인터 이동
def deQueue(self) -> bool:
    # front 포인터 위치에 값이 없을 때는 삭제할 요소가 없으므로 False 리턴
    if self.q[self.front] is None:
        return False
    else:
        self.q[self.front] = None # front가 가리키는 요소를 삭제해준다.
        self.front = (self.front + 1) % self.maxlen
        return True

 

front는 요소가 삭제될 때 이동을 한다. 포인터가 이동하는 else문부터 보자.

큐는 선입선출 방식이므로 디큐를 하면 당연히 front가 가리키는 요소가 삭제되어야 한다. 

 

self.q[self.front] = None

간단하게 front 포인터를 인덱스로 가지고 있는 큐의 요소를 None으로 바꾸면 삭제는 끝이 난다. 원형 큐이기 때문에 요소들을 일일히 앞으로 옮겨주는게 아니라 front 포인터만 한 칸 뒤로 (마지막 인덱스 쪽으로) 옮겨주기만 하면 된다. 

역시나 포인터를 옮겨줄 때, front의 다음 인덱스가 할당된 크기의 마지막 인덱스에 다다르면 % 키워드를 이용해서 첫번째 인덱스로 이동시켜주고, True를 반환해주면 해결된다. 

 

else문 위에 있는 if문은 단지 front 포인터가 가리키는 요소가 없을 때, 디큐할 게 없다고 False로 알려주기만 하면 되는 간단한 코드이다. 

 

 

이렇게 원형 큐(링 버퍼)를 구현하는 방식에 대해서 분석해보았다. 연결리스트까지는 아니어도 비슷하게 헷갈리는 개념이기도 하고, 원형 리스트는 매우 많이 사용되는 개념이라고 하니 꼭 복습하고 숙지해놓자!

---

마치며

원형큐... 뭔가 보고 있으면 신기하기도 하고 마음이 편안해진다.