원글 : 파이썬에서 큐(queue) 자료 구조 사용하기
큐의 특징 : 선입 선출, FIFO(First In First Out), 너비 우선 탐색(BFS)에 주로 사용 된다.
파이썬에서 큐 사용하기
파이썬에서 큐 자료구조를 사용하는 방법은 3가지 정도가 있다.
1. List 자료구조 사용하기
2. Collections 모듈의 deque 사용하기
3. queue 모듈의 Queue 클래스 사용하기
이 중 어느 것이 무조건 좋다고 할수 없고, 각 방법마다 장단점이 있다.
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
>>> print(queue)
[3, 4, 5]list 자료 구조의 .append(n) 함수를 사용하면 뒤에 데이터를 추가 할 수 있고, .pop(0) 함수를 이용하면 맨 앞의 데이터를 제거할 수 있기 때문에 큐 자료구조를 사용하는 효과가 난다.
그러나 성능적으로 문제가 있는데, 파이썬의 list 자료 구조는 무작위 접근에 최적화된 자료 구조이기 때문이다.
pop(0) 연산의 시간 복잡도는 O(N) 이어서 N이 커질 수록 연산이 매우 느려진다. 그래서 큐 자료구조를 사용하려고 한다면 list 자료 구조는 비추!
deque
double-ended queue의 약자로 데이터를 양방향에서 추가하고 제거할 수 있는 자료구조이다.
popleft() 라는 메서드를 사용하면 list의 pop(0) 메서드와 같은 효과를 가진다!
>>> from collections import deque
>>>
>>> queue = deque([1, 2, 3])
>>> queue.append(4)
>>> queue
deque[1, 2, 3, 4]
>>> queue.popleft()
1
>>> queue.popleft()
2
>>> queue
deque[3, 4] deque는 Queue와 다르게 appendleft(x) 라는 메서드가 있는데, 이 메서드를 사용하면 데이터를 맨 앞에서 삽입할수 있다고 한다.
deque의 popleft()와 appendleft(x) 메서드는 모두 O(1)의 시간 복잡도를 가지기 때문에, list 자료 구조보다 성능이 훨씬 뛰어나다!
그러나 단점도 있는데, 무작위 접근의 시간 복잡도가 O(N)이고, 내부적으로 linked list를 사용하고 있기 때문에 N번째 데이터에 접근하려면 N번 순회가 필요하다.
Queue
deque와 달리 방향성이 없기 때문에 데이터 추가와 삭제가 하나의 메서드로 처리된다!
데이터를 추가 할 때 : put(x) 메서드를 사용
데이터 삭제 : get() 메서드 사용
>>> from queue import Queue
>>> que = Queue()
>>> que.put(1)
>>> que.put(2)
>>> que.put(3)
>>> que.get()
1
>>> que.get()
2Queue의 성능은 deque와 똑같다. 데이터 추가/삭제는 O(1), 데이터 접근은 O(N)의 시간 복잡도를 가진다.
그렇다면 deque를 사용하지 queue를 쓸 이유가 없지 않나...?(개인적 생각)
queue와 deque에 관한 자세한 내용은 아래 파이썬 공식 레퍼런스를 참고하자.
