[C] 자료구조 큐(queue)

자료구조 중 하나인 큐(queue), 덱(Deque)에 대한 설명 + c로 구현한 큐 코드에 대한 정리

 

■ 큐(queue)

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

객체 : n개의 요소들의 순서 있는 모임

연산 :

Create    ::= 큐 생성

Empty(q)    ::= 비어 있는지 검사

Full(q)    ::= 가득 차 있는지 검사

Enqueue(q, e)   ::= 큐의 뒤에 요소 e 추가

Dequeue(q)   ::= 큐의 앞에 있는 요소 반환 후 삭제

Peek(q)  ::= 큐에서 삭제하지 않고 앞에 있는 요소 반환

 

■ 삽입, 삭제 연산

 

■ 배열로 구현한 큐

• 선형 큐

위와 같이 선형 큐로 구현할 경우, 삽입을 하기 위해서 요소들을 계속 이동시켜야 하는 문제 발생

데이터를 옮기는데에만 많은 연산을 수행하게 됨

따라서 아래와 같은 순환형식의 원형 큐를 이용하여 구현해야 함

 

• 원형 큐

• 구조체 선언

#include <stdio.h>

#define MAX_QUEUE_SIZE 10

typedef int Element;
typedef struct {
   Element EQueue[MAX_QUEUE_SIZE];
   int nFront;	//전단
   int nRear;	// 후단
} QueueType;

• Error, Init

int Error(char *message)
{
   fprintf(stderr, "%s\n", message);
   return -1;
}
int Init(QueueType *pQue)
{
   pQue->nFront = pQue->nRear = 0;
   return 0;
}

• Empty, Full

int Empty(QueueType *pQue)
{
   if (pQue->nFront == pQue->nRear) return 1;
   else return 0;
}

