자료구조 - 큐(Queue)

데이터 삽입 시 가장 마지막에 저장하고 데이터 추출 시 가장 앞에 있는 원소를 출력하는 자료구조

흔히 식당에서 기다릴 때 먼저온 사람부터 들어가는 선착순을 생각하면된다. 

 

 

 

위의 그림처럼 큐는 가장 앞의 원소를 가르키는 Front, 가장 뒤를 가르키는 Rear 로 위의 두 위치를 관리하며 큐에 원소를 삽입 혹은 추출 시 Front 와 Rear 의 값을 증가시키며 위의 동작을 수행한다. 하지만 큐는 정해진 크기 내에서는 결국 앞에 비어있는 공간으로 자료를 옮겨 주는(그만큼 시간을 소모)  작업을 해야 지속적으로 사용할 수 있는 단점이 있다. 그래서 개발자들은 단순 선형 큐의 단점을 개선해 아래 그림과 같은 원형 큐로 발전시켰다. 

 

 

원형 큐 또한 정해진 길이 내에서 초과가 발생하면 오류가 발생하지만 빈 공간이 있을 경우에는 다음과 같이 술래잡기처럼 포인터가 이동하며 결과적으로는 기존의 단순 선형 큐의 단점을 개선할 수 있다. 

 

대표적 예시로는 CPU 의 프로세스 Job 큐가 있으며 이 경우에도 프로세스 스케쥴링에 따라 조금 다를 수 있지만 기본적으로는 가장 앞에 있는 가장 먼저 온 프로세스를 먼저, 그리고 가장 마지막에 온 프로세스를 큐의 마지막에 삽입해준다.