자구/큐(Queue) -수정중

큐 만들기도 역시 <열혈 자료구조>를 참조했다.




1. ADT

큐의 추상 자료형은 다음과 같다.

void QueueInit(Queue* pq);
-큐를 초기화

int QIsEmpty(Queue* pq);
-큐가 비었는지 검사

void Enqueue(Queue* pq, Data data);
-큐 첫 번째 위치에 데이터를 삽입

Data Dequeue(Queue* pq);
-큐의 첫 번째 데이터를 반환하면서 삭제

Data Qpeek(Queue* pq);
-큐의 첫 번째 데이터를 삭제하지 않고 반환

2. 메인함수

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

#include <stdio.h> #include <stdlib.h> #include "Queue.h" int main(void){     Queue q;     QueueInit(&q);          int i=0;     for(i=0; i<10; i++){         Enqueue(&q, i*i);     }     while(!QIsEmpty(&q))         printf("%d ", Dequeue(&q));          return 0; }

cs

3. 헤더파일

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

#ifndef __QUEUE_H__ #define __QUEUE_H__ #define TRUE 1 #define FALSE 0 typedef int Data; typedef struct _node{     Data data;     struct _node* next; } Node; typedef struct _queue{     Node* front;     Node* rear; } Queue; void QueueInit(Queue* pq); int QIsEmpty(Queue* pq); void Enqueue(Queue* pq, Data data); Data Dequeue(Queue* pq); Data Qpeek(Queue* pq); #endif

cs

4. Queue.c

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53

#include <stdio.h> #include <stdlib.h> #include "Queue.h" void QueueInit(Queue* pq){     pq->front = NULL;     pq->rear = NULL; } int QIsEmpty(Queue* pq){     if(pq->front == NULL)         return TRUE;     else         return FALSE; } void Enqueue(Queue* pq, Data data){     Node* newNode = (Node*)malloc(sizeof(Node));     newNode->next = NULL;     newNode->data = data;          if(QIsEmpty(pq)){         pq->front = newNode;         pq->rear = newNode;     }     else{         pq->rear->next = newNode;         pq->rear = newNode;     } } Data Dequeue(Queue* pq){     Node* delNode;     Data retData;          if(QIsEmpty(pq)){         printf("QUEUE MEMORY ERROR");         exit(-1);     }          delNode = pq->front;     retData = delNode->data;     pq->front = pq->front->next;          free(delNode);     return retData; } Data Qpeek(Queue* pq){     if(QIsEmpty(pq)){         printf("QUEUE MEMORY ERROR");         exit(-1);     }          return pq->front->data; } Colored by Color Scripter

cs

처음에 보고 큐를 왜 쓰나... 하는 생각이 들었는데, 여러 가지로 응용이 가능하다. 당장 책 조금 뒤에 나오는 기수 정렬(Radix Sort)에서도 큐가 사용된다.
큐의 응용 버전인 덱(Deque)도 있는데 그냥 양방향 큐라고 생각하면 될 듯하다.

참고

윤성우.(2012).열혈 자료구조.오렌지미디어