queue
- 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out) 구조로 저장하는 형식
- stack과 반대되는 개념
- 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 경우 사용
python 에서 queue 사용하기
- list 자료구조 사용
- Collections 모듈의 deque 사용하기
- queue 모듈의 Queue 클래스 사용하기
1. List 자료구조 사용
queue = [1,2,3]
queue.append(4)
queue.append(5)
print(queue)
>>> [1,2,3,4,5]
queue.pop(0)
>>> 1
queue.pop(0)
>>> 2
queue.pop(0)
>>> 3
- list의 append() 함수를 이용하면 뒤에 데이터를 추가할 수 있음
- pop(0) 함수를 사용하면 맨 앞의 데이터를 뺄 수 있음
-> 큐 자료구조를 사용하는 효과
- but, 시간 복잡도에서 O(N), N이 커질 수록 느려진다.
2. deque
from collections import deque
que = deque()
que.append(1)
que.append(2)
que.append(3)
print(que)
>>> deque([1, 2, 3])
que.popleft()
>>> 1
que.popleft()
>>> 2
- O(1)의 시간복잡도를 가지고 있기 때문에 성능이 뛰어나다.
- but, 무작위 접근의 시간 복잡도가 O(N)이고, 내부적으로 linked list를 사용하고 있기 때문에 N번째 데이터에 접근하기 위해 N번 순회가 필요.
- appendleft() : 맨 앞에 데이터를 추가
3. queue
from queue import Queue
que = Queue()
que.put(1)
que.put(2)
que.put(3)
que.get()
>>> 1
que.get()
>>> 2
- deque와 달리 방향성이 없기 때문에 데이터의 추가와 삭제가 하나의 메서드로 처리된다.
- 데이터 추가 : put()
- 데이터 삭제 : get()