큐

앞서 설명한 스택과 함께 언급되는 자료구조입니다. 스택은 먼저 들어간 데이터가 나중에 나오는 구조인 반면, 큐는 먼저 들어간 데이터가 먼저 나오는 구조입니다. 

큐의 이해

FIFO(First in, First out) 구조의 자료구조라 불립니다. 

큐의 ADT 정의

enqueue 큐에 데이터를 넣는 연산, dequeue 큐에 데이터를 꺼내는 연산. 스택에서 데이터를 넣고 뺴는 연산을 가리켜 각각 push, pop 이라 하는 것처럼, 큐에서 데이터를 넣고 뺴는 연산에 대해서도 각각 enqueue, dequeue 라는 별도의 이름을 붙여주고 있습니다. 

큐의 초기화를 진행합니다. 큐 생성 후 제일 먼저 호출되어야 하는 함수입니다. 큐가 빈 경우 참을 그렇지 않은 경우 거짓을 반환합니다. 큐에 데이터를 저장합니다. 매개변수 data로 전달된 값을 저장합니다. 저장 순서가 가장 앞선 데이터를 삭제합니다. 삭제된 데이터는 반환됩니다. 본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 합니다. 저장 순서가 가장 앞선 데이터를 반환하되 삭제하지 않습니다. 본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 합니다. 배열 기반의 큐와 연결 리스트 기반의 큐를 각각 구현해 보겠습니다. 

큐의 배열 기반 구현

스택과 큐의 차이점이 앞에서 꺼내느냐 뒤에서 꺼내느냐에 있으니, 이전에 구현해 놓은 스택을 대상으로 꺼내는 방법만 조금 변경하면 큐가 될 것 같습니다. 

원형 큐의 소개

R과 F를 회전시켜서, 큐를 구성하는 배열을 효율적으로 사용하자는 결론에 도달했습니다. F와 R의 위치만 가지고는 꽉 찬 경우와 텅 빈 경우를 구분할 수가 없습니다. 배열을 꽉 채우지 않는다. 꽉 차면 구분이 안되는 꽉 채우지 않는 방법이 있습니다. 배열의 길이가 N 이라면 데이터가 N-1 개 채워졌을 때, 이를 꽉 찬 것으로 간주합니다. enqueue 연산 시, R이 가리키는 위치를 한 칸 이동시킨 다음에, R이 가리키는 위치에 데이터를 저장합니다. dequeue 연산 시, F가 가리키는 위치를 한 칸 이동시킨 다음에, F가 가리키는 위치에 저장된 데이터를 반환 및 소멸합니다. 구현할 큐의 특성 두 가지를 다음과 같이 추가로 정리할 수 있습니다. 원형 큐가 텅 빈 상태 F와 R이 동일한 위치를 가리킵니다. 원형 큐가 꽉 찬 상태는 R이 가리키는 위치의 앞을 F가 가리킵니다. 

원형 큐의 구현

원형 큐의 논리를 완전히 이해하였습니다. 때문에 원형 큐의 구현은 부담스럽지 않습니다. 

#ifndef __C_QUEUE_H__ #define __C_QUEUE_H__ #define TRUE 1 #define FALSE 0 #define QUE_LEN 100 typedef int Data; typedef struct _cQueue { int front; int rear; Data queArr[QUE_LEN]; }CQueue; typedef CQueue Queue; void QueueInit(Queue * pq); int QIsEmpty(Queue * pq); void Enqueue(Queue * pq, Data data); Data Dequeue(Queue * pq); Data QPeek(Queue * pq); #endif

