[자료구조] ch 3. 큐

3.1 큐 ADT

 

3.1.1 큐의 개념

 

- 먼저 들어간 데이터가 먼저 나오는 (FIFO First In First Out , 선입선출) 자료구조

- 입력과 출력 창구가 따로 존재하고, 제일 먼저 들어간 데이터가 제일 먼저 나옴\

 

3.1.2 큐의 핵심 기능 : 삽입과 제거 연산 

 

- 전단(Front) : 큐의 가장 앞 요소 

- 후단(Rear) : 큐의 가장 마지막 요소 

- 삽입 연산 : 후단에 노드를 덧붙여서 새로운 후단을 만드는 연산 

- 제거 연산 : 전단의 노드를 없애서 전단 뒤에 있는 노드를 새로운 전단으로 만드는 연산 

 

 

3.2  순환큐 

 

순환 큐 (Circular Queue)

 

- 시작과 끝을 연결해서 효율적인 삽입/삭제 연산이 가능하도록 고안된 큐 

- 배열의 시작과 끝을 연결 

- 전단을 가리키는 변수를 도입해서 배열 내 요소를 옮기는 대신 전단의 위치만 변경

- 후단을 가리키는 변수를 도입해서 삽입이 일어날 때마다 후단의 위치를 변경 

- 후단을 가리키는 변수에는 '실제 후단의 위치 + 1'한 값을 담음 

 

 

3.2.1 공백 상태와 포화 상태 

 

- 큐가 포화 상태일 때뿐 아니라 공백 상태일 때도 전단과 후단이 만나기 때문에(같은 위치에 있기 때문에) 이 두 상태를 구분하는 방법을 찾아야 함 

- 이 문제를 해결하기 위해 큐 배열을 생성할 떄 실제 용량보다 1만큼 더 크게 만들어서 전단과 후단(실제 후단)사이를 비움 

 

- 큐가 공백 상태일 떄 전단과 후단이 같은 곳을 가리킴

- 큐가 포화 상태일 때 후단이 전단보다 1 작은 값을 가짐 

 

3.2.2 순환 큐의 기본 연산 

 

- 순환 큐는 배열 기반으로 구현되며 삽입과 삭제 연산이 이루어질 때 전단과 후단을 변경함으로써 큐가 공백 상태인지 포화 상태인지 확인 

 

1) 순환 큐 선언 

 

 - 순환 큐의 노드 구조체 

typedef int ElementType;

typedef struct tagNode
{
    ElementType Data;
}Node;

 

- 순환 큐를 나타내는 구조체 

typedef struct tagCircularQueue
{
    int Capacity; //용량
    int Front;  //전단의 위치 
    int Rear;   //후단의 위치 
    
    Node* Nodes; //순환 큐 요소 배열에 대한 포인터 
}CircularQueue;

 - Nodes 포인터가 가리키는 배열은 힙에 생성 

 - Nodes 포인터는 힙에 할당한 배열의 첫번째 요소를 가리킴 

 

 - Capacity는 순환 큐의 용량 즉, Nodes 배열의 크기를 나타내는데 실제로 Nodes를 메모리에 할당할 때는 'Capacity+1'만큼의 크기를 할당 

(노드 하나를 공백/포화 상태 구분용 더미 노드 (Dummy Node)로 사용하기 때문)

 

 - Front는 전단 위치를, Rear는 후단 위치를 가리킴. 이들이 갖는 값은 실제 메모리 주소가 아니라 배열 내의 인덱스 

 

2) 순환 큐 생성 / 소멸 연산 

 

순환 큐 생성 함수 CQ_CreateQueue

 

- 순환 큐 구조체를 힙에 생성 

- 순환 큐에 대한 포인터(의 포인터)인 Queue와 용량을 결정하는 Capacity를 매개변수로 받음 

- 순환 큐를 힙에 생성한 다음. ,배열을 'Node의 크기 * (Capacity+1)'의 크기를 힙에 할당 

 

void CQ_CreateQueue(CircularQueue** Queue, int Capacity)
{
    //큐를 힙에 생성 
    (*Queue) = ( CircularQueue*)malloc(sizeof(CircularQueue));
    
    //입력된 Capacity+1만큼의 노드를 힙에 생성 
    (*Queue)->Nodes = (Node*)malloc(sizeof(Node)*(Capacity+1));
    
    (*Queue)->Capacity = Capacity;
    (*Queue)->Front = 0;
    (*Queue)->Rear = 0;
}

 

순환 큐 소멸 함수 CQ_DestroyQueue

 

- 순환 큐를 메모리에서 제거 

- 배열을 먼저 힙에서 제거하고 순환 큐 구조체를 제거 

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

 

3) 노드 삽입 연산 

 

순환 큐 노드삽입 함수 CQ_Enqueue

 

- Rear의 값이 '*Queue->Capacity+1'과 같은 값이라면 후단이 배열 끝에 도달했다는 의미이므로 Rear와 Position을 0으로 지정 

- 그렇지 않은 경우 else 블록으로 넘어가서 현재 Rear의 위치를 Position에 저장하고 Rear의 값을 1 증가시킴