int Full(QueueType *pQue)
{
   if ((pQue->nRear + 1) % MAX_QUEUE_SIZE == pQue->nFront return 1;
   else return 0;
}

• Enqueue

int Enqueue(QueueType *pQue, Element EData)
{
   if (Full(pQue) == 1) {
      Error("큐 포화");
   }
else {
   pQue->nRear = (pQue->nRear + 1) % MAX_QUEUE_SIZE;
   pQue->EQueue[pQue->nRear] = EData;
}
   return 0;
}

• Dequeue

Element Dequeue(QueueType *pQue)
{
   if (Empty(pQue) == 1) {
   Error("큐 공백");
}
else {
   pQue->nFront = (pQue->nFront + 1) % MAX_QUEUE_SIZE;
}

   return pQue->EQueue[pQue->nFront];
}

 

■ 연결리스트로 구현한 큐

• 노드 정의

typedef int Element;
typedef struct _queuenode {
   Element EData;
   struct _queuenode *link;
} QueueNode;

typedef struct {
   QueueNode *front;
   QueueNode *rear;
} QueueType;

 

• Init, Empty

int Init(QueueType *pQue)
{
   pQue->front = pQue->rear = NULL;

   return 0;
}
int Empty(QueueType *pQue)
{
   if (pQue->front == NULL) return 1;
   else return 0;
}

 

• Enqueue

int Enqueue(QueueType *pQue, Element EData)
{
   QueueNode *pNew = (QueueNode *)malloc(sizeof(QueueNode));

   if (pNew == NULL) Error("메모리 할당 불가");
   else {
      pNew->EData = EData;	// 데이터 저장
      pNew->link = NULL;	// 마지막에 삽입
         if (Empty(pQue) == 1) {
            pQue->front = pNew;
            pQue->rear = pNew;
         }
         else {
            pQue->rear->link = pNew;
            pQue->rear = pNew;
          }
   }
   return 0;
}

 

• Dequeue

Element Dequeue(QueueType *pQue)
{
   QueueNode *pRemove = NULL; 
   Element EData = 0;

   pRemove = pQue->front;

   if ( Empty(pQue) == 1) {
      Error("큐 공백");
   }
   else {
      EData = pRemove->EData;
      pQue->front = pQue->front->link;
      if (pQue->front == NULL) {
         pQue->rear = NULL;
      }
      free(pRemove); pRemove = NULL;
      return EData;
   }
}

 

■ 덱(Deque)

Double-ended-queue
전단과 후단에서 모두 삽입 & 삭제

add_rear(dq, e) =  Enqueue(dq, e)   ::= 덱의 뒤에 요소 e 추가

delete_front(dq, e) = Dequeue()   ::= 덱의 앞에 있는 요소 반환 후 삭제

delete_rear(dq, e) = Pop()  ::= 덱의 마지막 요소 반환 후 삭제

add_front(dq, e)   ::= 덱의 앞에 요소 e 추가

 

■ 덱(Deque)의 연산

• 노드 정의

typedef int Element;

typedef struct _listnode {
   Element EData;
   struct _listnode *Llink;
   struct _listnode *Rlink;
} ListNode;

typedef struct _dequetype {
   ListNode *pHead;
   ListNode *pTail;
} DequeType;

 

• Init, Empty

int Init(DequeType *pDeque)
{
   pDeque->pHead = pDeque->pTail = NULL;
}
int Empty(DequeType *pDeque)
{
   if (pDeque->pHead == NULL) return 1;
   else return 0;
}

 

• 노드 생성

ListNode *CreateNode(ListNode *Llink, Element EData, ListNode *Rlink)
{
   ListNode *pNode = (ListNode *)malloc(sizeof(ListNode));
   if (pNode == NULL) {
      Error("메모리 할당 오류");
   }
   pNode->Llink = Llink;
   pNode->EData = EData;
   pNode->Rlink = Rlink;
   return pNode;
}

 

• Add rear

int Add_Rear(DequeType *pDeque, Element EData)// 마지막에 추가
{
   ListNode *pNew = NULL;
   pNew = CreateNode(pDeque->pTail, EData, NULL);
   if (Empty(pDeque) == 1) {
      pDeque->pHead = pNew;
   }
   else {
      pDeque->pTail->Rlink = pNew;
   }
   pDeque->pTail = pNew;
   return 0;
}

 

• Add front

int Add_Front(DequeType *pDeque, Element EData)// 처음에 추가
{
   ListNode *pNew = NULL;
   pNew = CreateNode(NULL, EData, pDeque->pHead);
   if (Empty(pDeque) == 1) {
      pDeque->pTail = pNew;
   }
   else {
      pDeque->pHead->Llink = pNew;
   }
   pDeque->pHead = pNew;
   return 0;
}

 

• Delete front

Element Delete_Front(DequeType *pDeque)
{
   Element EData = 0;
   ListNode *pRemove = NULL;

   if (Empty(pDeque) == 1) {
      Error("덱 공백");
   }
   else {
      pRemove = pDeque->pHead;		// 제거할 노드
      EData = pRemove->EData;			// 제거 데이터 저장
      pDeque->pHead = pRemove->Rlink;		// 제거 노드의 R링크가 덱의 헤드가 됨
      //pDeque->pHead = pDeque->pHead->Rlink;	
      free(pRemove); pRemove = NULL;		// 반환
      if (pDeque->pHead == NULL) {		// 공백 상태
         pDeque->pTail = NULL;			// tail도 공백
      }
      else {
         pDeque->pHead->Llink = NULL;		 // 공백이 아니면- head Llink = NULL
      }
    }
   return EData;
}

 

• Delete rear

Element Delete_Rear(DequeType *pDeque)
{
   Element EData = 0;
   ListNode *pRemove = NULL;

   if (Empty(pDeque) == 1) {
      Error("덱 공백");
   }
   else {
      pRemove = pDeque->pTail;			// 제거할 노드
      EData = pRemove->EData;			// 제거 데이터 저장
      pDeque->pTail = pRemove->Llink;		// 제거 노드의 L링크가 덱의 tail이 됨
      //pDeque->pTail = pDeque->pHead->Llink;	
      free(pRemove); pRemove = NULL;		// 반환
      if (pDeque->pTail == NULL) {		// 공백 상태
         pDeque->pHead = NULL;			// head도 공백
      }
      else {
         pDeque->pTail->Rlink = NULL;		// 공백이 아니면 – tail Rlink = NULL;
      }
   }
   return EData;
}