List
List는 컴퓨터 프로그래밍에서 사용되는 데이터 구조로, 항목들의 순서를 유지하는 컬렉션이다.일련의 항목을 저장하고 접근하고 조작하는 데 사용된다. 다른 용어로는 배열(Array)이라고도 불리며, 동적 배열(Dynamic Array)로 구현되기도 한다.
List 사용
list객체의 pop(0) 함수를 호출하면 첫 번째 데이터를 제거할 수 있다.
pop(0) 또는 insert(0, x)는 시간복잡도가 O(N)이기 때문에 담고 있는 데이터의 개수가 많아질수록 느려진다.
큐 자료 구조의 효과를 내기 위해 사용하는 것은 비추천한다.
Deque
collections 모듈의 deque는 double-ended queue의 약자로 데이터를 양방향에서 추가하고 제거할 수 있는 자료구조이다.
Deque 사용
deque는 list에는 없는 popleft()라는 메소드를 제공한다. 이는 pop(0)과 같은 기능을 한다.
deque의 popleft()와 appendleft(x)는 모두 O(1)의 시간 복잡도를 가지기 때문에, 위에서 살펴본 list의 pop(0)와 insert(0, x) 대비 성능 상에 큰 이점이 있다.
Queue
큐(Queue)는 선형 자료구조로, 데이터를 저장하는 컬렉션이다. 선입선출(First-In-First-Out, FIFO) 원칙에 따라 동작한다.
이는 가장 먼저 들어온 항목이 가장 먼저 나가는 구조를 말한다.
Queue 사용
deque와 달리 방향성이 없기 때문에 데이터 추가와 삭제가 하나의 메서드로 처리된다.
따라서 데이터를 추가하려면 put(x)를 사용하고, 데이터를 삭제하려면 get()를 사용한다.
Queue의 성능은 deque와 마찬가지로 데이터 추가/삭제는 O(1), 데이터 접근은 O(N)의 시간 복잡도를 가진다.
[출처] [자료구조] 큐(queue) (파이썬)|작성자 연수구 주정뱅이
