주요 연산

실제 파이썬에서의 메서드명과는 다릅니다.

연산 설명
enqueue 데이터를 큐에 삽입
dequeue 큐에서 가장 앞 데이터를 제거
peek 가장 앞 데이터를 조회
is_empty 큐가 비었는지 확인
size 큐에 들어있는 데이터 개수 반환

큐 구현(in Python)

from collections import deque

# deque = double-ended queue의 약자
queue = deque()
queue.append(1) # 큐 상황 : 1
queue.append(2) # 큐 상황 : 1, 2

# appendleft : 줄을 새치기한다고 생각해주세요
queue.appendleft(3) # 큐 상황 : 3,1,2
queue.popleft() # 큐 상황 : 1,2

print(queue.popleft()) # 1

queue.append(5) # 큐 상황 : 2,5
queue.append(6) # 큐 상황 : 2,5,6

리스트(list) vs 큐(deque)

# 리스트를 이용한 큐 구현
queue = [4,5,6]
queue.insert(0,3)
queue.insert(0,2)

print(queue) # [2,3,4,5,6]
print(queue.pop(0)) # 2
print(queue.pop(0)) # 3

print(queue) # [4,5,6]

리스트의 pop(0), insert() 함수를 이용하면 언뜻 보기엔 큐를 구현한 것과 같아보입니다. 하지만 성능 측면에선 아닌데요, 리스트는 다른 언어의 배열처럼 무작위 접근(random access)에 최적화된 자료구조라서 시간복잡도가 O(N)이 됩니다. 왜냐하면 리스트의 맨 앞에 삽입하면, 그 뒤의 원소들은 한 칸씩 뒤로 밀려나는 형태이거든요. 반대로 맨 앞의 원소를 빼내면, 그 뒤의 원소들은 한 칸씩 당겨집니다.

하지만 큐의 popleft(), appendleft() 는 시간복잡도가 O(1)입니다. 맨 앞에 원소를 추가하거나 빼낸다고 해서 다른 기존 원소들이 한 칸씩 밀리거나 당겨지지 않는다는 소리입니다(= 연결리스트 사용).

무작위 접근이란?

배열은 인덱스만 알면 곧바로 해당 원소에 접근이 가능합니다. 이처럼 원하는 인덱스에 바로 접근할 수 있는 방식을 무작위 접근(Random Access) 또는 **직접 접근(Direct Access)**라고 합니다.

큐(Queue)와 덱(Deque)의 차이가 뭔가요?

항목 큐(Queue) 덱(Deque)
삽입 위치 뒤(rear) 앞(left) / 뒤(right) 모두 가능
삭제 위치 앞(front) 앞(left) / 뒤(right) 모두 가능
파이썬 구현 collections.deque 또는 queue.Queue collections.deque

그럼 덱만 사용하고 리스트 안 쓰면 되지 않나요?

큐는 오히려 중간 인덱스의 값을 사용하고 싶을 때는 더 느립니다. 연결리스트 방식은 무작위 접근이 아닌, 앞에서부터 순차적으로 다음 값으로 넘어가는 자료구조이기 때문입니다. 연결리스트라는 자료구조의 특징 때문에 무작위 접근이 불가합니다. 그렇기에 무작위 인덱스 접근이 필요할 때는 리스트를 사용하는 게 성능에 좋습니다.

큐 관련 알고리즘(BFS)

from collections import deque

def bfs(graph, start):
	visited = set()
	queue = deque([start])
	
	while queue:
		node = queue.popleft()
		
		if node not in visited:
			print(node, end=' ')
			
			visited.add(node)
			for neighbor in graph[node]:
				if neighbor not in visited:
					queue.append(neighbor)
					
# 예시
# i번째 인덱스 노드는 i번째 배열 내 원소들과 연결되어있다고 생각해주세요
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'E'],
    'D': ['B', 'F'],
    'E': ['C'],
    'F': ['D']
}

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

참고자료