•
FIFO(First-In-First-Out) 구조를 가진 자료구조 : 선입선출
◦
예시 : 음식점 대기 줄, 게임 큐 대기
주요 연산
실제 파이썬에서의 메서드명과는 다릅니다.
연산 | 설명 |
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
Python
복사
리스트(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]
Python
복사
리스트의 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
Python
복사
