큐(queue)

큐(queue)

스택(stack-LIFO)의 반대개념으로 FIFO(First In First Out)구조입니다.
즉 먼저 들어간 데이터가 먼저 빠져나오는 밀어내기 구조라고 보면 될 것 같습니다.
큐는 스트리밍(streaming),너비우선탐색(Breath First Search)등 소프트웨어 개발에서
널리 응용되고 있습니다.

list

파이썬에서 큐를 사용하는 가장 간단한 방법은 범용 자료 구조인 list를 사용하는 것입니다.
list 객체의 pop(0) 함수를 호출하면 첫 번째 데이터를 제거할 수 있습니다.

append

pop(0)함수를 호출하면 첫 번째 위치한 데이터를 제거할 수 있습니다.

하지만 이렇게 list를 큐 자료 구조의 효과를 내기 위해서 사용하는 것은 성능 측면에서 추천되지 않습니다.
파이썬의 list는 다른 언어의 배열처럼 무작위 접근(random access)에 최적화된 자료 구조이기 때문에
pop(0)또는 insert(0, x)는 성능적으로 매우 불리한 연산입니다. 이 두 연산은 시간 복잡도는 O(N)이기 때문에 담고 있는 데이터의 개수가 많아질 수록 느려집니다. 왜냐하면 첫 번째 데이터를 제거한 후에는 그 뒤에 있는 모든 데이터를 앞으로 한 칸식 당겨줘야 하고, 맨 앞에서 데이터를 삽입하려면 그 전에 모든 데이터를 뒤로 한 칸씩 밀어줘야 하기 때문입니다.

deque

double-ended queue의 약자로 데이터를 양방향에서 추가하고 제거할 수 있는 자료구조입니다.

collection 모듈에서 deque로 불러오며 list에는 없는 popleft()라는 메서드를 제공해줍니다.
popleft()를 사용해서 가장 앞에 있는 데이터를 꺼내준다.

또한 appendleft(x)라는 메서드를 제공합니다. 데이터를 맨 앞부터 삽입할 수 있으며,
데이터의 흐름은 앞에서 뒤로 흐르게 됩니다.

deque의 popleft()와 appendleft(x)메서드는 모두 O(1)의 시간 복잡도를 가지기 때문에,
위에서 살펴본 list의 pop(0)와 insert(0, x) 대비 성능 상에 큰 이점이 있으나,
무작원 접근(random access)의 시간 복잡도가 O(N)이라는 단점이 있습니다.
내부적으로 linked list를 사용하고 있기 때문에 i 번째 데이터에 접근하려면 맨 앞/뒤부터 i 번 순회(iteration)가 필요하기 때문입니다.

Queue

파이썬에서 큐를 사용하는 마지막 방법은 queue 모듈의 Queue 클래스를 사용하는 것입니다. 이 방법은 주로 멀티 쓰레딩(threading) 환경에서 사용되며, 내부적으로 라킹(locking)을 지원하여 여러 개의 쓰레드가 동시에 데이터를 추가하거나 삭제할 수 있습니다.
deque와 달리 방향성이 없기 때문에 데이터 추가와 삭제가 하나의 메서드로 처리됩니다.
따라서, 데이터가 추가하려면 put(x) 메서드를 사용하고, 데이터를 삭제하려면 get() 메서드를 사용합니다.

Queue의 성능은 deque와 마찬가지로 데이터 추가/삭제는 O(1), 데이터 접근은 O(N)의 시간 복잡도를 가집니다.