[자료구조] 큐(Queue)

큐는 간결하게 임시 데이터를 다루며 제약이 있는 배열이라는 점에서 스택과 비슷하다. 다만 데이터를 처리하는 순서가 다르므로 작업 중인 애플리케이션의 요구에 따라 선택한다.

 

극장에 줄 서 있는 사람들을 큐처럼 생각할 수 있다. 줄 맨 앞에 있는 사람이 그 줄을 떠나 가장 먼저 극장에 들어간다. 큐 역시 큐에 첫 번째로 추가된 항목이 가장 먼저 제거된다. 그래서 컴퓨터 과학자는 큐를 FIFO(first in, first out)이라 한다.

 

큐는 다음과 같은 제약을 포함한다.

• 데이터는 큐의 끝에만 삽입할 수 있다.
• 데이터는 큐의 앞에서만 읽을 수 있다.
• 데이터는 큐의 앞에서만 삭제할 수 있다.

빈 큐로 시작해서 큐의 동작을 알아보자. 먼저 5를 삽입하자. ( 스택 삽입은 push라고 하지만 큐 삽입은 put, add, enqueue 등으로 불린다. 즉 표준 명칭이 따로 없다. )

다음으로 3일 삽입하자.

다음으로 0을 삽입하자.

지금까지는 스택과 동일하게 동작했다. 하지만 큐는 앞에서부터 데이터를 삭제한다. 데이터를 삭제하려면 5부터 시작해야 한다.

다음으로 3을 삭제한다.

이제 큐에는 원소가 0 하나 남았다.

큐는 요청받은 순서대로 요청을 처리하므로 비동기식 요청을 처리하는 완벽한 도구이기도 하다. 이 외에 이륙을 기다리는 비행기나 진료를 기다리는 환자처럼 정해진 순서대로 이벤트가 발생해야 하는 실세계 시나리오를 모델링하는 데 흔하게 쓰인다.