[C/C++][자료구조] 큐(Queue)에 대하여

[C/C++][자료구조] 큐(Queue)에 대하여

• 큐(Queue)는 스택(Stack)과 반대로 FIFO(First In First Out)의 원리대로 동작하는 자료 구조이다.
• 동일한 자료의 집합을 다룬다는 면에 있어서는 스택과 비슷하지만 가장 먼저 들어간 자료가 가장 늦게 나온다는 점이 다르다.
• 넣은 순서대로 자료를 꺼내가므로 순서대로 처리해야 하는 자료를 임시적으로 저장하는 용도로 흔히 사용한다.
• 저장되는 자료의 타입이 동일하므로 배열 또는 연결리스트로 큐를 구현할 수 있다. 이번 포스팅에서는 상대적으로 간단한 배열로 큐를 먼저 구현해 보도록 하겠다.

큐를 구현하는 과정을 간단히 설명하고 실제 코드를 보면서 부가설명을 하도록 하겠다.

큐를 구현하기 위해서는 먼저, 일정한 크기를 가지는 배열을 만들고 여기에 자료를 저장한다.

큐는 자료가 삽입되는 곳과 삭제되는 곳의 위치가 다르기 때문에 다음과 같은 두 개의 포인터를 관리해야 한다(여기서 포인터라고 함은 위치를 가리키는 값이라는 뜻이지 C의 포인터 타입과는 다른 뜻이다).

• head : 다음 삭제될 위치를 가리킨다.

• tail : 다음 삽입될 위치를 가리킨다.

tail 쪽에서는 새로 도착하는 자료가 끊임없이 쌓이기만 하고 head에서는 처리할 자료를 빼내 가기만 한다.

* 두 포인터의 의미를 잘 정해야 하는데 데이터를 넣을 때 삽입을 먼저 하고 포인터를 증가할 것인지 아니면 포인터를 증가한 후 삽입할 것인지에 대해 선택하여 한 번 정한 의미를 헷갈려서는 안된다.

큐를 초기화할 때 최초 head, tail은 모두 배열 선두인 0을 가리키는데 두 포인터가 같은 위치를 가리키면 대기중인 데이터가 없고 큐가 비어 있다는 뜻이다.

자료가 추가되면 tail 위치에 삽입되고 tail은 다음 칸으로 이동한다. 자료를 읽어서 삭제하면 head가 다음 칸으로 이동할 것이다. 이런 식으로 head와 tail은 자료가 삽입, 삭제될 때 배열의 뒤쪽으로 점점 이동하게 된다. 하지만 이런 식으로 자료를 계속 삽입, 삭제를 하게 되면 금방 배열의 뒤쪽 공간으로 이동되어 더 이상 삽입할 공간이 부족해지게 된다. 이런 경우의 문제를 해결하기 위해 사용되는 방법은 포인터가 배열의 끝에 닿았을 때 앞쪽으로 보내어 배열을 원형(Circular)으로 연결하는 방법을 많이 사용한다. 이는 % 연산자로 간단하게 구현할 수 있으며 관련 코드는 아래에서 소개하도록 하겠다. 이렇게 되면 head와 tail은 원형의 큐를 빙글빙글 돌아가면서 자료를 삽입하고 삭제한다.

* 만약 삽입하는 속도가 삭제하는 속도보다 빨라 tail이 head를 따라 잡으면 큐가 가득찬 상태이다. head가 tail과 같은 상태는 큐가 빈 상태와 같으므로 두 포인터의 값만 비교해서는 큐의 정확한 상태를 알 수 없다. 그래서 head 바로 앞의 한 칸은 미사용으로 남겨 두어 tail이 head의 바로 앞쪽에 있을 때, 즉 tail이 head-1일 때를 큐가 가득찬 것으로 정의한다. 이렇게 하면 기억 장소 하나를 쓰지 못하는 약간의 낭비가 발생하기는 하지만 상태를 정확하게 판별할 수 있다.