- if~else 블록을 거치고 나면 Nodes 배열에서 Position이 가리키는 곳에 데이터를 저장 

void CQ_Enqueue(CircularQueue* Queue, ElementType Data)
{
    int Position = 0;
    
    if(Queue->Rear == Queue->Capacity)
    {
    	Position = Queue->Rear;
        Queue->Rear = 0;
    }
    else
    	Postion = Queue->Rear++;
        
    Queue->Nodes[Position].Data = Data;
}

 

4) 노드 제거 연산 

 

순환 큐 노드 제거 함수 CQ_Dequeue

 

- 전단의 위치(Front)를 Position에 저장 

- Position은 CQ_Dequeue()함수가 큐의 전단에 저장되어 있던 데이터를 반환할 때 Nodes 배열의 인덱스로 사용되는 변수 

- 전단이 배열 끝에 도달한 경우 전단의 값은 순환 큐의 용량과 같으므로 Front를 0으로 초기화 하고, 그렇지 않은 경우 Front의 값을 1만큼 증가 

ElementType CQ_Dequeue(CircularQueue* Queue)
{
    int Position = Queue->Front;
    
    //전단이 배열 끝에 도달 
    if( Quque->Front == Queue->Capacity) 
    	Queue->Front = 0;
    else
    	Queue->Front++;
        
    return Queue->Nodes[Position].Data;
}

 

5) 공백 상태 확인 

 

순환 큐의 공백 상태를 확인하는 함수 CQ_IsEmpty

 

- 전단과 후단의 값이 같으면 공백 상태라는 의미이므로 Front와 Rear를 동등 연산자(==)로 비교한 결과를 반환 

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

 

6) 포화 상태 확인

 

순환 큐의 포화 상태를 확인하는 함수 CQ_IsFull

 

- 전단이 후단 앞에 있을 때 후단과 전단의 차(Rear-Front)가 큐의 용량(Capacity)과 동일하면 순환 큐는 포화상태 

- 전단이 후단과 같은 위치 또는 뒤에 있고 후단에 1을 더한 값(Rear+1)이 전단(Front)과 동일하면 순환 큐는 포화상태 

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

 

3.3 링크드 큐 

 

링크드 큐 (Linked Queue)

-링크드 큐의 각 노드는 이전 노드에 대한 포인터를 이용해 연결되므로 삽입 연산을 할 때는 삽입하려는 노드에 후단을 연결하고, 제거 연산을 할 때는 전단 바로 다음 노드에서 전단에 대한 포인터를 거두기만 하면 됨 

 

- 순환 큐와 달리 큐가 가득 찬 상태인지 확인할 필요 없음

 

3.3.1 링크드 큐의 기본 연산 

 

1) 링크드 큐와 노드 선언

 

링크드 큐 노드 구조체 

typedef struct tagNode
{
    char* Data; //데이터 필드 
    struct tagNode* NextNode; //다음 노드를 가리키는 포인터 
} Node;

 

링크드 큐 구조체 

typedef struct tagLinkedQueue
{
    Node* Front; //전단
    Node* Rear; //후단
    int Count; //노드 개수
}LinkedQueue;

 

2) 링크드 큐 생성/소멸 연산

 

링크드 큐 생성 함수 LQ_CreateQueue

 

- LinkedQueue 구조체를 힙에 생성하고 이 구조체의 각 필드를 초기화 

void LQ_CreateQueue(LinkedQueue** Queue)
{
    //큐를 힙에 생성
    (*Queue) = (LinkedQueue*)malloc(sizeof(LinkedQueue));
    (*Queue)->Front = NULL;
    (*Queue)->Rear = NULL;
    (*Queue)->Count = 0;
}

 

링크드 큐 소멸 함수 LQ_DestroyQueue

 

- 큐 내부에 있는 모든 노드를 힙에서 제거하고, 마지막에는 큐마저 힙에서 제거 

void LQ_DestroyQueue(LinkedQueue* Queue)
{
    while(!LQ_IsEmpty(Queue))
    {
    	Node* Popped = LQ_Dequeue(Queue);
        LQ_DestroyNode(Popped);
    }
    
    //큐를 힙에서 할당 해제
    free(Queue);
}

 

3) 노드 삽입  연산 

 

링크드 큐 노드 삽입 함수 LQ_Enqueue

 

-후단에 새로운 노드를 붙임

void LQ_Enqueue(LinkedQueue* Queue, Node* NewNode)
{
    if(Queue->Front == NULL)
    {
    	Queue->Front = NewNode;
        Queue->Rear = NewNode;
        Queue->Count++;
    }
    else
    {
    	//Rear의 다음 노드(Rear->NextNode)가 새로 들어온 노드가 됨
    	Queue->Rear->NewNode = NewNode;
        //Rear을 새로 들어온 노드를 가리키게 함 
        Queue->Rear = NewNode;
        Queue->Count++;
     }
}

 

4) 노드 제거 연산 

 

링크드 큐 노드 제거 함수 LQ_Dequeue

 

- 전단 뒤에 있는 노드를 새로운 전단으로 만들고 전단이었던 노드의  포인터를 호출자에게 반환 

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;
}