자료구조 - 링크드 큐(Liked Queue)

용량(Capacity)가 이미 정해진 순환 큐(Circular Queue)와 달리

링크드 큐(Linked Queue)는 우리가 생각하는 큐의 개념대로 쉽게 짤 수 있다.

링크드 큐(Linked Queue)는 용량에 구애받지 않고, 포인터로 연결하기 때문에

큐가 가득 차 있는지(포화상태), 큐가 비어있는지(공백상태)때문에 신경을 쓸 필요가 없다.

대신 링크드 큐(Linked Queue)는 노드와 생성, 그리고 삭제할 때 malloc(),free()함수 호출을 반복하므로

큐의 크기가 예측가능하다면 순환 큐(Circular Queue)가 더 성능이 좋다. 

 

typedef struct tagNode{ char* Data; //데이터 struct tagNode* NextNode; //포인터 }Node;

 

typedef struct tagLinkedQueue{ Node* Front; Node* Rear; int Count; //노드의 갯수 }LinkedQueue;

 

void LQ_CreateQueue(LinkedQueue** Queue){ (*Queue) = (LinkedQueue*)malloc(sizeof(LinkedQueue)); //초기화 (*Queue)->Front = NULL; (*Queue)->Rear = NULL; (*Queue)->Count = 0 }

 

void LQ_DestoryQueue(LinkedQueue* Queue){ while( !LQ_IsEmpty(Queue) ){ //큐안에 노드가 다 비어질 때 까지 Node* Popped = LQ_Dequeue(Queue); LQ_Destory Node(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++; } }

 

void LQ_Dequeue(LinkedQueue* Queue){ Node* TempFront = Queue->Front; if(Queue->Front->NextNode == NULL){ //큐에 노드가 하나 밖에 없을 때 Queue->Front = NULL; Queue->Rear = NULL; } else{ Queue->Front = Queue->Front->NextNode; } Queue->Count--; return TempFront; }