Data structure - queue(FIFO) in c language

Queue란?

Queue란 자료구조 중 하나로 처음 입력된 데이터가 처음 빠져나가는(First In First Out, FIFO) 형태의 자료구조입니다.

위와 같이 A블럭의 데이터가 처리된 후 B블럭의 데이터가 처리되어야 하는 시스템이라고 가정해봅시다. 두 블럭이 동일 자원을 사용하기때문에 A블럭은 B블럭의 데이터 처리가 완료될 때 까지 팬딩상태입니다.

이 때 queue형태의 버퍼가 있다면 A,B 블럭 모두 독립적으로 수행될 수 있습니다.

구조

queue는 data와 다음 queue(node)를 가지고 있습니다. 그리고 시작 위치의 queue(front)와 마지막 위치의 queue(rear)를 가르키는 포인터가 있습니다.

이 구조에서 데이터를 추가할 때(enqueue)는 큐의 메모리를 하나 생성한 후, 원래의 rear의 다음 포인터를 생성한 큐에 지정합니다. 그리고 rear를 새로 생성한 큐로 지정을 하게 되면 위의 그림처럼 데이터가 하나 연결됩니다.

 

데이터를 빼낼때(dequeue)는 우선 front의 queue메모리를 해제한 후 front를 다음 큐에 연결합니다. 그리고 가지고있던 data를 반환하면 됩니다.

샘플 소스 분석

위의 구조대로 소스가 짜여진 샘플 코드입니다.

git clone https://github.com/juwith/jsutils.git git checkout 6d1bffa03ceae289c2c67a38e1d60b229b2b7ef7 cd queue

기본 queue의 데이터형입니다.

typedef struct qData qData;

struct qData
{
 qData* next;
 void* item;
};

typedef struct Queue
{
 qData* front;
 qData* rear;
 int nItem;
 struct QueueFuncTable *functable;
} Queue;

struct QueueFuncTable
{
 void (*enqueue)(Queue* queue, void* item);
 void* (*dequeue)(Queue* queue);
 int (*get_itemNum)(Queue* queue);
 void (*flush)(Queue* queue);
 void (*destroy)(Queue* queue);
};

전체 핸들인 Queue는 front와 rear를 가지고있으며 qData(실제 queue)는 다음 queue를 가르키는 포인터와 item을 가지고있습니다.
※ Tip. item이 void*형인 이유는 어떤 구조체를 저장할지 모르기때문에 void*으로 받습니다. 마찬가지로 dequeue도 void*형으로 반환을 하기때문에 dequeue 이후 형변환이 필요합니다.

void _queue_enque(Queue* queue, void* item)
{
 qData* newQData = (qData*)malloc(sizeof(qData));
 if(queue->front == NULL)
 {
  queue->front = newQData;
  queue->rear = queue->front;
 }
 else
 {
  queue->rear->next = newQData;
  queue->rear = queue->rear->next;
 }
 newQData->next = NULL;
 newQData->item = item;
 queue->nItem++;
}

queue를 넣을 때에는 메모리를 할당한 후 front가 없으면 처음 생성한 큐이기 때문에 front와 rear가 같아집니다. 이후 enqueue부터는 rear에 데이터형이 하나씩 붙습니다.

void* _queue_deque(Queue* queue)
{
 if(queue->front == NULL)
  return NULL;

 void* item = queue->front->item;
 qData* qnext = queue->front->next;
 free(queue->front);
 queue->front = qnext;

 queue->nItem--;
 return item;
}

queue를 뺄때는 front를 free한 후 front를 다음 queue로 지정하며, 원래 front가 가지고있던 data를 반환합니다.

queue를 여러 쓰레드에서 운용할 경우에는 mutex로 race condition을 조절해야합니다. 내부 queue에 mutex가 없는 이유는 이 queue를 사용하는 유저는 싱글쓰레드인지 멀티쓰레드인지 모르기때문에 불필요한 부분을 제외했습니다.