ch9-6(leetcode 622). 원형 큐 디자인

* 해당 포스트는 <파이썬 알고리즘 인터뷰> 공부 후 정리 목적으로 작성되었습니다. *

 

leetcode 622번 ( https://leetcode.com/problems/design-circular-queue/ )

 

풀이방법 1. (오답노트)

(문제를 잘못 이해하고 풀었던 풀이다.)

코드는 다음과 같다. 

class MyCircularQueue(object):

    def __init__(self, k):
        self.size = k
        self.queue = []

    def enQueue(self, value):
        if len(self.queue) == self.size:
            return False
        
        self.queue.append(value)
        return True

    def deQueue(self):
        if len(self.queue) == 0:
            return False
        
        self.queue.remove(self.queue[0])
        return True
        
    def Front(self):
        if self.isEmpty():
            return -1
        return self.queue[0]
        
    def Rear(self):
        if self.isEmpty():
            return -1
        return self.queue[-1]
        
    def isEmpty(self):
        return len(self.queue) == 0
        
    def isFull(self):
        return len(self.queue) == self.size

 

원형 큐를 구현하고, 언어에서 기본으로 제공되는 큐(파이썬의 경우는 데크) 자료형을 사용하지만 않으면 되는 문제라고 생각했다. 그래서 큐를 빈 리스트 자료형으로 구현했었다. 

 

하지만 원형 큐(circular queue)의 중요한 장점 중 하나는 한정된 공간을 사용한다는 것이다. 빈 리스트[ ]를 사용해서 구현한다면 리스트에서 원소를 빼거나 추가하면서 메모리 상으로는 공간을 계속 추가해서 사용하게 된다. 

그러므로 원형 큐를 구현하려면 원형 큐를 매개변수 k를 받아서 초기화할 때, 미리 한정된 공간을 할당해 주어야 한다. 

 

풀이방법 2.

원형 큐를 초기화할 때 큐의 크기 k를 매개변수로 받는다. k로 원형 큐의 크기를 초기화하는 방법은 간단하다. 미리 리스트 배열의 크기대로 할당해 놓고 리스트의 크기를 추가(append)나 제거(pop)하는 메소드는 사용하지 않는 것이다. 

self.queue = [None] * k

 

원형 큐에는 사용할 큐 배열뿐만 아니라 다른 변수들도 필요하다. 

우선 배열의 최대값을 저장해 둬야 한다. 그래야 원소를 넣거나 뺄 때 배열의 최대값을 넘었는지 확인할 수 있다. 

(사실 배열의 최대값을 '넘었는지'를 확인하는 데에는 안 쓰이고, front 포인터와 rear 포인터 값을 이동시키는 데 쓰인다.)

def __init__(self, k):
        self.queue = [None] * k
        self.size = k	# max capacity
        self.front = 0	# pointer that points front element
        self.rear = 0	# pointer that points rear element

 

원형 큐처럼 정해진 크기의 공간이 할당되어 있고 2개의 포인터가 사용되는 자료구조를 구현한다면, 각 함수마다 각 포인터의 값을 어떻게 변화시킬지가 중요하다. 

 

front 포인터의 경우 맨 앞 원소의 인덱스를 가리키고, rear 포인터는 맨 뒤의 원소의 인덱스를 가리킨다. 그러므로 최대 k개의 인덱스가 있을 때, 실제로 값이 저장된 공간은 front 인덱스부터 rear 인덱스 사이 공간까지이다. 

 

dequeue()로 원소를 제거할 경우 먼저 제거할 원소가 있는지(큐가 비어있는지)를 확인한다. 

기존의 front 포인터가 가리키던 공간에다가는 null을 할당한 뒤 front 포인터를 한 칸 앞으로 증가시킨다. 

 

enqueue()로 원소를 추가할 경우 먼저 원소를 추가할 공간이 있는지(큐가 전부 차 있는지)를 확인한다. 

rear 포인터 자리에다가 새 원소를 추가하고, rear 포인터를 한 칸 이동시킨다. 

사실상 front 포인터는 실제 원소가 있는 인덱스를 가리키지만, rear 포인터는 맨 끝 원소의 인덱스 + 1을 가리키게 된다. 

 

다만 사용할 수 있는 공간은 맨 처음에 [None] * k로 총 k개의 인덱스만 할당해 두었기 때문에, 계속해서 front와 rear를 증가시키다 보면 금방 끝에 도달할 것이다. 만약 포인터가 k번째 인덱스를 찾으려고 한다면 값이 없어서 오류가 발생한다(0부터 k-1번째 인덱스까지만 있다). 

 

보통은 나눗셈 연산(modulo)을 사용해서 front와 rear 값이 계속 증가해도 0부터 k-1 범위 사이에만 존재하도록 처리할 수 있다. 어떤 수를 k로 나눌 경우 나머지는 무조건 0과 k-1 사이에 있기 때문이다. 

 

이를 참고해서 작성한 전체 코드이다.

(교재에서는 아이디어(인덱스가 k개인 초기화된 배열을 할당)만 참고하였고, 실제 코드는 교재를 참고하지 않고 작성하였다.)

class MyCircularQueue(object):

    def __init__(self, k):
        self.queue = [None] * k
        self.size = k
        self.front = 0
        self.rear = 0
        
    def enQueue(self, value):
        if self.isFull():
            return False
        
        self.queue[self.rear] = value
        self.rear = (self.rear + 1) % self.size
        return True
        
    def deQueue(self):
        if self.isEmpty():
            return False

        self.queue[self.front] = None
        self.front = (self.front + 1) % self.size
        return True
        
    def Front(self):
        if self.isEmpty():
            return -1
        return self.queue[self.front]
        
    def Rear(self):
        if self.isEmpty():
            return -1
        return self.queue[(self.rear)-1]
        
    def isEmpty(self):
        if self.front == self.rear and not self.queue[self.front]:
            return True
        return False
        
    def isFull(self):
        if self.front == self.rear and self.queue[self.front]:
            return True
        return False

 

 

 

 

참고한 포스트

https://docs.python.org/3/tutorial/datastructures.html