Python의 대기열 구현 이해

로

자료 구조는 프로그래밍 분야에서 핵심적인 역할을 합니다. 데이터를 효율적으로 관리하고 활용할 수 있는 방식으로 조직하는 데 필수적입니다. 그중에서도 큐(Queue)는 비교적 단순하면서도 매우 유용한 자료 구조입니다.

본 글에서는 큐의 개념과 파이썬(Python)에서의 구현 방법을 상세히 알아보겠습니다.

큐란 무엇인가?

큐는 선입선출(FIFO, First-In-First-Out) 원칙을 따르는 선형 자료 구조입니다. 이는 스택(Stack) 자료 구조와 반대되는 특징입니다.

영화관 매표소 줄을 큐에 비유해 생각해 볼 수 있습니다. 아래 그림을 통해 큐를 좀 더 자세히 살펴보겠습니다.

매표소에서 줄을 서는 상황을 보면, 두 번째 사람은 첫 번째 사람이 업무를 완료해야만 매표소에 갈 수 있습니다. 즉, 먼저 줄을 선 사람이 먼저 업무를 처리하게 됩니다. 이러한 방식이 바로 FIFO(First-In/First-Out) 원칙입니다. 우리는 일상생활에서 이와 유사한 큐 형태를 자주 볼 수 있습니다.

큐 자료 구조도 동일한 원칙을 따릅니다. 이제 큐가 무엇이고, 어떤 원리로 작동하는지 이해하셨을 것입니다. 다음으로는 큐 자료 구조에서 수행할 수 있는 주요 연산에 대해 알아보겠습니다.

큐의 기본 연산

스택과 마찬가지로 큐 자료 구조에서도 두 가지 핵심적인 연산을 수행할 수 있습니다.

인큐(Enqueue, 데이터 삽입)

큐의 가장 뒤쪽에 새로운 데이터를 추가하는 연산입니다. 이 위치를 ‘후단(rear)’이라고 합니다.

디큐(Dequeue, 데이터 삭제)

큐의 가장 앞쪽에서 데이터를 제거하는 연산입니다. 이 위치를 ‘전단(front)’이라고 합니다.

큐 연산에 대한 이해를 돕기 위해 아래 그림을 참조하십시오. 한 장의 그림이 천 마디 말보다 낫다는 말이 있죠.

큐에 대한 좀 더 자세한 정보를 얻기 위해 몇 가지 보조 함수를 추가할 수 있습니다. 보조 함수의 수에는 제한이 없지만, 지금은 가장 중요한 기능에 집중해 보겠습니다.

후단(rear) 확인

큐의 가장 뒤쪽에 있는 첫 번째 요소를 반환합니다.

전단(front) 확인

큐의 가장 앞에 있는 첫 번째 요소를 반환합니다.

비어있음(empty) 확인

큐가 비어 있는지 여부를 반환합니다.

지금까지 큐에 대한 개념적인 설명을 다루었습니다. 지루하셨나요? 개념적인 내용은 때로는 지루하게 느껴질 수 있습니다.

그러나 개념을 제대로 이해하지 못하면 코드를 작성할 수 없습니다. 구현하기 전에 개념을 완전히 파악해야 합니다. 이제 코드를 직접 작성해 볼 시간입니다. 너무 걱정하지 마세요.

온라인 컴파일러를 이용하시거나, PC에 파이썬이 설치되어 있다고 가정하고 진행하겠습니다.

큐 구현

큐 구현은 프로그래머에게 15분 이상 걸리지 않습니다. 이 튜토리얼을 끝까지 보시면 몇 분 안에 큐를 구현할 수 있을 것입니다.

파이썬에서는 다양한 방식으로 큐를 구현할 수 있습니다. 여러 가지 큐 구현 방법을 단계별로 살펴보겠습니다.

#1. 리스트를 이용한 큐 구현

파이썬의 내장 데이터 유형인 리스트(list)를 사용하여 클래스 내에서 큐를 구현해 보겠습니다. 모듈 없이 처음부터 큐 자료 구조를 구현하는 다양한 단계를 안내할 것입니다.

1단계: Queue라는 클래스를 정의합니다.

class Queue:
    pass

2단계: 큐의 데이터를 저장할 변수가 필요합니다. elements라는 이름의 리스트를 사용합니다.

class Queue:
    def __init__(self):
        self.elements = []

3단계: 큐에 데이터를 삽입하려면 클래스에 메서드가 필요합니다. 이 메서드는 이전 섹션에서 이미 언급했듯이 enqueue라고 합니다.

이 메서드는 일부 데이터를 인자로 받아 큐(elements)에 추가합니다. 리스트의 append 메서드를 사용하여 큐의 끝에 데이터를 추가할 수 있습니다.