#include <stdio.h> #include <stdlib.h> #include "CircularQueue.h" void QueueInit(Queue * pq) { pq->front = 0; pq->rear = 0; } int QIsEmpty(Queue * pq) { if (pq->front == pq->rear) return TRUE; else return FALSE; } int NextPosIdx(int pos) { if (pos == QUE_LEN - 1) return 0; else return pos + 1; } void Enqueue(Queue * pq, Data data) { if (NextPosIdx(pq->rear) == pq->front) { printf("Queue Memory Error"); exit(-1); } pq->rear = NextPosIdx(pq->rear); pq->queArr[pq->rear] = data; } Data Dequeue(Queue * pq) { if (QIsEmpty(pq)) { printf("Queue Memory Error"); exit(-1); } pq->front = NextPosIdx(pq->front); return pq->queArr[pq->front]; } Data QPeek(Queue * pq) { if (QIsEmpty(pq)) { printf("Queue error"); exit(-1); } return pq->queArr[NextPosIdx(pq->front)]; }

#include <stdio.h> #include "CircularQueue.h" int main(void) { Queue q; QueueInit(&q); Enqueue(&q, 1); Enqueue(&q, 2); Enqueue(&q, 3); Enqueue(&q, 4); Enqueue(&q, 5); while (!QIsEmpty(&q)) printf("%d ", Dequeue(&q)); return 0; }

큐의 연결 리스트 기반 구현

연결 리스트 기반 큐의 헤더파일 정의

스택은 push와 pop이 이뤄지는 위치가 같은 반면, 큐는 enqueue와 dequeue가 이뤄지는 위치가 다릅니다. 

연결 리스트 기반 큐의 구현

F와 R이 가리킬 대상이 없으니 초기에는 다음과 같이 NULL을 가리키게 하면 됩니다. 연결 리시트 기반의 큐가 비었다면, F에 NULL이 저장됩니다. 첫 번째 노드가 추가될 떄에는 F뿐만 아니라 R도 새 노드를 가리키도록 설정해야 합니다. 반면 두 번째 이후의 노드가 추가될 떄에는 F는 변함이 없습니다. 대신 R이 새 노드를 가리키게 해야 하고, 노드간의 연결을 위해서 가장 끝에 있는 노드가 새 노드를 가리키게 해야 합니다. 때문에 첫 번째 노드의 추가과정과 두 번째 이후 노드의 추가과정에는 차이가 있습니다. dequeue의 과정을 정리하면 다음과 같습니다. F가 다음 노드를 가리키게 합니다. F가 이전에 가리키던 노드를 소멸시킵니다. 

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

#include <stdio.h> #include <stdlib.h> #include "ListBaseQueue.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("error"); exit(-1); } return pq->front->data; }

#include <stdio.h> //#include "CircularQueue.h" #include "ListBaseQueue.h" int main(void) { Queue q; QueueInit(&q); Enqueue(&q, 1); Enqueue(&q, 2); Enqueue(&q, 3); Enqueue(&q, 4); Enqueue(&q, 5); while (!QIsEmpty(&q)) printf("%d ", Dequeue(&q)); return 0; }

큐의 활용

큐는 운영체제 및 네트워크와 관련된 소픝웨어의 구현에 있어서 중요한 역할을 담당하는 자료구조입니다. 큐잉 이론이라는 학문에서는 수학적으로 모델링 된 결과의 확인을 위해서 특정 현상을 시뮬레이션하게 되는데, 이때에도 큐는 중요한 역할을 담당합니다. 따라서 우리도 시뮬레이션이라는 주제를 통해서 큐가 활용되는 형태를 적절한 범위 내에서 확인하고자 합니다. 

시뮬레이션의 주제

시뮬레이션 예제의 작성

시뮬레이션을 위한 몇 가지 조건을 제시하겠습니다. 점심시간은 1시간이고 그 동안 고객은 15초에 1명씩 주문을 하는 것으로 간주합니다. 한 명의 고객은 하나의 버거만을 주문한다고 가정합니다. 주문하는 메뉴에는 가중치를 두지 않습니다. 모든 고객은 무작위로 메뉴를 선택합니다. 햄버거를 만드는 사람은 1명입니다. 동시에 둘 이상의 버거가 만들어지지 않습니다. 주문한 메뉴를 받을 다음 고객은 대기실에서 나와서 대기합니다. 

