[자료구조] 파이썬으로 큐(Queue) 구현하기

큐(Queue)

큐

큐는 한쪽 끝에서 자료를 추가하고 한쪽 끝에서 자료를 꺼내는 선형 자료 구조로 가장 먼저 들어온 자료가 가장 먼저 나가는 FIFO(First In First Out) 방식입니다.
롤에서 랭크 게임을 매칭할 때 "큐를 돌린다"라고 표현하죠. 게임 시작 버튼을 먼저 누른 사람이 먼저 게임을 할 수 있도록 처리해줍니다. 큐는 이처럼 요청이 들어온 순서대로 일을 처리할 때 사용합니다.

큐의 동작 방식

큐가 동작하는 방식을 알아봅시다. 크기가 5인 큐를 만듭니다.

Queue = [None, None, None, None, None]

우선 큐는 가장 먼저 들어온 데이터를 가리키는 front 변수와 가장 나중에 들어온 데이터의 위치를 가리키는 back 변수가 필요합니다.

처음에는 큐가 비어있으므로 front와 back 둘다 첫 번째 인덱스 0을 가리키고 있습니다.

front = 0
back = 0

데이터 하나가 들어오면 back이 가리키고 있던 인덱스에 값을 집어넣고 back을 다음 인덱스로 옮깁니다. first는 가장 먼저 들어온 값을 기억하고 있어야 하므로 그대로 있습니다.

Queue[back] = A
Queue = [A, None, None, None, None]
first = 0
back = back + 1 = 1

큐에 값을 세 번 더 넣으면 front는 여전히 첫 번째 인덱스를 back은 마지막 인덱스를 가리키고 있을 것입니다.

Queue[back] = D
Queue = [A, B, C, D, None]
front = 0
back = back + 1 = 4

이제 큐에서 값을 하나 빼봅시다. front가 가리키고 있는 인덱스에서 값을 반환하고 front를 한 칸 옮깁니다.

Queue = [None, B, C, D, None]
front = 1
back = 4

큐에서 값을 하나 더 빼고 또 값을 넣어보겠습니다.

Queue = [None, None, C, D, None]
first = 2
back = 4

Queue[back] = E
Queue = [None, None, C, D, E]
front = 2
back = ?

이제 back은 어디를 가리켜야 할까요? 뒤에 남은 공간이 없으므로 큐의 크기를 늘리고 인덱스 5를 가리키면 되겠죠. 그런데 바로 크기를 늘리기엔 뭔가 아쉽습니다. 인덱스 0, 1의 값이 비어있기 때문이죠. 비어있는 자리가 지금처럼 한 두개라면 큰 문제가 없겠지만 수백개라면 메모리 낭비가 커지겠죠. 그렇다면 back이 인덱스 0을 가리키도록해서 다음 값을 Queue[0] 자리에 넣을 수는 없을까요?

Queue = [F, None, C, D, E]
front = 2
back = 1

원형 큐(Circular Queue)

여기서 원형 큐(Circular Queue) 개념이 등장합니다. back이 마지막 인덱스를 가리키고 있지만 큐의 공간이 남아있을 때, 비어있는 공간을 활용해 효율성을 높이기 위해서이죠.

원형 리스트

원형 큐를 구현하려면 back의 인덱스를 증가시킬 때 단순히 1을 더하는게 아니라 1을 더한 값에 전체 크기를 나눈 나머지를 할당해주면 됩니다.

back = (back + 1) % len(Queue)

우리가 본 예제에서는 (4 + 1) % 5를 back에 할당해주면 되겠죠.

큐의 기본 연산

파이썬의 리스트를 이용해서 큐를 구현해보도록 하겠습니다. 큐는 기본적으로 다음과 같은 연산들이 필요합니다.

Q.enqueue(e): back에 요소 e를 추가
Q.dequeue(): front의 요소를 반환하면서 제거
Q.first(): front의 요소를 제거하지 않고 반환
Q.is_empty(): 큐가 비어있으면 True를 반환

뼈대 코드

class ArrayQueue:
    def __init__(self):
    """빈 큐를 생성합니다"""
    def __len__(self):
    """큐의 길이를 반환합니다."""
    def _resize(self, n):
    """큐가 가득 찼을 때 큐를 확장합니다."""
    def is_empty(self):
    """큐가 비어있으면 True를 반환합니다."""
    def first(self):
    """front의 요소를 제거하지 않고 반환합니다"""
    def enqueue(self, e):
    """back에 요소를 추가합니다"""
    def dequeue(self):
    """front의 요소를 반환하고 제거합니다."""