class Queue:
    # ...
    def enqueue(self, data):
        self.elements.append(data)
        return data

4단계: 큐에서 데이터를 제거하는 dequeue 메서드가 필요합니다. 리스트의 pop 메서드를 사용할 것입니다. 눈치채셨을 수도 있겠죠?

리스트의 pop 메서드는 주어진 인덱스의 요소를 삭제합니다. 인덱스를 제공하지 않으면 리스트의 마지막 요소를 삭제합니다.

여기서는 리스트의 첫 번째 요소를 삭제해야 하므로, 인덱스 0을 pop 메서드에 전달해야 합니다.

class Queue:
    # ...
    def dequeue(self):
        return self.elements.pop(0)

이제 큐의 기본 연산을 구현했습니다. 그러나 큐 연산이 제대로 작동하는지 확인하려면 몇 가지 보조 함수가 필요합니다. 보조 함수도 함께 작성해 보겠습니다.

5단계: rear() 메서드는 큐의 마지막 요소를 가져오는 데 사용됩니다. 리스트의 음수 인덱싱을 활용하여 큐의 마지막 요소를 쉽게 가져올 수 있습니다.

class Queue:
    # ...
    def rear(self):
        return self.elements[-1]

6단계: front() 메서드는 큐의 첫 번째 요소를 가져오는 데 사용됩니다. 리스트의 인덱싱을 사용하여 큐의 첫 번째 요소를 가져올 수 있습니다.

class Queue:
    # ...
    def front(self):
        return self.elements[0]

7단계: is_empty() 메서드는 큐가 비어 있는지 확인하는 데 사용됩니다. 리스트의 길이를 확인하여 큐가 비어있는지 확인할 수 있습니다.

class Queue:
    # ...
    def is_empty(self):
        return len(self.elements) == 0

큐 자료 구조 구현이 완료되었습니다! 이제 Queue 클래스를 사용하여 객체를 만들어 보겠습니다.

class Queue:
    # ...
if __name__ == '__main__':
    queue = Queue()

이제 Queue 객체가 생성되었습니다. 일련의 연산을 통해 이 객체를 테스트해 보겠습니다.

  • is_empty 메서드를 사용하여 큐가 비어 있는지 확인합니다. True를 반환해야 합니다.
  • enqueue 메서드를 사용하여 숫자 1, 2, 3, 4, 5를 큐에 추가합니다.
  • is_empty 메서드는 False를 반환해야 합니다. 확인해 보세요.
  • front 및 rear 메서드를 각각 사용하여 전단 및 후단 요소를 출력합니다.
  • dequeue 메서드를 사용하여 큐에서 요소를 제거합니다.
  • front 요소를 확인합니다. 요소 2를 반환해야 합니다.
  • 이제 큐에서 모든 요소를 제거합니다.
  • is_empty 메서드는 True를 반환해야 합니다. 확인해 보세요.

이 정도면 큐 구현을 테스트하기에 충분할 것입니다. 위에서 언급한 각 단계를 코드로 작성하여 큐를 테스트해 보겠습니다.

코드를 직접 작성해보셨나요?

아니라면, 걱정하지 마세요.

아래 코드를 참조하세요.

class Queue:
    def __init__(self):
        self.elements = []
    def enqueue(self, data):
        self.elements.append(data)
        return data
    def dequeue(self):
        return self.elements.pop(0)
    def rear(self):
        return self.elements[-1]
    def front(self):
        return self.elements[0]
    def is_empty(self):
        return len(self.elements) == 0
if __name__ == '__main__':
    queue = Queue()
    ## checking is_empty method -> True
    print(queue.is_empty())
    ## adding the elements
    queue.enqueue(1)
    queue.enqueue(2)
    queue.enqueue(3)
    queue.enqueue(4)
    queue.enqueue(5)
    ## again checking is_empty method -> False
    print(queue.is_empty())
    ## printing the front and rear elements using front and rear methods respectively -> 1, 5
    print(queue.front(), end=' ')
    print(queue.rear())
    ## removing the element -> 1
    queue.dequeue()
    ## checking the front and rear elements using front and rear methods respectively -> 2 5
    print(queue.front(), end=' ')
    print(queue.rear())
    ## removing all the elements
    queue.dequeue()
    queue.dequeue()
    queue.dequeue()
    queue.dequeue()
    ## checking the is_empty method for the last time -> True
    print(queue.is_empty())

위 코드를 실행하면 다음과 유사한 결과를 얻을 수 있습니다.

True
False
1 5
2 5
True

리스트 데이터 유형을 사용하여 큐 자료 구조를 직접 구현할 수 있다는 것을 알았습니다. 위에서 구현한 큐는 다른 프로그래밍 언어에서 큐를 구현하는 방법을 이해하는 데 도움이 될 것입니다.

