큐(queue)는 먼저 입력된 자료가 먼저 출력되는 First In First Out(FIFO)구조로 동작하는 자료구조를 의미한다. 나중에 입력된 자료가 먼저 출력되는 스택(stack)과는 반대되는 구조이다. 운영체제에서 스택은 프린터 작업 처리, 프로세스 관리 등 데이터나 요청이 입력된 순서대로 작업을 처리해야하는 상황에 주로 이용된다.
큐에는 선형 큐(linear queue), 환형 큐(circular queue), 링크드 큐(linked queue) 등이 있다. 일반적으로, 큐는 선형 큐를 의미하며 선형 큐의 문제점을 극복하기 위해 환형 큐, 링크드 큐 등이 고안되었다. 선형 큐의 문제점은 아래에서 자세하게 설명한다.
선형 큐는 큐의 가장 단순한 형태로써, 큐의 가장 앞을 가리키는 front와 가장 뒤를 가리키는 rear를 갖는다. 자료를 추가하면, 현재 rear가 가리키는 위치에 자료를 추가하고 rear는 1만큼 증가한다. 자료를 꺼내면, 현재 front가 가리키는 위치의 자료를 꺼내고 front는 1만큼 증가한다. 아래의 소스 코드는 C++를 이용한 선형 큐의 구현이다.
선형 큐는 구현이 매우 간단하다는 장점이 존재하지만, 아래의 그림과 같이 pop 연산을 반복하면 자료가 입력될 위치를 가리키는 front가 증가하여 큐의 일정 공간을 이용할 수 없게 되는 심각한 문제점이 존재한다.
선형 큐의 이러한 문제점을 해결하기 위해서는 큐에 저장된 모든 데이터를 큐의 앞쪽으로 옮기는 shifting 연산이 필요하다. shifting 연산의 구현은 아래와 같다.
shifting 연산은 큐의 private 멤버 함수로 선언되며, push 연산 시 rear가 큐의 capacity와 같고 front가 0보다 클 때 shift 함수가 호출된다. 선형 큐의 문제점을 해결하기 위한 수정된 push 연산의 구현은 아래와 같다.
환형 큐는 선형 큐에서 pop 연산이 반복될 수록 큐에 저장할 수 있는 공간이 감소하는 문제점을 극복하기 위해 고안되었다. 앞의 선형 큐에서는 이러한 문제점을 shift 함수를 구현하여 해결하였다. 그러나 shift 함수는 큐의 크기가 1,000,000이라면, 최대 999,999번 자료를 이동시켜야하는 매우 비효율적인 함수이다.
환형 큐는 비효율적인 shifting 연산 대신, 기존의 선형 큐를 원형(circular)으로 구성한 새로운 형태의 큐를 이용한다. 환형 큐의 구조는 아래와 같다.
환형 큐의 구조에서 보이듯이 환형 큐의 pop, push 연산은 큐의 처음과 끝이 연결된 것처럼 동작하도록 구현되어야 한다. 환형 큐의 pop, push 연산은 주로 모듈로(modulo, %)연산을 이용하여 구현되며, 환형 큐의 구현은 아래의 소스 코드와 같다.
.
