Kwangmin Kim - Data Structure (6) Queue

1 Queue

정의: 큐 (Queue)

큐는 먼저 삽입된 데이터가 먼저 제거되는 FIFO(First-In, First-Out) 자료구조다.

삽입(Enqueue): 항상 꼬리(tail)에 추가 — \(O(1)\)
추출(Dequeue): 항상 머리(head)에서 제거 — \(O(1)\)
Python에서는 collections.deque로 효율적인 큐를 구현한다

큐(queue)는 먼저 삽입된 데이터가 먼저 추출되는 자료구조(data structure)다. (First-In First-Out)
딥러닝 모델에 들어가는 데이터 순서대로 들어가는데 먼저 들어간 데이터는 먼저 나오게 할때 사용되는 자료 구조이다.

직관적 이해: 편의점 계산대 줄서기와 같다. 먼저 줄을 선 사람이 먼저 계산하고 나간다(FIFO). 새로운 손님은 항상 줄의 맨 뒤에 선다. 스택이 “가장 나중 사람 우선”이라면, 큐는 “가장 먼저 온 사람 우선”이다.

동작 원리 (시각화):

초기 큐: head → [3]→[5]→[9] ← tail

enqueue(8):  head → [3]→[5]→[9]→[8] ← tail

dequeue():   head → [5]→[9]→[8] ← tail  (3이 추출됨)
             반환값: 3

2 왜 필요한가

먼저 들어온 데이터를 먼저 처리해야 하는 작업 큐(task queue)에 활용된다.
BFS(너비 우선 탐색): 큐를 이용해 레벨 순서로 탐색한다.
운영체제의 프로세스 스케줄링에서 FIFO 방식의 큐가 사용된다.
데이터 스트림 처리, 메시지 큐, 프린터 작업 대기열 등에 활용된다.

3 연결 리스트로 큐 구현

큐를 연결 리스트로 구현하면, 삽입과 삭제에 있어서 \(O(1)\) 을 보장할 수 있다.
연결 리스트로 구현할 때는 머리(head)와 꼬리(tail) 두 개의 포인터를 가진다.
머리(head): 남아있는 원소 중 가장 먼저 들어 온 데이터를 가리키는 포인터
꼬리(tail): 남아있는 원소 중 가장 마지막에 들어 온 데이터를 가리키는 포인터

3.1 삽입 연산

삽입할 때는 꼬리(tail) 위치에 데이터를 넣는다.
값으로 8을 갖는 새로운 데이터가 삽입되었을 때 예시)

3.2 삭제 연산

삭제할 때는 머리(head) 위치에서 데이터를 꺼낸다.
하나의 데이터를 삭제할 때의 예시)

아래 코드는 연결 리스트로 큐를 구현한다. head가 출구(dequeue), tail이 입구(enqueue)를 담당한다.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class Queue:
    def __init__(self):
        self.head = None
        self.tail = None

    def enqueue(self, data):
        node = Node(data)
        if self.head == None:
            self.head = node
            self.tail = node
        # 꼬리(tail) 위치에 새로운 노드 삽입
        else:
            self.tail.next = node
            self.tail = self.tail.next

    def dequeue(self):
        if self.head == None:
            return None

        # 머리(head) 위치에서 노드 꺼내기
        data = self.head.data
        self.head = self.head.next

        return data

    def show(self):
        cur = self.head
        while cur:
            print(cur.data, end=" ")
            cur = cur.next


queue = Queue()
data_list = [3, 5, 9, 8, 5, 6, 1, 7]

for data in data_list:
    queue.enqueue(data)

print("\n전체 노드 출력:", end=" ")
queue.show()

print("\n[원소 삭제]")
print(queue.dequeue())
print(queue.dequeue())
print(queue.dequeue())

print("[원소 삽입]")
queue.enqueue(2)
queue.enqueue(5)
queue.enqueue(3)

print("전체 노드 출력:", end=" ")
queue.show()
# 출력:
# 전체 노드 출력:  3 5 9 8 5 6 1 7
# [원소 삭제]
# 3
# 5
# 9
# [원소 삽입]
# 전체 노드 출력:  8 5 6 1 7 2 5 3

핵심 포인트

Python의 리스트 pop(0)은 \(O(N)\)이므로 큐로 사용하면 안 된다.
collections.deque의 appendleft()/popleft()는 \(O(1)\)이므로 BFS에 반드시 deque를 사용한다.
연결 리스트 큐는 tail 포인터 덕분에 enqueue가 \(O(1)\)로 보장된다.

3.3 큐 동작 속도: 연결 리스트 vs. 리스트 자료형

다수의 데이터를 삽입 및 삭제할 때에 대하여, 수행 시간을 측정할 수 있다.
단순히 Python의 리스트 자료형을 이용할 때보다 수행 시간 관점에서 효율적이다.

list.pop(0)과 연결 리스트 큐의 성능 차이를 10만 개 데이터로 측정한다. 앞에서 제거할 때 list는 \(O(N)\), 연결 리스트는 \(O(1)\)이므로 데이터가 많을수록 차이가 커진다.

import time

data_list = [i for i in range(100000)]

start_time = time.time()

queue = []
for data in data_list:
    queue.append(data)
while queue:
    queue.pop(0)

print(f"Elapsed time: {time.time() - start_time} seconds.")
print(queue)

start_time = time.time()

queue = Queue()
for data in data_list:
    queue.enqueue(data)
while queue.head != None:
    queue.dequeue()

print(f"Elapsed time: {time.time() - start_time} seconds.")
queue.show()
# 출력:
# Elapsed time: X.XXX seconds.  (list pop(0) 방식: 상대적으로 느림)
# []
# Elapsed time: X.XXX seconds.  (연결 리스트 방식: 상대적으로 빠름)
# (빈 큐, 출력 없음)

4 응용 분야

BFS(너비 우선 탐색): 탐색할 노드를 큐에 넣어 레벨 단위로 탐색한다. 최단 경로 탐색의 핵심이다.
운영체제 프로세스 스케줄링: CPU 자원을 FIFO 방식으로 할당한다.
메시지 큐(Message Queue): Kafka, RabbitMQ 등 분산 시스템에서 이벤트를 순서대로 처리한다.
딥러닝 데이터 로더: 미니배치를 큐에 적재하여 GPU와 CPU가 병렬로 작업한다.
프린터 대기열: 인쇄 작업을 큐로 관리하여 순서를 보장한다.