큐 (Queue)

큐 (Queue)

스택의 경우 나중에 들어온 데이터가 먼저 나가는 구조인데 반해 큐(Queue)는 먼저 들어온 데이터가 먼저 나가는 구조입니다.

이러한 구조를 선입선출(FIFO : First-In First-Out)이라고 합니다.

큐의 예로는 매표소에서 표를 사기 위해 한줄로 늘어선 열을 들 수 있겠습니다.

큐의 연산은

enqueue : 큐의 뒤에 요소를 추가한다

dequeue : 큐의 앞에서 요소를 삭제한다

큐는 뒤(Rear)에 요소를 추가하고 앞(Front)에서 삭제합니다.

이러한 형태입니다.

데이터가 들어온 순서대로 앞에서 삭제되는 것을 확인하실 수 있습니다.

큐를 배열로 구현할 경우 rear와 front가 무한히 늘어나고, Dequeue 연산 이후 주기적으로 모든 요소들을 왼쪽으로 다시 이동시켜주어야하는 문제가 생기기 때문에 큐는 주로 링크드리스트로 구현합니다.

배열로 구현하게 될때에는 원형 큐의 형태로 배열의 끝에 도달하게 되면 0이 되도록 하는 형태로 구현을 하기도 합니다.

링크드리스트로 구현한 큐 코드

#include <stdio.h>

#include <malloc.h>

typedef int element;                // 요소의 타입

typedef struct QueueNode {     // 큐의 노드의 타입, 아이템과 링크

  element item;

  struct QueueNode *link;         // 양방향이 아닌 단방향 링크

} QueueNode;

typedef struct {                       // 큐의 Front, Rear 구현

  QueueNode *front, *rear;

} QueueType;

void error(char *message)

{

   fprintf(stderr, "%s\n", message);

   exit(1);

}

void init(QueueType *q)           // 큐 초기화, 처음엔 Front, Rear 둘다 0

{

   q->front = q->rear = 0;

}

void is_empty(QueueType *q)   // 공백상태 검출함수

{

   return (q->front==NULL);       // Front가 Null이면 공백

}

int is_full(QueueType *q)    // 포화상태 검출함수

{

   return 0;                        // 에러가 없는 한 포화상태는 아니기 때문에 0리턴

}

void enqueue(QueueType *q, element item)

{

   QueueNode *temp = (QueueNode *)malloc(sizeof(QueueNode));

   if(temp == NULL)

     error("메모리 할당 불가");

   else {

     temp->item = item;    // 데이터 저장

     temp->link = NULL;    // 링크 필드 NULL 설정

     if ( is_empty(q) ) {      // 큐가 공백이면

        q->front = temp;     // 큐에 Front와 Rear 둘다 temp (새로운 노드), 아무것도 없기 때문

        q->rear = temp;

     }

     else {                            // 공백이 아니면

        q->rear->link = temp;  // rear가 가리키고 있는 링크필드를 temp (새로운 노드)

        q->rear = temp;          // rear가 새로운 노드가 됨

     }

   }

}

element dequeue(QueueType *q)

{

   QueueNode *temp = front;      // front를 temp에 복사

   element item;

   if (is_empty(q) )                     // 공백상태

     error("큐가 비어있음");

   }

   else {

      item = temp->item;             // temp(현재데이터) 데이터를 꺼낸다 (Front 삭제)

      q->front = q->front->link;    // front는 다음 링크의 값을 가리키도록 한다.

      if( q->front == NULL)           // 공백 상태

         q->rear = NULL;

      free(temp);                         // 동적 메모리 해제

     return item;                          // 꺼낸 데이터 반환

  }

}

element peek(QueueType *q)

{

    if( is_empty(q) )

      error("큐가 비어있음");

   else {

      item = q->front->item;      // 데이터를 꺼낸다

      return item;                       // 데이터 리턴

   }

}

void main()

{

   QueueType q;

 

   init(&q);

   enqueue(&q, 1);

   enqueue(&q, 2);

   enqueue(&q, 3);

   printf("dequeue() = %d\n", dequeue(&q));

   printf("dequeue() = %d\n", dequeue(&q));

   printf("dequeue() = %d\n", dequeue(&q));

}