이제 이전에 했던 것처럼 객체를 생성하여 프로젝트의 다른 프로그램에서 위에서 구현한 큐 클래스를 사용할 수 있습니다.

리스트 데이터 유형을 사용하여 큐를 처음부터 구현했습니다. 큐를 위한 내장 모듈이 있을까요? 네! 내장 큐 구현이 있습니다. 함께 살펴보겠습니다.

#2. collections 모듈의 deque를 이용한 큐 구현

deque는 양방향 큐(double-ended queue)로 구현되어 있습니다. 양쪽 끝에서 요소를 추가하고 제거하는 것을 지원하므로 스택과 큐로 모두 사용할 수 있습니다. deque를 사용하여 큐를 구현하는 방법을 살펴보겠습니다.

deque는 이중 연결 리스트(doubly linked list)라는 다른 자료 구조를 사용하여 구현되었습니다. 따라서 요소 삽입 및 삭제 성능이 일정합니다. 연결 리스트의 중간에 있는 요소에 접근하는 데 O(n) 시간이 걸리지만, 큐에서는 중간 요소에 접근할 필요가 없으므로 큐로 사용하는 데 문제가 없습니다.

deque에서 제공하는 다양한 메서드를 살펴보겠습니다.

  • append(data) – 큐에 데이터를 추가하는 데 사용합니다.
  • popleft() – 큐에서 첫 번째 요소를 제거하는 데 사용합니다.

전단, 후단, is_empty 메서드에 대한 대체 메서드는 없습니다. 전단 및 후단 메서드 대신 전체 큐를 출력할 수 있습니다. 또한, len 메서드를 사용하여 큐가 비어 있는지 여부를 확인할 수 있습니다.

이전에 큐 구현을 테스트하기 위해 일련의 단계를 거쳤습니다. 여기에서도 동일한 단계를 따르겠습니다.

from collections import deque
## creating deque object
queue = deque()
## checking whether queue is empty or not -> True
print(len(queue) == 0)
## pushing the elements
queue.append(1)
queue.append(2)
queue.append(3)
queue.append(4)
queue.append(5)
## again checking whether queue is empty or not -> False
print(len(queue) == 0)
## printing the queue
print(queue)
## removing the element -> 1
queue.popleft()
## printing the queue
print(queue)
## removing all the elements
queue.popleft()
queue.popleft()
queue.popleft()
queue.popleft()
## checking the whether queue is empty or not for the last time -> True
print(len(queue) == 0)

위 코드를 실행하면 다음과 유사한 결과를 얻을 수 있습니다.

True
False
deque([1, 2, 3, 4, 5])
deque([2, 3, 4, 5])
True

#3. queue 모듈의 Queue를 이용한 큐 구현

파이썬에는 큐 구현을 위해 Queue라는 클래스를 제공하는 queue라는 내장 모듈이 있습니다. 이 모듈은 앞서 직접 구현한 것과 유사한 기능을 제공합니다.

먼저 Queue 클래스의 다양한 메서드를 살펴보겠습니다.

  • put(data) – 데이터를 큐에 추가합니다.
  • get() – 큐에서 첫 번째 요소를 제거하고 반환합니다.
  • empty() – 큐가 비어 있는지 여부를 반환합니다.
  • qsize() – 큐의 길이를 반환합니다.

위 메서드를 사용하여 큐를 구현해 보겠습니다.

from queue import Queue
## creating Queue object
queue_object = Queue()
## checking whether queue is empty or not -> True
print(queue_object.empty())
## adding the elements
queue_object.put(1)
queue_object.put(2)
queue_object.put(3)
queue_object.put(4)
queue_object.put(5)
## again checking whether queue is empty or not -> False
print(queue_object.empty())
## removing all the elements
print(queue_object.get())
print(queue_object.get())
print(queue_object.get())
## checking the queue size
print("Size", queue_object.qsize())
print(queue_object.get())
print(queue_object.get())
## checking the whether queue_object is empty or not for the last time -> True
print(queue_object.empty())

위 코드의 실행 결과를 확인해 보세요.

True
False
1
2
3
Size 2
4
5
True

Queue 클래스에는 이 외에도 여러 메서드가 있습니다. dir 내장 함수를 사용하여 탐색해 볼 수 있습니다.

결론

큐 자료 구조와 그 구현에 대해 배우셨기를 바랍니다. 큐는 FIFO(First-In-First-Out) 순서로 처리해야 하는 여러 상황에서 유용하게 활용될 수 있습니다. 큐가 필요한 상황을 맞이했을 때, 이 글에서 배운 내용을 활용하여 문제를 해결해 보세요.

파이썬 마스터에 관심이 있으신가요? 다음 학습 자료들을 확인해 보세요.

즐거운 코딩하세요! 🙂 👨‍💻