queue

python에서 queue 사용하는 방법

 

*queue는 FIFO의 구조를 가지고 있다. (선입 선출)

 

1. list 사용하기

list에서 push연산은 append를 사용해 구현할 수 있고, pop연산은 pop(0)을 사용해 구현할 수 있다. 그러나 pop연산의 시간복잡도는 O(N)이어서 큐에 적합한 자료구조라고는 볼 수 없다.

2. collections module의 deque 사용하기

deque는 double-ended queue로 양방향 큐이다.

앞, 뒤 양쪽 방향에서 데이터를 추가하거나 제거가 가능한 큐이다.

from collections import deque deq = deque() # 데이터 push deq.append() //데크의 오른쪽 끝에 데이터 push deq.appendleft() //데크의 왼쪽 끝에 데이터 push # 데이터 pop deq.pop() //데크의 오른쪽 끝 데이터 pop deq.popleft() //데크의 왼쪽 끝 데이터 pop # 데이터 rotate deq.rotate(num) //num이 양수면 오른쪽으로 배열을 돌리고 음수이면 왼쪽으로 돌림 # 데이터 remove deq.remove(x) //x를 데크에서 찾아 삭제

https://docs.python.org/3.8/library/collections.html#collections.deque

collections — Container datatypes — Python 3.8.11 documentation

 

3. queue module의 Queue 클래스 사용하기

데이터 추가/삭제는 O(1), 데이터 접근은 O(N)의 시간복잡도를 가진다.

# queue 만들기 import queue ex_queue = queue.Queue() # 데이터 push ex_queue.put() # 데이터 pop ex_queue.get() # queue size 확인 ex_queue.qsize()

https://docs.python.org/3/library/queue.html

queue — A synchronized queue class — Python 3.9.6 documentation