큐(Queue)

큐(Queue)

FIFO(First-In-First-Out)

데이터가 들어간 순서(Enqueue)가 빠져나가는 순서(Dequeue)와 동일한, 선입선출 구조

----🐢

주요 연산

enqueue(item)

큐 뒷부분(rear)에 요소 삽입

dequeue()

큐 앞부분(front)의 요소를 제거하여 반환

front() 또는 peek()

큐의 맨 앞(front) 요소를 확인 (제거하지 않음)

is_empty()

큐가 비었는지 확인

size()

큐에 있는 요소 개수를 반환

---🐢-

파이썬 큐 구현

리스트 큐 구현

# 비효율적 예시 (pop(0)가 O(n))
queue = []
queue.append(10)  # Enqueue
queue.append(20)  # Enqueue

item = queue.pop(0)  # Dequeue -> O(n)

리스트 앞쪽 요소를 제거하려면 내부적으로 모든 요소가 한 칸씩 당겨지므로 시간 복잡도 O(n) 이 발생

리스트를 사용해 큐를 직접 구현하는 것은 소규모 데이터에서는 괜찮지만, 대규모에는 비효율

 

collections.deque를 사용한 구현

deque(Double-Ended Queue)는 양쪽에서 삽입/삭제가 O(1) 상수 시간에 가능한 자료 구조

큐를 구현할 때는 보통 오른쪽 끝(append)으로 삽입(enqueue)하고, 왼쪽 끝(popleft)에서 제거(dequeue)하는 식으로 사용

from collections import deque

queue = deque()

# enqueue (오른쪽 끝에 삽입)
queue.append(10)  # deque([10])
queue.append(20)  # deque([10, 20])
queue.append(30)  # deque([10, 20, 30])

# dequeue (왼쪽 끝에서 제거)
item = queue.popleft()  # item=10, queue=deque([20, 30])

# peek (왼쪽 끝을 확인)
front_item = queue[0]  # 20

# is_empty
if not queue:
    print("큐가 비어있음")
else:
    print("큐에 원소가 있음")

# size
print("큐 크기:", len(queue))  # 2

deque는 내부적으로 양방향 연결 리스트와 비슷하게 동작해, 양 끝 삽입/삭제가 상수 시간에 가능하므로 큐를 구현하기에 적합

 

queue.Queue 클래스

파이썬 표준 라이브러리의 queue 모듈에는 Queue, LifoQueue(스택), PriorityQueue 등의 클래스가 제공

Queue 는 멀티스레드 환경에서 안전한(스레드 안전) 큐를 제공하고, 내부적으로 락(Lock) 등을 관리하여 동기화 문제를 해결

import queue

q = queue.Queue()  # 기본적으로 FIFO
q.put(10)   # Enqueue
q.put(20)
item = q.get()  # Dequeue (blocking 모드로 아이템 꺼냄)
print(item)     # 10

q.get() 호출 시 큐가 비어 있으면, 기본적으로 블록(block) 하고 대기합니다(옵션으로 timeout, block=False 지정 가능)

멀티쓰레드에서 소비자 스레드(consumer)가 get()으로 꺼내고, 생산자 스레드(producer)가 put()으로 넣는 방식을 쉽게 구현

--🐢--

큐 활용 사례

너비 우선 탐색(BFS)

그래프나 트리에서, 이웃 노드들을 먼저 탐색하기 위해 큐를 사용

시뮬레이션 (버퍼, 대기열, 프로세스 스케줄링 등)

은행 창구나 버스 승강장 등, 실제로도 선입선출이 필요한 상황을 큐로 모델링할 수 있음

멀티스레드 프로그래밍

작업 생산자(Producer)와 작업 소비자(Consumer)를 구현할 때, queue.Queue를 사용해 안전하게 작업을 넘겨줄 수 있음

 

# 활용 예시(BFS)

from collections import deque

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

    while queue:
        current = queue.popleft()
        print(current, end=" ")

        for neighbor in graph[current]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

# 예시 그래프
graph_example = {
    1: [2, 3],
    2: [4],
    3: [5],
    4: [6],
    5: [],
    6: []
}

bfs(1, graph_example)  # 1 2 3 4 5 6

시작 노드에서부터 가까운 노드(이웃)를 먼저 방문한 뒤, 해당 노드들의 이웃도 방문하여 점차 확장

-🐢---

큐 시간 복잡도

enqueue: O(1) (e.g. deque.append(), queue.Queue.put())

dequeue: O(1) (e.g. deque.popleft(), queue.Queue.get())

peek/front: O(1) (e.g. queue[0] in deque)

is_empty: O(1) (e.g. len(queue) == 0)

size: O(1) (e.g. len(queue))

 

>>> 단, 리스트의 pop(0)로 큐를 구현하면 dequeue가 O(n)이므로 비효율적이므로 주의

🐢----

큐 search

시간 복잡도: O(n)

>>> 큐의 구조상 검색을 위해서는 요소를 순차적으로 확인

>>> 큐의 각 요소를 하나씩 확인해야 하므로, 최악의 경우 n개의 요소를 모두 확인

queue = [10, 20, 30, 40, 50]

# 큐에서 값 찾기 (search)
def search(queue, target):
    for i, value in enumerate(queue):
        if value == target:
            return i  # 0-based 위치 반환
    return -1  # 값이 없는 경우

# 테스트
print(search(queue, 30))  # 출력: 2 (30은 큐에서 3번째 위치)
print(search(queue, 100)) # 출력: -1 (100은 없음)