초기화

class Empty(Exception):
    pass

class ArrayQueue:
    DEFAULT_CAPACITY = 10

    def __init__(self):
        self._data = [None] * ArrayQueue.DEFAULT_CAPACITY
        self._size = 0
        self._front = 0


    def __len__(self):
        return self._size

    def _resize(self, n):
        pass

DEFAULT_CAPACITY: 큐를 생성할 때 기본 크기를 10으로 지정
self._data: 데이터를 관리하는 리스트
self._size: 큐에 저장된 데이터의 개수
self._front: 제일 첫번째 값의 인덱스를 저장할 변수
back은 명시적으로 지정하지 않고 self._front + self._size - 1로 계산

앞선 글 스택에서처럼 Exception을 상속받아 예외처리할 클래스도 만들어줍니다. _resize는 조금 있다가 만들도록 하겠습니다.

dequeue

    def is_empty(self):
        return self._size == 0

    def first(self):
        if self.is_empty():
            raise Empty("Queue is empty")
        return self._data[self._front]

    def dequeue(self):
        if self.is_empty():
            raise Empty("Queue is empty")
        answer = self._data[self._front]
        self._data[self._front] = None
        self._front = (self._front + 1) % len(self._data)
        self._size -= 1
        return answer

is_empty와 first는 그리 복잡하지 않습니다. dequeue는 우선 큐가 비어 있는지 확인하고 비어있다면 오류를 발생시킵니다.

큐에 값이 들어있다면 반환할 값을 answer에 저장합니다. answer에 값을 저장해뒀으니 그 자리에 None을 할당해 값을 비워줍니다.

그리고 front를 한 칸 앞으로 옮기는데 앞서 설명했듯 이때 단순히 1을 더하는 것이 아니라 큐의 길이로 나눈 나머지를 할당해 줍니다. 이렇게 하면 (큐에 빈 공간이 남아있다면) front가 큐의 마지막 인덱스인 9를 가리키고 있었더라도 큐를 확장해 (9+1)을 가리키도록 하는 것이 아니라 (9+1)%10인 0을 가리키게 합니다.

enqueue

    def enqueue(self, e):
        if self._size == len(self._data):
            self._resize(2 * len(self._data))
        avail = (self._front + self._size) % len(self._data)
        self._data[avail] = e
        self._size += 1

만일 큐가 가득찼다면 큐의 크기를 두 배로 늘려줍니다.
새로운 값이 들어갈 인덱스를 가리킬 변수 avail을 선언하고 거기에 가장 마지막 값을 가리키는 인덱스의 바로 다음 인덱스(back + 1)를 큐의 크기로 나눈 나머지를 할당해줍니다.

resize

큐가 가득 차있는 상태에서 큐에 값을 더 넣으려면 크기가 더 큰 큐를 생성해서 기존의 값을 복사해주어야 합니다. 다만 원형 큐의 경우 원래 값의 순서와 인덱스의 순서가 다르기 때문에 값을 복사할 때 순서를 재정렬해주어야 합니다.

원형 큐 리사이징

    def _resize(self, n):
        old = self._data
        self._data = [None] * n
        walk = self._front
        for i in range(self._size):
            self._data[i] = old[walk]
            walk = (walk + 1) % len(old)
        self._front = 0

전체 코드

class Empty(Exception):
    pass


class ArrayQueue:
    DEFAULT_CAPACITY = 10

    def __init__(self):
        self._data = [None] * ArrayQueue.DEFAULT_CAPACITY
        self._size = 0
        self._front = 0

    def __len__(self):
        return self._size

    def _resize(self, n):
        old = self._data
        self._data = [None] * n
        walk = self._front
        for i in range(self._size):
            self._data[i] = old[walk]
            walk = (walk + 1) % len(old)
        self._front = 0

    def is_empty(self):
        return self._size == 0

    def first(self):
        if self.is_empty():
            raise Empty("Queue is empty")
        return self._data[self._front]

    def enqueue(self, e):
        if self._size == len(self._data):
            self._resize(2 * len(self._data))
        avail = (self._front + self._size) % len(self._data)
        self._data[avail] = e
        self._size += 1

    def dequeue(self):
        if self.is_empty():
            raise Empty("Queue is empty")
        answer = self._data[self._front]
        self._data[self._front] = None
        self._front = (self._front + 1) % len(self._data)
        self._size -= 1
        return answer