Queue란?(자료구조)

큐(Queue)란 ‘줄’, ‘줄을 서서 기다리다’라는 뜻을 가지고 있습니다. 일상 생활에서 이러한 큐 구조를 많이 접할 수 있는데요. 예를 들면, 은행창구에서 번호표를 뽑아 기다린다거나, 신호를 기다리는 자동차 등은 일종의 큐 구조에 해당한다고 볼 수 있습니다!

이러한 큐 구조에 공통적으로 적용되는 특징이 있는데요, 그것은 바로 FIFO(First In, First Out) 또는 LILO(Last in Last Out)구조라는 것입니다. 즉 먼저 들어간 것이 가장 먼저 나오고, 가장 마지막에 들어간 것이 가장 마지막에 들어갑니다. 먼저 온 사람에게 먼저 기회를 준다는 점에서, 가장 민주적이라 볼 수 있겠지요?

이러한 큐 구조는 컴퓨터 과학 전반에 자주 쓰이는 자료구조입니다. 가장 대표적인 예로 ‘버퍼(Buffer)’를 들 수 있는데, 데이터가 마구 입력이 되면, 이를 처리하지 못할 수가 있습니다. 이를 해결 하기 위해, 순서대로 입력된 데이터를 보관해두는 곳을 바로 버퍼라고 합니다. 은행에 가면 바로 행원을 만날 수 없어서 번호표를 뽑고 의자에서 기다리는 것은 버퍼와 비슷한 개념에 해당합니다.

<그림 1> 큐의 구조

큐의 주요 기능

큐의 주요 기능을 소개하기 위해서 일상생활로 다시 돌아와 봅시다. 우리는 은행에 가면 대기표를 뽑아 대기를 합니다.(Enqueue) 그리고 앞사람들의 일처리가 모두 끝나면, 자신의 차례가 되어 은행업무를 봅니다.(Dequeue) 큐는 시점을 대기표를 뽑는 인원으로 봅니다. 즉 번호표를 가장 먼저 뽑아서 기다리는 사람(전단 : Front)과, 가장 마지막에 뽑아서 기다리는 사람(후단 : Rear)까지의 ‘줄’이라고 생각하시면 됩니다. 즉 대기열에 들어가는 것을 삽입(Enqueue), 대기열에서 나오는 것을 제거(Dequeue) 그리고 그 대기열의 선두를 전단(Front), 대기열의 마지막을 후단(Rear)라고 합니다.