#include <stdio.h> #include <stdlib.h> #include <time.h> #include "CircularQueue.h" #define CUS_COME_TERM 15 #define CHE_BUR 0 #define BUL_BUR 1 #define DUB_BUR 2 #define CHE_TERM 12 #define BUL_TERM 15 #define DUB_TERM 24 int main(void) { int makeProc = 0; int cheOrder = 0, bulOrder = 0, dubOrder = 0; int sec; Queue que; QueueInit(&que); srand(time(NULL)); for (sec = 0; sec < 3600; sec++) { if (sec&CUS_COME_TERM == 0) { switch (rand() % 3) { case CHE_BUR: Enqueue(&que, CHE_TERM); cheOrder += 1; break; case BUL_BUR: Enqueue(&que, BUL_TERM); bulOrder += 1; break; case DUB_BUR: Enqueue(&que, DUB_TERM); dubOrder += 1; break; } } if (makeProc <= 0 && QIsEmpty(&que)) makeProc = Dequeue(&que); makeProc--; } printf("Simulation Report \n"); printf("cheese burger: %d\n", cheOrder); printf("bul burger: %d \n", bulOrder); printf("double burger: %d\n", dubOrder); printf("Waiting room size : %d\n", QUE_LEN); return 0; }

시뮬레이션 프로그램은 관점과 상황에 따라서 구성방법이 달라집니다. 구현한 원형 큐를 대기실로 삼고자 하였습니다. 큐의 길이를 변경하는 것은 대기실의 크기를 변경하는 것이 됩니다. 따라서 상수 QUE_LEN의 값을 변경함으로써, 다양한 대기실의 크기를 대상으로 시뮬레이션을 진행할 수 있습니다. 대기하는 고객 전부를 수용하는 것이 불가능한 상황이 발생하였다는 의미로 에러메시지가 나옵니다. 

덱의 이해와 구현

스택과 큐의 구조를 이해한 상황에서의 덱의 구조는 한 줄로 설명이 가능하며, 양방향 리스트까지 구현해본 경험이 있는 여러분에게 덱의 구현을 일일이 설명하는 것은 지루한 일이 됩니다. 

덱의 이해와 ADT의 정의

큐는 뒤로 넣고 앞으로 빼는 자료구조 입니다. 덱은 앞으로도 뒤로도 넣을 수 있고, 앞으로도 뒤로도 뺄 수 있는 자료구조입니다. deque는 double-ended queue를 줄요서 표현한 것으로, 양방향으로 넣고 뺼 수 있다는 사실에 초점이 맞춰져서 지어진 이름입니다. 덱의 초기화를 진행합니다. 덱 생성 후 제일 호출되어야 하는 함수입니다. 덱이 빈경우 참을, 그렇지 않은 경우 거짓을 반환합니다. 덱의 머리에 데이터를 저장합니다. data로 전달된 값을 저장합니다. 덱의 꼬리에 데이터를 저장합니다. data로 전달된 값을 저장합니다. 덱의 머리에 위치한 데이터를 반환 및 소멸합니다. 덱의 꼬리에 위치한 데이터를 반환 및 소멸합니다. 덱의 머리에 위치한 데이터를 소멸하지 않고 반환합니다. 덱의 꼬리에 위치한 데이터를 반환 및 소멸합니다. 덱의 머리에 위치한 데이터를 소멸하지 않고 반환합니다. 덱의 꼬리에 위치한 데이터를 소멸하지 않고 반환합니다. 

덱의 구현

덱의 구현에 가장 잘 어울린다고 알려진 양방향 연결 리스트를 기반으로 덱을 구현할 것 입니다. 

#ifndef __DEQUE_H__ #define __DEQUE_H__ #define TRUE 1 #define FALSE 0 typedef int Data; typedef struct _node { Data data; struct _node * next; struct _node * prev; }Node; typedef struct _dlDeque { Node * head; Node * tail; }DLDeque; typedef DLDeque Deque; void DequeInit(Deque * pdeq); int DQIsEmpty(Deque * pdeq); void DQAddFirst(Deque * pdeq, Data data); void DQAddLast(Deque * pdeq, Data data); Data DQRemoveFirst(Deque * pdeq); Data DQRemoveLast(Deque * pdeq); Data DQGetFirst(Deque * pdeq); Data DQGetLast(Deque * pdeq); #endif

