개요

큐(Queue)란, 먼저 들어가고 먼저 나오는(FIFO) 자료구조를 일컫는다. 큐는 작업을 처리하는 요소에 부하를 주지 않으면서도 처리하는 능력을 넘어서는 작업들도 놓치지 않고 수용할 수 있기 때문에 완중장치로서 사용된다.

큐의 주요기능 : 삽입과 제거

큐는 삽입은 후단, 제거는 전단에서 수행된다.

순환 큐

개요

전단인 1을 제거하면 배열 내에 첫 번째 인덱스의 요소는 비게되고, 빈 자리를 채우기 위해 뒤에 있던 2,3,4 요소가 앞으로 한 칸씩 옮겨온다.

여기에서 생기는 문제점은 전단을 제거한 후, 나머지 요소들을 한 칸씩 앞으로 옮기는데 비용이 발생하기 때문인데, 이러한 문제를 해결하기 위해서 전단을 가리키는 변수를 도입하여 배열 내의 요소를 옮기는 대신 변경된 전단의 위치만 관리하면 된다.
이와 함께, 후단을 가리키는 변수도 도입해서 삽입이 일어날 때마다 변경되는 후단의 위치를 관리한다.

하지만 제거 연산을 수행할 수록 큐의 가용 용량도 줄어들기 때문에 큐의 수명도 되어가는데, 이때 배열의 끝과 시작을 연결하면 다음과 같다.

삽입이 이루어질 때마다 후단이 뒤로 후퇴하다가 전단을 만나게 되면 비로소 그 큐는 '가득 찬 상태'가 된다.

<가득 찼을때 사진추가>

특징

큐는 비어 있는 상태와 가득 차 있는 상태를 구분할 수 없다. 그래서 이를 해결하기 위해 실제의 용량보다 1만큼 더 크게 만들어서 전단과 후단 사이를 비우는 것이다.

이렇게 하면 큐가 비어 있을 때 전단과 후단이 같은 곳을 가리키게 되고, 큐가 차 있을 때는 후단이 전단보다 1 작은 값을 갖게 된다.

순환 큐 구현

순환 큐의 선언

순환 큐를 나타내는 CircularQueue 구조체는 Queue의 용량(Capacity), 전단의 위치(Rear), 그리고 순환 큐 요소의 배열에 대한 포인터를 갖고 있다.

typedef struct tagCircularQueue
{
	int   Capacity;  /*용량*/
   	int	  Front;	 /*전단의 인덱스*/
    int	  Rear;		 /*후단의 인덱스*/
    Node* Nodes; 	 /*노드 배열 */
} CircularQueue;

CircularQueue 구조체의 Nodes 포인터가 가리키는 배열은 그림처럼 자유저장소에 생성된다.
Capacity에는 배열의 크기, 즉 큐의 용량이 저장되는데 Capacity가 갖는 값은 실제의 용량보다 하나 작다. 그 이유는 앞에서 언급했듯이 공백과 포화상태를 구분하기 위해 더미 노드를 한 개 더 갖고 있기 때문이다. 또한 Rear는 실제의 후단보다 1 더 큰 값을 갖는다.

Front는 전단의 위치를, Rear는 후단의 위치를 가리킨다. 이 값들이 갖는 값은 배열 내의 인덱스이다.

순환 큐의 생성과 소멸

[생성]

void CQ_CreateQueue (CircularQueue** Queue, int Capacity)
{
	/* 큐를 자유 저장소에 생성 */
    (*Queue)			= (CircularQueue*)malloc(sizeof(CircularQueue)); 
    /* 입력된 Capacity+1 만큼의 노드를 자유 저장소에 생성 */
    (*Queue)->Nodes		= (Nodes*)malloc(sizeOf (Node) * (Capacity+1) ); 
    
    (*Queue)->Capacity = Capacity; /* 큐가 수용할 실제 용량을 저장*/
    (*Queue)->Front = 0;
    (*QUeue)->Rear = 0;
}

CQ_CreateQueue는 순환 큐에 대한 포인터인 Queue와 용량을 결정하는 Capacity를 매개 변수로 받는다.

매개변수를 받아들인 CQ_CreateQueue()는 제일 먼저 순환 큐를 자유 저장소에 생성한 다음 "Node의 크기 x (Capacity +1)"의 크기로 배열을 자유 저장소에 할당한다.

[소멸]

void CQ_DestroyQueue(CircularQueue* Queue) 
{
	free(Queue->Nodes);
    free(Queue);
}

삽입 연산

+<코드까지 옆에 나란히 첨부하여 어떻게 1씩 추가되는지 확인하기>

CQ_Enqueu() 함수에 if ~ else의 if 블록에서 Rear의 값이 "*Queue -> Capacity +1" 과 같은 값을 갖고 있다면 후단이 배열의 끝에 도달했다는 것을 뜻하므로, Rear와 Position을 ()로 지정한다. 그렇지 않은 경우에는 else 블록으로 넘어가서 현재 Rear의 위치를 Position에 저장하고 Rear를 1 증가시킨다.