본격적으로, 배열을 이용하여 정수형 자료를 저장하는 큐(Queue)를 구현한 소스코드를 살펴보도록 하겠다.

#include ...

int *Queue;
int QSize;
int head,tail;
 
void InitQueue(int size)
{
     QSize=size;
     Queue=(int *)malloc(QSize*sizeof(int));
     head=tail=0;
}
 
void FreeQueue()
{
     free(Queue);
}
 
BOOL Insert(int data)
{
     if ((tail+1) % QSize == head) {
          return FALSE;
     }
     Queue[tail]=data;
     tail=(tail+1) % QSize;
     return TRUE;
}
 
int Delete()
{
     int data;
 
     if (head==tail) {
          return -1;
     }
     data=Queue[head];
     head=(head+1) % QSize;
     return data;
}
 
void main()
{
     int i;
 
     InitQueue(10);
     printf("빈 상태에서 삭제할 때 = %d\n",Delete());
     for (i=0;i<9;i++) {
          Insert(i);
     }
 
     printf("가득찬 상태에서 삽입 %s\n",Insert(100) ? "성공":"실패");
    
     for (i=0;i<9;i++) {
          printf("%d  ",Delete());
     }
 
     FreeQueue();
}

• 스택(Stack)과 마찬가지로 Queue 포인터가 곧 큐가 된다. QSize는 큐의 크기, head, tail은 큐의 양끝 포인터이다.

• InitQueue 함수는 큐를 초기화하는데 인수로 전달 받은 size 크기만큼 Queue 배열을 할당하고 head와 tail은 모두 0으로 초기화하여 빈 상태로 만든다. 이후 자료가 삽입, 삭제되면 head와 tail이 이동하면서 큐를 회전할 것이다.

• FreeQueue 함수는 동적으로 할당된 Queue 배열을 해제하여 큐를 파괴한다.

• Insert 함수는 큐에 데이터를 삽입하는 동작을 하며 이는 Queue[tail++]=data; 로 간단하게 설명할 수 있다. tail이 가리키는 위치에 인수로 전달된 data를 저장하고 tail은 다음 칸으로 이동하는 것이다. 간단한 코드이지만 여기에는 두 가지 예외 처리가 추가되어야 한다. 먼저, tail이 배열의 끝일 때 선두로 보내기 위해 QSize와 나머지 연산을 취한다. tail의 다음 위치는 통상 tail+1이지만 배열 끝인 QSize에 이르렀을 때는 배열 선두인 0으로 다시 돌아가야 한다. 또한, 큐가 가득 차서 더 이상 삽입할 수 없는 Overflow도 처리해야 한다. tail의 다음 위치가 head와 같으면 이때는 에러 처리하고 리턴을 한다. tail과 head 사이에 사용하지 않는 빈칸을 하나 둠으로써 가득 찼을 때와 비어 있을 때를 구분할 수 있다.

• * Insert 함수의 동작을 간단하게 정리하면 큐에 여유가 있을 때 tail 위치에 데이터를 삽입하고 tail을 다음 삽입할 위치로 보낸다고 할 수 있다.

• Delete 함수는 큐에 데이터를 제거하는 동작을 하며 이는 return Queue[head++]; 로 간단하게 설명할 수 있다. Insert와 마찬가지로 두 가지 예외를 처리해야 한다.

• 마지막으로 큐가 잘 동작하는지 테스트하기 위한 main 함수는 크기 10의 큐를 생성하고 9개의 자료를 삽입했다가 다시 빼 보는 작업을 수행한다. 에러를 잘 처리하는지 테스트하기 위해 빈 상태에서 괜히 삭제도 해 보고 가득찬 상태에서 더 삽입해 보기도 한다. 실제 코드를 돌려보면 삽입된 자료가 순서대로 출력되며 에러 처리도 제대로 되는 것을 확인할 수 있다.

* 참고 - 소프트웨어 공학연구소 C/C++ 강좌 (http://soen.kr/)