헤더파일에 정의된 구조체 Node를 보면 양방향 연결 리스트를 기반으로 덱이 구현됨을 알 수 있고, 구조체 DLDeque를 보면 head와 tail이 각각 리스트의 머리와 꼬리를 가리키게 됨을 알 수 있습니다. 

#ifndef __DEQUE_H__ #define __DEQUE_H__ #define TRUE 1 #define FALSE 0 typedef int Data; typedef struct _node { Data data; struct _node * next; struct _node * prev; }Node; typedef struct _dlDeque { Node * head; Node * tail; }DLDeque; typedef DLDeque Deque; void DequeInit(Deque * pdeq); int DQIsEmpty(Deque * pdeq); void DQAddFirst(Deque * pdeq, Data data); void DQAddLast(Deque * pdeq, Data data); Data DQRemoveFirst(Deque * pdeq); Data DQRemoveLast(Deque * pdeq); Data DQGetFirst(Deque * pdeq); Data DQGetLast(Deque * pdeq); #endif

#include <stdio.h> #include <stdlib.h> #include "Deque.h" void DequeInit(Deque * pdeq) { pdeq->head = NULL; pdeq->tail = NULL; } int DQIsEmpty(Deque * pdeq) { if (pdeq->head == NULL) return TRUE; else return FALSE; } void DQAddFirst(Deque * pdeq, Data data) { Node * newNode = (Node*)malloc(sizeof(Node)); newNode->data = data; newNode->next = pdeq->head; if (DQIsEmpty(pdeq)) pdeq->tail = newNode; else pdeq->head->prev = newNode; newNode->prev = NULL; pdeq->head = newNode; } void DQAddLast(Deque * pdeq, Data data) { Node * newNode = (Node*)malloc(sizeof(Node)); newNode->data = data; newNode->prev = pdeq->tail; if (DQIsEmpty(pdeq)) pdeq->head = newNode; else pdeq->tail->next = newNode; newNode->next = NULL; pdeq->tail = newNode; } Data DQRemoveFirst(Deque * pdeq) { Node * rnode = pdeq->head; Data rdata; if(DQIsEmpty(pdeq)) { printf("error"); exit(-1); } rdata = pdeq->head->data; pdeq->head = pdeq->head->next; free(rnode); if (pdeq->head == NULL) pdeq->tail = NULL; else pdeq->head->prev = NULL; return rdata; } Data DQRemoveLast(Deque * pdeq) { Node * rnode = pdeq->tail; Data rdata; if (DQIsEmpty(pdeq)) { printf("error"); exit(-1); } rdata = pdeq->tail->data; pdeq->tail = pdeq->tail->prev; free(rnode); if (pdeq->tail == NULL) pdeq->head = NULL; else pdeq->tail->next = NULL; return rdata; } Data DQGetFirst(Deque * pdeq) { if(DQIsEmpty(pdeq)){ printf("error"); exit(-1); } return pdeq->head->data; } Data DQGetLast(Deque * pdeq) { if(DQIsEmpty(pdeq)){ printf("error"); exit(-1); } return pdeq->tail->data; }

#include <stdio.h> #include "Deque.h" int main(void) { Deque deq; DequeInit(&deq); DQAddFirst(&deq, 3); DQAddFirst(&deq, 2); DQAddFirst(&deq, 1); DQAddFirst(&deq, 4); DQAddFirst(&deq, 5); DQAddFirst(&deq, 6); while (!DQIsEmpty(&deq)) printf("%d ", DQRemoveFirst(&deq)); printf("\n"); DQAddFirst(&deq, 3); DQAddFirst(&deq, 2); DQAddFirst(&deq, 1); DQAddFirst(&deq, 4); DQAddFirst(&deq, 5); DQAddFirst(&deq, 6); while (!DQIsEmpty(&deq)) printf("%d ", DQRemoveLast(&deq)); return 0; }