[Python] 큐(Queue)

큐(Queue)는 데이터를 선입선출(FIFO: First In, First Out) 방식으로 처리하는 자료구조다. 즉, 큐에 먼저 들어간 데이터가 먼저 나오는 구조다. 아래의 그림을 참고하면 이해하기 편하다.

 

그렇다면 파이썬에서는 큐를 어떻게 구현할 수 있을까?

 

1. list 범용 자료구조

가장 간단한 방법은 list를 사용하는 것이다.

queue.pop(0)을 이용하면 첫 번째 데이터를 제거할 수 있다.

# 큐 구현 (리스트 사용)
queue = []

# 데이터 삽입 (Enqueue)
queue.append(1)  # 큐에 1 추가
queue.append(2)  # 큐에 2 추가
queue.append(3)  # 큐에 3 추가


print("큐 상태:", queue) # [1, 2, 3]

# 데이터 삭제 (Dequeue)
first_item = queue.pop(0)  # 큐에서 가장 먼저 들어간 1 제거
print("제거된 요소:", first_item)

print("큐 상태:", queue) # [2, 3]


# 큐의 다음 요소를 미리 확인
next_item = queue[0]
print("다음 실행할 요소:", next_item) # 2

# 큐가 비었는지 확인
is_empty = len(queue) == 0
print("큐가 비었나요?", is_empty) # False

 

이런식으로 사용하면 list로 큐 자료구조를 흉내낼 수 있다. 하지만 이 방법은 성능 측면에서 좀 별로다.

파이썬의 list는 다른 언어의 배열처럼 무작위 접근(random access)에 최적화된 자료구조이기 때문에 pop(0)은 성능적으로 매우 불리한 연산이다.

참고로 이 연산의 시간 복잡도는 O(n)이다. (첫 번째 데이터를 제거한 후에 그 뒤에 있는 모든 데이터를 앞으로 한 칸씩 당겨줘야 하기 때문에)

 

2. deque 모듈

deque는 양쪽 끝에서 삽입과 삭제가 가능한 자료구조이지만, 큐처럼 한쪽 끝에서만 삽입, 다른 한쪽 끝에서만 삭제하도록 사용할 수 있다.

 

from collections import deque

# 큐 생성
queue = deque()

# 데이터 삽입 (Enqueue)
queue.append(1)        # 오른쪽 끝에 1 추가
queue.append(2)        # 오른쪽 끝에 2 추가
queue.appendleft(3)    # 왼쪽 끝에 3 추가

print("큐 상태:", queue) # deque([3, 1, 2])

# 데이터 삭제 (Dequeue)
first_item = queue.popleft()  # 큐에서 가장 왼쪽에 있는 3 제거
print("제거된 요소:", first_item) # 3

print("큐 상태:", queue) # deque([1, 2])

# 오른쪽 끝에 추가 (append) 및 왼쪽 끝에 추가 (appendleft)
queue.append(4)        # 오른쪽 끝에 4 추가
queue.appendleft(5)    # 왼쪽 끝에 5 추가

print("최종 큐 상태:", queue) # deque([5, 1, 2, 4])

# 큐의 끝에서 데이터 삭제
last_item = queue.pop()  # 오른쪽 끝에서 제거
print("오른쪽 끝에서 제거된 요소:", last_item) # 4

print("큐 상태:", queue) # deque([5, 1, 2])

 

deque의 popleft()와 appendleft(x)메서드는 모두 O(1)의 시간 복잡도를 가지기 때문에, 위에서 살펴본 list의 pop(0)와 insert(0, x) 대비 성능 상에 큰 이점이 있다.

 

 

 

 

3. queue.Queue 모듈

queue 모듈은 멀티스레드 환경에서 안전하게 큐를 사용할 수 있도록 설계된 클래스들을 제공한다.

 

기본 연산:

• put(item): 큐에 데이터를 추가
• get(): 큐에서 데이터를 제거하고 반환
• qsize(): 큐에 있는 항목의 수를 반환
• empty(): 큐가 비어있는지 확인
• full(): 큐가 가득 찼는지 확인

 

import queue

# 큐 생성
q = queue.Queue()

# 데이터 삽입 (Enqueue)
q.put(1)  # 큐에 1 추가
q.put(2)  # 큐에 2 추가
q.put(3)  # 큐에 3 추가

# 큐 크기 확인
print("큐 크기:", q.qsize()) # 3

# 데이터 삭제 (Dequeue)
first_item = q.get()  # 큐에서 가장 먼저 들어간 1 제거
print("제거된 요소:", first_item) # 1

# 큐가 비었는지 확인
print("큐가 비었나요?", q.empty()) # False

 

 

이 방법은 주로 멀티 쓰레딩(threading) 환경에서 사용되며, 내부적으로 라킹(locking)을 지원하여 여러 개의 쓰레드가 동시에 데이터를 추가하거나 삭제할 수 있다.

list나 deque와 달리 방향성이 없기 때문에 데이터 추가와 삭제가 하나의 메서드로 처리된다.

따라서, 데이터가 추가하려면 put(x) 메서드를 사용하고, 데이터를 삭제하려면 get() 메서드를 사용하면 된다.

 

Queue는 deque처럼 O(1) 데이터 추가/삭제 성능을 보이는데요. list나 deque와 달리 인덱스로 데이터 접근하는 것을 기본적으로는 지원하지 않으니 코딩테스트에서는  list나 deque을 사용하길 권한다.