(Python/파이썬) 파이썬으로 큐 구현하기

파이썬에서 큐 자료구조를 사용하는 방법은 3가지 정도 존재한다.

 

1. list 자료구조 사용

2. Collections 모듈의 deque 사용

3. queue 모듈의 Queue 클래스 사용

 

1. list 자료구조 사용

list 자료 구조에서 .append() 함수를 사용하면 데이터 추가 가능하고, .pop()함수를 이용하면 맨 앞의 데이터 제거가 가능하기 때문에, 큐의 자료 구조를 사용하는 효과를 만들 수 있다.

하지만 파이썬에서 list 자료 구조는 무작위 접근에 효율적이고, pop()함수의 시간 복잡도는 O(n)으로 n이 커질 수록 시간복잡도도 같이 커지기 때문에 연산이 느려질 수 있다.

 

2. Collections 모듈의 deque 사용

deque의 popleft()와 appendleft()는 시간 복잡도가 O(1)로 데이터를 처리하는 속도가 매우 빠르다는 것을 알 수 있다.

from collections import deque
 
#deque 선언
dq = deque([])
 
#deque에 데이터 추가
dq.append(1)
dq.append(2)
dq.append(3)
dq.append(4)
print(dq)  #deque([1,2,3,4])
 
#deque의 첫번째 원소 제거
print(dq.popleft()) #1
print(dq.popleft()) #2
print(dq.popleft()) #3
print(dq.popleft()) #4
print(dq) #deque([])

 

3. queue 모듈의 Queue 클래스 사용

파이썬의 큐 모듈에서는 큐, 우선순위 큐, 스택을 제공하고 있다.  deque와 달리 방향성이 없기 때문에, 데이터의 추가와 삭제가 하나의 메서드로 처리 되게 된다.

put()을 사용하면 데이터가 추가되고 get()사용하면 데이터를 삭제 할 수 있다.

import queue
 
q = queue.Queue()
 
#q에 데이터 추가
q.put(1)
q.put(2)
q.put(3)
q.put(4)
 
# q에서 첫번째 원소 제거
print(q.get()) #1
print(q.get()) #2
print(q.get()) #3
print(q.get()) #4