[자료구조] 연결 자료구조를 이용한 큐의 구현..

[자료구조] 연결 자료구조를 이용한 큐의 구현..
순차 자료구조를 이용하여 구현한 큐에는 몇 가지 단점이 있다. 사용 크기가 제

한되어 큐의 길이를 마음대로 사용할 수 없고, 원소가 없을 때에도 항상 그 크

기를 유지하고 있어야 하므로 메모리도 낭비 된다는 점이다. 이와 같은 문제를

극복하기 위해 연결 자료구조를 이용하여 크기 제한이 없는 연결 큐(Linked

Queue)를 구현해 보자.

연결 큐에서 원소는 데이터 필드와 링크 필드를 가진 노드로 구성하며, 첫 번째
노드를 가리키는 front 포인터와 마지막 노드를 가리키는 rear 포인터를 사용한

다. 연결 큐의 초기 상태(공백 큐)는 front와 rear를 NULL 포인터로 설정하여 표

현한다.

다음은 간단히 구현한 소스 이다.

#include <stdio.h>
#include <malloc.h>

typedef struct QNode{
 char data ;
 struct QNode *link ;
} QNode;

typedef struct {
 QNode *front, *rear ;
} LQueueType ;

LQueueType* createLinkedQueue()
{
 LQueueType *LQ ;
 LQ = (LQueueType*)malloc(sizeof(LQueueType)) ;
 LQ->front = NULL ;
 LQ->rear = NULL ;

 return LQ ;
}

bool isEmpty(LQueueType* LQ)
{
 if(LQ->front == NULL)
 {
  printf("\n Linked Queue is empty! \n") ;
  return true ;
 }else
  return false ;
}

void enQueue(LQueueType* LQ, char item )
{
 QNode* newNode = (QNode*)malloc(sizeof(QNode)) ;
 newNode->data = item ;
 newNode->link = NULL ;

 if(LQ->front == NULL)
 {
  LQ->front = newNode ;
  LQ->rear = newNode ;
 }else
 {
  LQ->rear->link = newNode ;
  LQ->rear = newNode ;

 }
}

char deQueue(LQueueType* LQ)
{
 QNode* old = LQ->front ;
 char item ;

 if(isEmpty(LQ)) return 0 ;
 else
 {
  item = old->data ;
  LQ->front = LQ->front->link ;

  if(LQ->front == NULL )
   LQ->rear = NULL ;

  free(old) ;

  return item ;
 }
}

void printfLQ(LQueueType* LQ)
{
 QNode* temp = LQ->front ;
 printf("\n Linked Queue : [") ;

 while(temp){
  printf("%3c", temp->data) ;
  temp = temp->link ;
 }
 printf("]") ;
}

void main()
{
 LQueueType* LQ1 = createLinkedQueue() ;
 
 enQueue(LQ1, 'a') ;
 printfLQ(LQ1) ;

 enQueue(LQ1, 'b') ;
 printfLQ(LQ1) ;

 deQueue(LQ1) ;
 printfLQ(LQ1) ;

 enQueue(LQ1, 'c') ;
 printfLQ(LQ1) ;

 deQueue(LQ1) ;
 printfLQ(LQ1) ;

 deQueue(LQ1) ;
 printfLQ(LQ1) ;
}

이전의 선형구조로 소스를 짯을 때랑 화면상으로는 큰차이는 없다..

하지만 선형구조가 크기의 한계가 있다면, 연결 구조는 크기의 구애 받지 않고,
계속 늘었다, 줄었다 할 수 있기 때문에, 훨씬 여러곳에서 활용할 수 있다.

[자료구조] 연결 자료구조를 이용한 큐의 구현..