큐(Queue)

큐(Queue)

큐는 자료를 보관할 수 있는 (선형) 구조이다. 이 점에서는 Stack과 Queue는 동일하다.

스택과 다른 점은 넣을 때에는 한 쪽 끝에서 밀어 넣어야 하고(인큐(enqueue)), 꺼낼 때에는 반대 쪽에서 뽑아 꺼내야 하는(디큐(dequeue)) 제약이 있다. 이러한 이유로 선입선출의 특징을 가진다.(FIFO: First-In Fisrt-Out)

일상 생활과 연관지어보면, 영화관이나 맛집에서 사람들이 길게 줄 서있는 모습과 비슷한 상황을 예로 들 수 있다. 이런 경우에도 먼저 줄 선 사람이 먼저 그 줄에서 나올 수 있기 때문이다.

Stack은 LinkedListStack으로 만들지 않고 ArrayStack으로 만들더라도 크게 부담이 되지 않았지만, Queue의 경우는 조금 다르다.

일반적인 배열로 큐를 구현하면 pop(0)연산 시 시간복잡도에서 비효율성이 발생한다. 왜냐하면 pop(0) 연산의 경우 0번째 index를 remove한 후, 남은 elements의 index를 한 칸씩 당기는 과정을 거치므로 시간복잡도 O(n) 이 된다.

반면, 이중 연결 리스트로 큐를 구현(LinkedListQueue)하면 이러한 연산 또한 상수시간 O(1) 에 해결할 수 있다.

from pythonds.basic.queue import Queue
Q = Queue()

큐의 활용

• 큐는 자료를 생성하는 작업과 그 자료를 이용하는 작업이 비동기적으로 (asynchronously) 일어나는 경우(즉, Producer와 Consumer가 따로 행동하는 경우)

• 자료를 생성하는 작업이 여러 곳에서 일어나는 경우(즉, Producer가 복수인 경우)

• 자료를 이용하는 작업이 여러 곳에서 일어나는 경우(즉, Consumer가 복수인 경우)

• 자료를 생성하는 작업과 이용하는 작업 모두가 여러 곳에서 일어나는 경우(즉, Producer/Consumer 모두 복수인 경우)

• 자료를 처리하여 새로운 자료를 생성하고, 나중에 그 자료를 또 처리해야 하는 작업(즉, 어떠한 행동을 한 뒤 그 결과물을 다시 Queue에 넣어주는 경우)

이러한 특징 때문에 큐는 운영체제나, 네트워크 스케줄링에서 많이 사용된다.