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

들어가며

지난 포스팅에 이어서 이번에는 큐에 대해 공부한 내용을 정리해보았다.

큐

스택과 달리 큐(queue)는 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO, First In First Out) 방식으로 데이터 입/출력을 처리한다. 선입선출은 신선도를 고려한 편의점과 마트의 상품 진열 방식을 생각하면 이해하기 쉽다. 즉, 데이터를 맨 뒤에서 넣고 앞에서 꺼내는데, 이를 각각 인큐(enqueue)와 디큐(dequeue)라고 한다. 이와 같이 큐는 맨끝에서 맨앞으로 데이터를 밀어넣어 꺼내는 방식이며, 큐의 맨 앞의 원소를 프론트(front)라고 하고, 맨 뒤의 원소를 리어(rear)라고 한다. 예를 들어, 인큐와 디큐를 간단히 나타내면 다음과 같다.

queue = []
1. enqueue(1) → queue : [1]
2. enqueue(2) → queue : [1, 2]
3. enqueue(3) → queue : [1, 2, 3]
3. dequeue() → queue : 1, queue : [2, 3]

스택과 마찬가지로 큐 또한 배열을 통해 구현할 수 있는데, 배열로 큐를 구현하게 되면 한 가지 문제점이 있다. 이를 알아보기 위해 예시를 살펴보자. 먼저, 5개의 데이터가 다음과 같이 순서대로 저장되어 있다.

q = [1, 3, 5, 7, None]

여기서 새로운 데이터 2를 인큐하는 경우 맨 끝에 데이터가 저장된 q[3] 다음인 q[4]에 새로운 데이터 2가 저장되며, 복잡도는 O(1)로 비교적 적은 비용이 발생한다.

q = [1, 3, 5, 7, 2]

반대로 데이터 1을 디큐하는 경우에는 q[0]의 데이터를 꺼내야 하고, q[0] 뒤의 모든 데이터를 앞쪽으로 한 칸씩 앞당겨야 하므로 복잡도는 O(n)이 된다. 즉, 데이터를 꺼낼 때마다 이러한 작업을 수행한다면 프로그램의 효율성을 기대할 수 없다.

q = [None, 3, 5, 7, 2]
q = [3, None, 5, 7, 2]
q = [3, 5, None, 7, 2]
q = [3, 5, 7, None, 2]
q = [3, 5, 7, 2, None]

이러한 문제점을 보완하기 위해 이번에는 링 버퍼로 큐를 구현해보도록 하자. 직선 형태의 자료구조인 배열과는 달리 링 버퍼(ring buffer)는 배열 맨 끝과 맨 앞이 연결되는 자료구조로 동그라미 모양이라고 생각하면 이해하기 쉽다. 위에서 살펴본 배열로 구현한 큐에서는 디큐를 수행할 때마다 모든 원소의 자리를 앞쪽으로 당기는 자리 이동이 필요했지만, 링 버퍼는 맨 끝과 맨 앞이 연결되어 연속성이 생기므로 원소의 자리를 이동하는 대신 맨 앞의 기준이 되는 프론트만 바꾸어주면 된다. 이를 총으로 비유하자면, 아래 그림과 같이 일반 권총의 탄창(배열로 구현한 큐)과 리볼버 권총의 탄창이(링 버퍼로 구현한 큐)라고 할 수 있다. 단, 이 때 일반 권총의 탄창은 뒷 부분에서 총알을 넣는다고 가정한다.

링 버퍼로 고정 길이 큐를 구현하면 다음 코드와 같다. 아래 코드를 보면 알 수 있듯이 스택을 구현할 때와 굉장히 유사한 것을 알 수 있다.

class FixedQueue:
    def __init__(self, capacity: int) -> None:
        self.no = 0                     # 현재 데이터 개수 초기화
        self.front = 0                  # 프론트 초기화
        self.rear = 0                   # 리어 초기화
        self.capacity = capacity        # 큐의 크기 초기화
        self.queue = [None] * capacity  # 본체 초기화

    def __len__(self) -> int:
        return self.no

    def is_null(self) -> bool:
        return self.no <= 0

    def is_full(self) -> bool:
        return self.no >= self.capacity

스택을 구현할 때와 마찬가지로 데이터 인큐 전에 큐가 가득 차있는 경우와 큐가 비어있는 경우에 대한 예외 처리를 해주어야 하며, 이를 나타낸 코드는 다음과 같다.

class FixedQueue:

    # ..(생략)..

    class Full(Exception):
        pass

    class Null(Exception):
        pass

