큐(Queue) 완벽 정리 + 응용 문제

1. 큐란?

큐는 한쪽에서는 데이터가 들어오고, 다른 쪽에서는 데이터가 나가는 선형 자료구조로, 먼저 들어온 데이터가 먼저 나가는 구조(FIFO, First In First Out)입니다.

2. 큐의 기본 동작

enqueue(item): 큐에 데이터를 넣는다.
dequeue(): 큐에서 가장 먼저 들어온 데이터를 꺼낸다.
front(): 큐에서 가장 앞에 있는 데이터를 확인한다.
is_empty(): 큐가 비었는지 확인한다.

3. 파이썬 기본 큐 구현

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

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        if not self.is_empty():
            return self.items.pop(0)
        return None

    def front(self):
        if not self.is_empty():
            return self.items[0]
        return None

    def is_empty(self):
        return len(self.items) == 0

주의! 위 구현은 pop(0)가 O(n)이라 비효율적입니다.

4. 효율적인 큐 - collections.deque 사용

from collections import deque

queue = deque()

queue.append(10)    # enqueue
queue.append(20)

print(queue[0])     # front 출력: 10
print(queue.popleft()) # dequeue: 10
print(queue.popleft()) # dequeue: 20

5. 큐 응용문제 1: BFS (너비 우선 탐색)

문제: 그래프를 큐를 사용해 너비 우선 탐색으로 방문하는 코드를 작성하세요.

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)

    while queue:
        node = queue.popleft()
        print(node, end=' ')
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

bfs(graph, 'A')  # 출력: A B C D E F

6. 큐 응용문제 2: 프린터 큐 (우선순위 큐 변형)

문제: 여러 문서가 우선순위를 가지고 프린터 큐에 대기 중입니다. 현재 큐의 맨 앞 문서보다 우선순위가 높은 문서가 있으면 현재 문서는 뒤로 이동합니다. 주어진 문서의 출력 순서를 구하세요.

예:

문서 우선순위 = [2, 1, 3, 2]
몇 번째로 인쇄되는지 알고 싶은 문서 위치 = 2 (우선순위 3)

from collections import deque

def printer_queue(priorities, location):
    queue = deque([(i, p) for i, p in enumerate(priorities)])
    print_order = 0

    while queue:
        cur = queue.popleft()
        if any(cur[1] < other[1] for other in queue):
            queue.append(cur)
        else:
            print_order += 1
            if cur[0] == location:
                return print_order

# 테스트
print(printer_queue([2, 1, 3, 2], 2))  # 출력: 1

7. 큐 응용문제 3: 캐시 구현 (LRU 정책)

문제: 큐를 사용해 캐시 크기 제한(LRU 정책) 내에서 가장 오래된 데이터를 제거하며 새 데이터를 넣는 코드를 작성하세요.

from collections import deque

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = deque()

    def access(self, item):
        if item in self.cache:
            self.cache.remove(item)
        elif len(self.cache) >= self.capacity:
            self.cache.popleft()
        self.cache.append(item)

    def get_cache(self):
        return list(self.cache)

cache = LRUCache(3)
cache.access('A')
cache.access('B')
cache.access('C')
print(cache.get_cache())  # ['A', 'B', 'C']
cache.access('B')
print(cache.get_cache())  # ['A', 'C', 'B']
cache.access('D')
print(cache.get_cache())  # ['C', 'B', 'D']

8. 큐 정리표

특징	설명
구조	FIFO (First In First Out)
주요 연산	enqueue, dequeue, front, is_empty
시간복잡도	deque 사용 시 모든 연산 O(1)
응용분야	BFS, 프린터 큐, 프로세스 스케줄링, 캐시 관리

728x90