💡파이썬 큐(Queue) 이론 및 예제

알고리즘 코딩 테스트를 준비하다 보면 다양한 자료구조를 만나게 됩니다.

그 중에서도 큐(Queue)는 스택과 함께 가장 기본적인 자료구조 중 하나입니다.

이번 글에서는 큐의 개념과 파이썬으로 구현하는 방법에 대해 알아보겠습니다.

큐(Queue)란?

Queue 단어 뜻

줄서기 Queue

• 알고리즘 코딩테스트에서 가장 자주 활용되는, 데이터를 저장하는 자료구조 중 하나 (BFS문제에서 자주 활용)
• 먼저 들어온 데이터가 먼저 나가는 선입선출(FIFO, First In First Out) 방식
• 입력과 출력이 각각 다른 방향에서 한쪽으로만 일어남
• 큐의 크기가 제한되어 있음 - 데이터의 크기만큼 크기가 결정됨. 따라서 C에서는 enQueue, deQueue 할때마다 메모리 재할당(realloc)이 필요하지만 파이썬에서는 신경 안써도 됩니다. 파이썬 메모리 관리자가 알아서 해줍니다.

복잡하면 위 이미지처럼, 먼저 들어온 차가 먼저 나가는 1차선 도로를 연상하면 됩니다. (줄서기)

(사고내기 싫으면) 중간의 차를 바로 빼올 수는 없습니다.

중간의 차를 빼오기 위해서는, 가장 앞의 차부터 순서대로 나가야 합니다. 역주행하는거 아니면...

사용자는 가장 앞의 데이터(차량)만 볼 수 있고, 새로운 데이터는 가장 뒤에만 들어갈 수 있습니다.

FIFO LILO 방식의 데이터 타입으로, 프로세스 메모리 구조의 힙(heap) 메모리와 같은 방식입니다. 이에 대해 궁금하시다면 저의 이전 포스팅을 참고해주세요.

 

파이썬으로 큐 구현하기

파이썬에서 큐를 구현하는 방법은 대표적으로 다음 두 가지 정도가 있습니다.

• 덱(deque) import해서 사용(강추★) : 양방향 push, pop이 가능한 자료구조입니다. 이미 잘 구현되어 있으므로 잘 활용하시면 됩니다. O(1)으로 성능이 좋습니다. list처럼 중간값을 빼올 수도 있긴 한데, 그 경우 list보다 성능이 떨어지므로 지양하셔야 합니다. (list처럼 index로 조회 가능. q[1], q[2], ...)
• list 활용 : 이전에 포스팅한 Stack(스택)으로 많이 활용되나, append(x) - pop(0) or insert(0, x) - pop() 조합으로 양방향 처리를 구현할 수 있기는 합니다. 다만 강력히 비추천하는 방법입니다. pop(0) 또는 insert(0, x)는 리스트의 왼쪽만 처리하므로 O(1)의 간단한 연산처럼 보일 수 있으나, 실제로는 우측의 모든 데이터를 당기고, 미는 O(n)의 연산이 필요하기 때문입니다.

from collections import deque

# deque 생성
q = deque()

# 방법 1
q.append('a')		# enQueue
q.popleft()			# deQueue

# 방법 2
q.appendleft('a')	# enQueue
q.pop()				# deQueue

q.empty()			# True

 

예제

boj의 뱀 문제가 큐를 활용한 유명한 문제 중 하나입니다.

풀이 방법은 다양하겠지만, 큐 활용을 잘 생각해보면 간단히 풀 수 있는(30줄 이내) 문제이니 풀어보시고 다른 사람들의 풀이도 꼭 참고해보시길 바랍니다.