이어서 데이터 인큐를 구현해보자. 먼저, 큐가 가득 차있는 경우 예외 처리를 발생시키도록 하고, 큐 본체 배열의 리어에 새로운 데이터를 저장한다. 큐의 새로운 데이터가 저장됨에 따라 리어와 현재 데이터 개수를 증가시키는데, 이때, 리어가 큐의 크기와 같은 경우 본체 크기와 같거나 큰 인덱스에 해당하는 값은 본체 배열에 존재하지 않으므로 리어를 다시 본체 배열의 첫 번째 인덱스를 가리키도록 한다. 이를 나타낸 코드는 다음과 같다.

class FixedQueue:

    # ..(생략)..

    def enqueue(self, value: any) -> None:
        if self.is_full():
            raise FixedQueue.Full       # 예외 처리 발생
        self.queue[self.rear] = value
        self.rear += 1
        self.no += 1
        if self.rear == self.capacity:    # 리어와 큐의 크기가 같은 경우
            self.rear = 0                # 리어가 다시 맨 처음을 가리키도록 변경

이번에는 데이터 디큐를 구현해보자. 먼저, 큐가 비어있는 경우 예외 처리를 발생시키도록 하고, 큐 본체 배열의 프론트에 해당하는 데이터를 꺼낸다. 그리고 프론트는 증가시키고, 현재 데이터의 개수는 감소시키는데, 인큐 때와는 반대로 프론트가 큐의 크기와 같아지는 경우 본체 크기와 같거나 큰 인덱스에 해당하는 값은 본체 배열에 존재하지 않으므로 프론트를 다시 본체 배열의 첫 번째 인덱스를 가리키도록 한다. 이를 나타낸 코드는 다음과 같다.

class FixedQueue:

    # ..(생략)..

    def dequeue(self) -> any:
        if self.is_null():
            raise FixedQueue.Null       # 예외 처리 발생
        value = self.queue[self.front]
        self.front += 1
        self.no -= 1
        if self.front == self.capacity:    # 프론트와 큐의 크기가 같은 경우
            self.front = 0                # 프론트가 다시 맨 처음을 가리키도록 변경
        return value

이번에는 큐의 데이터를 디큐하지 않고도 프론트에 있는 데이터를 확인할 수는 픽(peek) 메소드를 구현해보자. 스택의 픽 메소드를 구현할 때와 마찬가지로 먼저 큐가 비어있는 상태를 확인하여 그에 따른 예외 처리를 발생시키도록 하고, 큐 본체에서 프론트 인덱스에 해당하는 데이터를 반환하도록 한다. 이를 나타낸 코드는 다음과 같다.

class FixedQueue:

    # ..(생략)..

    def peek(self) -> any:
        if self.is_null():
            raise FixedQueue.Null       # 예외 처리 발생
        return self.queue[self.front]

큐 또한 본체 배열의 원소 값을 직접 삭제할 필요가 없으므로 큐를 비유는 메소드는 다음과 같이 나타낼 수 있다.

class FixedQueue:

    # ..(생략)..

    def clear(self) -> None:
        self.no = self.front = self.rear = 0

이어서 원하는 데이터를 큐 본체 배열에서 검색하는 메소드를 구현해보자. 스택의 find 메소드와 마찬가지로 큐의 find를 구현할 때에도 현재 데이터 개수만큼 선형 검색을 수행한다. 다만, 링 버퍼로 구현한 상태이기 때문에 본체 배열의 시작과 끝은 프론트와 리어로 지칭한다는 사실을 인지해야 한다. 즉, 현재 데이터 개수만큼 선형 반복을 수행하되, 본체 배열에서 꺼낼 첫 번째 데이터는 프론트 인덱스에 해당하는 데이터가 되어야 하므로 새로운 인덱스를 구하는 연산을 먼저 수행한다. 이를 나타낸 코드는 다음과 같다.

class FixedQueue:

    # ..(생략)..

    def find(self, value: any) -> int:
        for i in range(self.no):                    # 데이터 개수만큼 선형검색하되,
            idx = (i + self.front) % self.capacity  # front → rear 순으로 스캔하도록 연산
            if self.queue[idx] == value:
                return idx
        return -1

마치며

혼자 공부하며 느낀 점인데 스택과 큐의 구조는 똑같다고 해도 될 정도이다. 다만, 후입선출이냐 선입선출이냐에 따라서 사용되는 변수에만 차이가 있는 것 같다. 링 버퍼를 활용하여 다른 구조의 큐도 구현할 수도 있는데, 예를 들어 길이가 20개인 큐에 한 꺼번에 25개의 데이터를 넣었을 때 앞의 5개 데이터는 버리는 형식이다. 이러한 개념과 활용을 알고리즘 문제에 적용한다면 더욱 빠르게 성장할 것이라고 생각한다.