큐의 정의

"큐"는 여러 개의 데이타 항목들이 일정한 순서로 나열된 자료 구조이다. 스택과는 달리 한쪽 끝에서는 삽입만 할 수 있고, 삭제는 반대쪽 끝에서만 할 수 있도록 되어 있다.

큐의 원리

큐는 매표소에서 표를 사기 위해 기다리는 대기자 열과 같은 원리를 가진다. 대기자 열에는 먼저 온 사람부터 차례로 대기자들이 늘어서 있다. 앞쪽 끝에서는 기다리던 사람이 표를 사서 빠져나가고 (삭제), 뒤쪽 끝에서는 새로운 사람들이 대기자 열로 들어온다(삽입).

큐의 성질

큐에 저장된 데이타 항목들 중에 먼저 삽입된 것은 먼저 삭제되고, 나중에 삽입된 것은 나중에 삭제된다. 그래서 큐를 선입 선출 리스트 (First-In-First-Out:FIFO) 라 부른다. 후입 선출법을 사용하는 스택 과는 상반된 성질을 가진다.

큐의 종류

선형 큐(linear queue)
환형 큐(circular queue)

큐에는 한 방향으로 데이타 항목들이 삽입/삭제되는 선형 큐와 시작점과 끝점이 서로 연결되어 있는 환형 큐가 있다.

선형 큐

선형 큐의 구조

큐는 여러 개의 데이타 항목들이 하한부터 차례로 저장되는 모양을 가진다. 새로운 데이타 항목의 삽입은 rear에서 일어나고, 이 위치는 rear 포인터라는 지시자가 가리킨다. 데이타 항목의 삭제는 front에서 일어나며, 이 위치는 front 포인터라는 지시자가 가리킨다.

front 포인터와 rear 포인터는 초기에 하한에서 시작하여 삽입과 삭제가 반복됨에 따라 상한쪽으로 이동한다.

선형 큐의 동작

선형 큐에 데이타 항목 삽입

데이타 항목을 삽입하려면 큐의 rear 포인터를 하나만큼 증가시켜 주고 그 위치에 데이타 항목을 저장한다.

<삽입전>

<삽입후>

실제 큐는 용량이 제한되어 있으므로 데이타 항목을 삽입하기 전에 여유 공간이 있는지 검사해야 한다.

선형 큐에서 full 검사

삽입이 계속되어 rear 포인터가 상한에 도달하면 더이상 삽입이 불가능한 상태가 된다.

그런데 다음과 같은 경우는 큐에 데이타 항목을 삽입할 공간이 있음에도 불구하고, rear 포인터가 상한에 도달했기 때문에 큐가 가득찬 것으로 된다.

이런 문제를 해결하기 위해 환형 큐를 이용한다.

선형 큐에서 데이타 항목 삭제

데이타 항목을 삭제하려면 큐의 front 포인터를 하나만큼 증가시키고 그 위치에 있는 데이타 항목을 삭제한다.

<삭제전>

<삭제후>

데이타 항목을 삭제하기 전에 큐에 삭제할 항목이 남아있는지 검사해야 한다.

선형 큐에서 empty 검사

저장된 데이타 항목들의 앞쪽 끝을 가리키는 front 포인터는 뒤쪽 끝을 가리키는 rear 포인터보다 큰 값을 가질 수 없다. 만약 front 포인터와 rear 포인터가 같은 값을 가진다면 큐에 저장된 데이타가 없다는 뜻이다.

환형 큐

환형 큐의 구조

환형 큐는 선형 큐의 문제점을 보완하기 위해 만들어진 자료구조이다. 삽입과 삭제 동작은 선형 큐와 같지만, 큐의 상한과 하한이 서로 연결된 고리 모양을 하고 있어, 사실상 큐의 한계가 없는 것과 같다.

선형 큐에서와 마찬가지로 삽입 위치를 가리키는 rear 포인터와 삭제 위치를 가리키는 front 포인터가 있다. 두개의 포인터는 초기에 시작점에서 출발하여 삽입과 삭제가 일어남에 따라 그 값이 하나씩 증가하여 시계 방향으로 이동한다. 포인터가 큐의 끝점에 있을 때 삽입이나 삭제가 일어나면 포인터가 reset 되어 다시 시작점을 가리킨다.

환형 큐의 동작

환형 큐에 데이타 항목 삽입

데이타 항목을 삽입하려면 큐의 rear 포인터를 하나만큼 증가시켜 주고 그 자리에 데이타 항목을 저장한다. 만약 rear 포인터가 끝점을 가리키고 있으면 reset 시켜 준다.

데이타 삽입시에 큐의 용량을 초과하여 삽입할 수 없으므로 삽입 전에 큐가 가득차 있는지 검사해야 한다.

환형 큐에서 full 검사

환형 큐를 이용하면 rear 포인터가 상한에 도달하여 삽입이 중단되는 문제를 해결할 수는 있지만 큐의 용량을 초과하여 데이타 항목을 삽입할 수는 없다. 다음 그림에서처럼 front 포인터와 rear 포인터가 같은 곳을 가리키면 큐가 가득찬 것이다.

이렇게 되면 큐가 가득찬 경우와 큐가 비어 있는 경우 모두 front 와 rear 포인터가 같아지므로 두 가지 경우를 구별하는 방법이 필요하다.

환형 큐에서 데이타 항목 삭제

데이타 항목을 삭제하려면 front 포인터를 하나만큼 증가시키고, 그 위치에 있는 데이타 항목을 제거한다. 만약 front 포인터가 끝점을 가리키고 있으면 reset 시켜준다.

데이타 항목을 삭제하기 전에 큐에 남아 있는 데이타 항목이 있는지 검사해야 한다.

환형 큐에서 empty 검사

다음의 그림처럼 front 포인터와 rear 포인터가 같은 곳을 가리키면 큐가 비어있는 것이다.

이렇게 되면 큐가 가득찬 경우와 비어 있는 경우 모두 front 와 rear 포인터가 같아지므로 두 가지 경우를 구별하는 방법이 필요하다.

환형 큐에서 큐가 가득찬 경우와 큐가 비어있는 경우를 구별하는 방법

환형 큐에서 front 포인터와 rear 포인터가 같은 경우를 큐 full 과 큐 empty 조건으로 사용하면 두 가지 경우를 구별할 수 없다. 이것을 구별하기 위해 하나의 여유 공간을 두고 그 공간은 사용하지 못하도록 한다.


front pointer = rear pointer


front pointer = rear pointer+1