그리고 if ~ else 블록이 끝난 후에 Nodes 배열에서 Position이 가리키는 곳에 데이터를 저장한다.

제거 연산

ElementType CQ_Dequeue (CircularQueue* Queue)
{
	int Position = Queue->Front;
    
    if ( Queue-> Front == Queue-> Capacity )
    	Queue->Front = 0;
    else 
    	Queue->Front++;
        
    return Queue->Nodes[Position].Data;
}

순환 큐의 제거 연산에서는 전단을 잘 관리해 주는 것이 중요하다. 가장 먼저 전단의 위치(Front)를 Position에 저장하고, 이 값은 건드리지 않은채 마지막에 함수를 종료하면서 전단의 데이터를 반환할 때 배열의 인덱스로 사용된다.

그리고 가운데에 있는 if ~ else 블록에서는 Front 값이 Capacity와 같을 때 Front를 0으로 초기화하고, 그렇지 않은 경우에는 Front의 값을 1만큼 증가시킨다.
Front의 값이 Capacity와 같다는 것은 전단이 곧 배열의 끝에 도달해 있다는 사실을 나타낸다.

<사진첨부>

공백 상태 확인

int CQ_IsEmpty(CircularQueue* Queue) 
{
	return (Queue -> Front == Queue-> Rear);
}

포화 상태 확인

int CQ_IsFUll (CircularQueue* Queue) 
{
	if (Queue -> Front < Queue -> Rear) 
    	return ( Queue-> Rear - Queue -> Front) == Queue->Capacity; 
        else 
        	return ( Queue->Rear + 1 ) == Queue -> Front; 
}

링크드 큐

<사진첨부>

링크드 큐의 각 노드는 앞 노드에 대한 포인터를 이용해 구성되어 있기 때문에, 삽입은 새 노드의 포인터에 후단을 연결하고 제거는 전단 바로 이후의 노드에서 전단에 대한 포인터를 거두어 들이는 것으로 구현이 된다.

링크드 큐의 장점은 한계 용량의 제한이 없기 때문에 큐가 가득 차 있는 상태인지 확인할 필요가 없다는 것이다.

링크드 큐 구현하기

링크드 큐와 노드의 선언

typedef struct tagNode
{
	char* Data;
    struct tagNode* NextNode;
}	Node;

링크드 큐의 노드는 링크드 리스트의 노드처럼 데이터 필드와 다음 노드를 카리키는 포인터로 구성된다. (위의 코드에서는 char* 자료형으로 왔지만, 다른 자료형이 올 수도 있다)

typedef struct tagLinkedQueue
{
	Node* Front;
    Node* Rear;
    int	  count;
}	LinkedQueue;

링크드 큐의 구조체의 필드는 모두 세 개이다. 첫 번째는 큐의 시작을 가리키는 Front, 두 번째는 큐의 끝을 가리키는 Rear, 마지막 필드는 노드의 수를 나타내는 Count이다.

링크드 큐의 생성과 소멸

void LQ_CreateQueue (LinkedQueue** Queue)
{
	(*Queue)	= (LinkedQueue*)malloc(sizeof(LinkedQueue));
	(*Queue)->Front = NULL;
    (*Queue)->Rear	= NULL;
    (*Queue)->COUNT = 0;
    
}

LQ_CreateQueue()는 LinkedQueue 구조체를 자유 저장소에 생성하고, 이 구조체의 각 필드를 초기화하는 일을 수행한다.

void LQ_DestroyQueue (LinkedQueue* Queue)
{
	while ( !LQ_IsEmpty(Queue)	)
    {
    	Node* Popped = LQ_Dequeue (&Queue);
        LQ_DestroyNode (Popped);
	}
    
    /* 큐를 자유 저장소에서 해제*/
    free(Queue);
}

삽입

void LQ_Enqueue ( LinkedQueue* Queue, Node* NewNode	)
{
	if ( Queue-> Front == NULL )
    {
    	Queue->Front = NewNode;
        Queue->Rear	 = NewNode;
        Queue->Count++;
    }
    else
    {
    	Queue->Rear->NextNode = NewNode;
        Queue->Rear = NewNode;
        Queue->Count++;
    }
}

제거

Node* LQ_Dequeue ( LinkedQueue* Queue)
{
	/* LQ_Dequeue() 함수가 반환할 최상위 노드 */
    Node* Front = Queue->Front;
    
    if ( Queue->Front->NextNode == NULL)
    {
    	Queue->Front = NULL;
        Queue->Rear	 = NULL;
    }
else
	{
      Queue->Front = Queue->Front->NextNode;
    }
    
    Queue->Count--;
    
    return Front;
}