5.3.1 큐 설계

여기에서는 연결리스트를 큐로 감싸(Wrapping)하여 선입선출(FIFO, First In First Out)방식으로 자료를 보관 및 꺼내기 동작을 제공하도록 설계할게요.

#include "LinkedList.h"
typedef LinkedList EHQueue;

큐를 설계할 때 내부에 자료를 보관하는 저장소를 배열로 만드는 방법도 있는데 이미 만들어진 연결리스트를 이용하여 자료를 보관하게 정의하면 저장소의 한계가 없는 큐를 만들 수 있습니다. 물론 메모리의 한계까지 없는 것은 아닙니다. 일반적으로 대학에서 배우는 큐는 자료를 보관하는 저장소를 정적 크기의 배열로 정의하는 큐를 배우고 꽉 찼을 때의 처리에 관한 고민을 합니다. 특히 이 문제를 원형 큐 형태로 만들어 문제를 해결하는데 자료를 저장하는 저장소를 이미 만들어진 연결리스트를 이용하면 구현을 단순화할 수 있습니다.

특히 대학교에서 다루는 큐는 저장소를 정적 배열로 정의하기 때문에 자료를 보관할 인덱스 rear와 자료를 꺼낼 인덱스 front를 기억하고 있어야 합니다. 하지만 여기에서 만드는 큐는 저장소를 이미 작성한 연결리스트를 이용하기 때문에 이와 같은 멤버를 별도로 기억할 필요가 없습니다. 연결리스트에는 head와 tail이 있어서 tail 앞에 자료를 보관하고 head 뒤에서 꺼내면 자연스럽게 선입선출(FIFO) 방식으로 자료를 보관 및 꺼낼 수 있습니다.

동적으로 큐를 생성하는 함수와 동적으로 생성한 큐를 제거하는 함수를 제공합시다.

EHQueue *New_EHQueue();
void Delete_EHQueue(EHQueue *ehq);

큐에 자료를 보관하는 함수와 큐에 보관한 자료를 꺼내는 함수를 제공합시다.

void EHQueue_Put(EHQueue *ehq, Element data);
Element EHQueue_Get(EHQueue *ehq);

마지막으로 큐가 빈 상태인지 확인하는 함수를 제공합시다.

int EHQueue_IsEmpty(EHQueue *ehq);

다음은 EHQueue.h 파일의 내용입니다.

//EHQueue.h
#pragma once
#include "LinkedList.h"

typedef LinkedList EHQueue;

EHQueue *New_EHQueue();
void Delete_EHQueue(EHQueue *ehq);
void EHQueue_Put(EHQueue *ehq, Element data);
Element EHQueue_Get(EHQueue *ehq);
int EHQueue_IsEmpty(EHQueue *ehq);