[Python 자료구조] Queue (큐) 구현하기

Queue(큐) ?!

큐는 FIFO (First - In - First - Out) 로써 먼저 삽입된 item 순으로 꺼내어진다고 이해하면 쉬울거 같습니다.

큐의 종류에는 순차적인 큐와 원형 큐(원형으로 이루어진 Queue)가 있습니다.

 

Python에서 Queue 구현하기

Python에서는 collections 모듈의 deque 를 통해 큐 자료구조를 구현합니다.

 

Deque (덱) 객체

deque는 스택과 큐를 합친 자료구조로 가장자리에 원소를 넣거나 뺄 수 있습니다.

deque([iterable[, maxlen]])	deque의 초기화 함수 (리스트, queue의 최대 길이를 넣을 수 있다)
append(x)	원소 x를 deque 맨 오른쪽에 삽입
popleft()	deque에 가장 왼쪽에 있는 원소를 제거하며 그값을 리턴
clear()	모든 원소를 지운다.
len(deque)	deque의 원소수를 알아낼 때

 

스택과 달리 큐를 list로 이용하지 않는 이유는 !?

스택에서 list.append와 list.pop()을 이용했던 것 처럼 list.append와 list.pop(0)을 이용하면 리스트를 큐처럼 사용할 수 있습니다. 하지만 pop()의 time complexity는 O(1)인 반면에 pop(0)의 time complexity는 O(N)이기 때문에 시간이 오래 걸립니다. 따라서 시간복잡도를 고려해 리스트는 큐로 사용하지 않습니다.

 

 

Deque를 이용하여 Queue 구현하기

deque - Init

deque ([iterable[, maxlen]]) 을 이용해 초기화 할 수 있습니다.

from collections import deque

# 빈 큐 만들기
deque1 = deque()

# 원소가 있는 큐 만들기
deque2 = deque([1, 2, 3])

# 큐 최대 길이 명시하기(원소 수가 maxlen에 도달했을 때 새로운 값을 넣으면, 앞서 넣은 값은 사라지고-pop이 일어남- 뒤에 새 값이 들어감)
deque3 = deque(maxlen=5)

 

deque - append(x)

원소 x를 넣을 때, append()을 사용합니다.

 

from collections import deque
y_deque = deque()
my_deque.append(3)

print(my_deque) #deque([3]

 

deque - popleft()

큐에서 원소를 삭제할 때 사용합니다.

my_deque = deque([1,2,3])

while my_deque:
  print("{}을/를 pop했습니다".format(my_deque.popleft())

""" 
1을/를 pop했습니다
2을/를 pop했습니다
3을/를 pop했습니다
"""

 

deque - clear()

모든 원소를 지웁니다.

my_deque = deque([1,2,3])

print("전:", my_deque)

my_deque.clear()

print("후:", my_deque)
"""
전: deque([1, 2, 3])
후: deque([])
"""

 

deque - len(deque)

len() 함수를 사용하여 deque의 원소 수를 알아낼 수 있습니다.

my_deque = deque([1,2,3], maxlen=5)

print(len(my_deque)) # 3

 

 

한번에 정리한 Python - Queue 자료구조