[자료구조] 큐(Queue)

큐는 선입선출(FIFO) 자료구조이며, 스택과 마찬가지로 큐도 삽입하는 연산은 push, 꺼내는 연산은 pop이라고 합니다. 큐의 동작 방식은 작업 대기열, 이벤트 처리 등에서 사용하고 있습니다.

 

 

 

큐의 동작 이해

구분	정의	설명
연산	boolean isFull()	큐에 들어 있는 데이터 개수가 maxsize인지 확인해 boolean값을 반환합니다.
	boolean isEmpty()	큐에 들어 있는 데이터가 하나도 없는지 확인해 boolean값을 반환합니다.
	void push(ItemType item)	큐에 데이터를 푸시합니다.
	ItemType pop()	큐에서 마지막에 푸시한 데이터를 팝하고, 그 데이터를 반환합니다.
상태	int front	큐에서 가장 마지막에 팝한 위치를 기록합니다.
	int rear	큐에서 가장 최근에 푸시한 데이터의 위치를 기록합니다.
	ItemType data[maxsize]	큐의 데이터를 관리하는 배열입니다. 최대 maxsize개의 데이터를 관리합니다.

 

 

원형 큐

큐는 front의 다음부터 rear까지를 큐가 관리하는 데이터 입니다. 그런데 선형 큐를 사용하게 되면 front 이전의 공간을 활용하지 못해 메모리가 낭비되는 상황이 발생합니다. 이를 개선하려면 원형 큐를 사용해야 하는데, 선형 큐보다 구현이 복잡하지만 낭비되는 공간을 없앨 수 있습니다.
(하지만 파이썬은 리스트의 길이를 자동으로 관리하므로 원형 큐를 사용할 필요는 없습니다.)

 

 

덱을 큐처럼 사용하기

덱은 Double Ended Queue를 줄인 말입니다. 큐의 양 끝에서 삽입, 삭제할 수 있는 큐를 구현한 것으로 큐를 구현할 때는 덱을 사용하는 것이 좋습니다. 일반 큐보다 덱의 성능이 더 우수하다고 하는데, 실제 그런지 확인해봅시다.

from collections import deque
import time

lst = list(range(100000))
dq = deque(range(100000))

# pop(0) 성능 측정
start_time = time.time()
for i in range(100000):
   lst.pop(0)
print("pop(0) 소요시간: ", time.time() - start_time)
# 0.8856086730957031

# popleft() 성능 측정
start_time = time.time()
for i in range(100000):
   dq.popleft()
print("popleft() 소요 시간: ", time.time() - start_time)
# 0.007999897003173828

 

 

큐 문제 풀기

# 요세푸스 문제
# N명의 사람이 원 형태로 서 있습니다. 
# 각 사람은 1부터 N까지 번호표를 갖고 있습니다.
# 그리고 임의의 숫자 K가 주어졌을 때 다음과 같이 사람을 없앱니다.
# - 1번 번호표를 가진 사람을 기준으로 K번째 사람을 없앱니다.
# - 없앤 사람 다음 사람을 기준으로 하고 다시 K번째 사람을 없앱니다.
# 마지막에 살아있는 사람의 번호를 반환하는 solution() 함수를 구현해주세요.
from collections import deque
import time

def solution(N, K):
   # 1부터 N까지의 번호를 queue에 추가
   queue = deque(range(1, N+1))

   while len(queue) > 1:
      for _ in range(K-1):
         queue.append(queue.popleft())
         queue.popleft()
      return queue[0]

start_time = time.time()
print(solution(5, 2))
print("소요시간: ", time.time() - start_time)