배열을 기반으로 큐를 구현하는 경우 몇가지 고려할 사항이 있었다. 그래서 원형 큐를 소개했고, 또 큐가 꽉 찬 경우와 텅 빈 경우를 구분하는 방법도 소개하였다. 하지만 연결리스트를 기반으로 구현하는 경우에는 의외로 신경 쓸 부분이 적다.
연결 리스트 기반 큐의 헤더파일 정의
"스택과 큐의 유일한 차이점은 앞에서 꺼내느냐 뒤에서 꺼내느냐에 있으니 ,이전에 구현해 놓은 스택을 대상으로 꺼내는 방법만 조금 변경하면 큐가 될꺼같다"
위의 판단은 배열 기반에서는 옳지 않았지만, 연결리스트 기반의 큐라면, 위의 판단은 어느 정도 옳다. 연결리스트를 기반으로 구현하면 앞서 논의한 고민거리들이 사라지기 때문이다. 하지만 다음과 같은 차이점이 있기 때문에 여전히 스택의 구현과는 차이가 있다고 말할 수 있다.
"스택은 push와 pop이 이뤄지는 위치가 같은 반면, 큐는 enqueue와 dequeue가 이뤄지는 위치가 다르다"
먼저 연결리스트 기반의 큐의 헤더파일을 구현하자.
//ListBaseQueue.h
#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; //그림을 통해서 F라 표현한 멤버
Node *rear; //그림을 통해서 R이라 표현한 멤버
}LQueue;
typedef LQueue Queue;
void QueueInit(Queue *pq);
int QIsEmpty(Queue *pq);
void Enqueue(Queue *pq, Data data); //enqueue연산 담당 함수
Data Dequeue(Queue *pq); //dequeue 연산 담당함수
Data QPeek(Queue *pq);
#endif위의 헤더파일에서 보이듯이 연결리스트 기반의 큐에서도 원형 큐와 마찬가지로 front와 rer을 유지해야 한다. enqueue 연산과 dequeue 연산이 이뤄지는 위치가 다르기 때문이다.
연결 리스트 기반의 큐의 구현
이제 연결리스트 기반의 큐의 동작형태를 간단하게나마 정리해보자. 처음 큐가 생성된 이후의 모습은 다음과 같다. F와 R이 가리킬 대상이 없으니 초기에는 다음과 같이 NULL을 가리키게 하면 된다.
F->NULL
R->NULL
따라서 QueueInit 함수는 다음과 같이 정의해야 한다.
void QueueInit(Queue *pq)
{
pq->front =NULL; //이후에도 front를 F라 표현한다.
pq->rear = NULL; //이후에도 rear을 R이라 표현한다.
}
그리고 F가 가리키는 노드를 대상으로 dequeue연산이 진행되니, 다음과 같이 판단할 수 있다.
"연결 리스트 기반의 큐가 비었다면, F에 NULL이 저장된다"
이렇듯 R을 제외한 F만을 참조하여 큐가 비었는지 판단을 하면, 이후에 큐가 텅 비게 되는 경우에도 F만을 신경쓰면 되기 때문에 여러모로 편리하다. 그럼 이어서 QIsEmpty 함수를 정의하겠다.
int QIsEmpty(queue *pq)
{
if(pq->front==NULL) //F에 NULL이 저장되어 있으면
return TRUE; //큐가 텅 빈 것이니 TRUE를 반환한다.
else
return FALSE;
}
이제 Enqueue 함수를 정의할 차례인데, 이 경우에는 큐의 머리를 가리키는 front 뿐만 아니라 큐의 꼬리를 가리키는 rear도 있다는데 주의해야 한다. 이 떄문에 노드의 추가과정이 둘로 나뉘기 때문이다. 그럼 다음 과정을 보면서 이와 관련된 설명을 진행하겠다.
F->2->NULL
2는 newNode, R 은 2를 가리키는 상태
위 상태에서 enqueue 4를 진행해보자
F->2->4->NULL
4는 newNode, R은 4를 가리키는 상태
위 과정에서 보이듯이, 첫 번째 노드가 추가될 때에는 F뿐만 아니라 R도 새 노드를 가리키도록 설정한다. 반면 두 번째 이후의 노드가 추가될 때에는 F는 변함이 없다. 대신 R이 새노드를 가리키게 해야 하고, 노드간의 연결을 위해서 가장 끝에 있는 노드가 새 노드를 가리키게 해야한다. 떄문에 첫 번째 노드의 추가과정과 두 번째 이후 노드의 추가과정에는 차이가 있다. 그럼 이러한 내용을 근거로 Enqueue 함수를 정의해 보자.
void Enqueue(Queue *pq, Data data)
{
Node *newNode= (Node *)malloc(sizeof(Node));
newNode->next = NULL;
newNode->data =data;
if(QIsEmpty(pq)) //첫 번째 노드의 추가라면
{
pq->front= newNode; //front가 새 노드를 가리키게 하고,
pq->rear= newNode; //rear도 새 노드를 가리키게 한다.
}
else
{
pq->rear->next= newNode; //마지막 노드가 새 노드를 가리키게 하고,
pq->rear = newNode; //rear가 새 노드를 가리키게 한다.
}
}
이제 마지막으로 Dequeue 함수를 정의할 차례인데, 이와 관련해서 다음과 같이 생각할 수 도 있다.
"Enqueue 함수의 구현과 마찬가지로 노드의 삭제과정도 둘로 나뉠 것이다"
하지만 그렇지 않다. 노드의 삭제과정에서는 신경 쓸 부분은 F하나이기 때문이다.
일단 삭제과정을 보이겠다.
F->2->4->6->NULL
R은 6을 가리킴
여기서 dequeue 연산을 진행하면 F가 가리키는 노드를 삭제할 것이다.
F->4->6->NULL
R은 6을 가리킴
위 과정에서는 dequeue의 과정을 보이고 있다. 위 과정에서 보이는 dequeue의 과정을 정리하면 다음과 같다.
1. F가 다음 노드를 가리키게 한다.
2. F가 이전에 가리키던 노드를 소멸시킨다.
때문에 위 과정의 상태에서 다시 한번 dequeue 연산을 진행하면 F와 R이 모두 6이 저장된 노드를 가리키게 되어 다음의 상태에 이르게 된다.
F->6->NULL
R은 6을 가리킴
문제는 그 다음이다. 위 과정의 상태에서 다시 한번 dequeue 연산을 하는 경우의 처리 방식이 문제이다. 만약에 앞서 하던 방식대로 처리한다면, 다시 말해서 F가 가리키는 대상을 그 다음 노드로 변경시키고, F가 이전에 가리키던 노드를 삭제한다면 다음의 상태가 된다.
F->NULL
R->???
우선 F에 NULL이 저장되었음에 주목하자. 이는 자연스러운 결과이다. F는 6이 저장된 노드를 참조하여 다음 노드의 주소값을 얻게 되는데 그 값이 NULL이다. 그래서 F에는 NULL이 저장된다.
위 과정의 결과에서 R에 NULL이 아닌 다른 값이 저장되어 있는데 이 것이 문제가 되지는 않을까?
문제 되지 않는다.
우리는 QIsEmpty 함수를 정의할 떄에도 F에 저장된 값만을 참조하여 TRUE도 또는 FALSE 를 반환하도록 정의하였다.
이렇듯 큐가 텅 비었는지 확인할 때에도 F만을 참조하니, R에 쓰레기 값이 저장된 위의 상황은 문제되지 않는다.
그리고 굳이 R에 NULL을 넣을 필요가 없다면, dequeue의 과정은 둘로 나뉘지 않는다. 때문에 다음과 같이 Dequeue 함수를 간단히 정의할 수 있다.
Data Dequque(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; //삭제할 노드의 다음 노드를 front가 가리킴
free(delNode);
return retData;
}
이로써 연결 리스트를 기반으로 하는 큐의 구현도 끝났다.
//ListBaseQueue.h
#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; //그림을 통해서 F라 표현한 멤버
Node *rear; //그림을 통해서 R이라 표현한 멤버
}LQueue;
typedef LQueue Queue;
void QueueInit(Queue *pq);
int QIsEmpty(Queue *pq);
void Enqueue(Queue *pq, Data data); //enqueue연산 담당 함수
Data Dequeue(Queue *pq); //dequeue 연산 담당함수
Data QPeek(Queue *pq);
#endif//ListBaseQueue.c
#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("Queue Memory Error!");
exit(-1);
}
return pq->front->data;
}
//ListBaseQueueMain.c
#include <stdio.h>
#include "ListBaseQueue.h"
int main()
{
//Queue의 생성 및 초기화
Queue q;
QueueInit(&pq);
//데이터 넣기
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 2 3 4 5이로써 연결리스트 기반의 큐를 구현하였다.
큐의 활용
큐는 운영체제 및 네트워크와 관련된 소프트웨어의 구현에 있어서 중요한 역할을 담당하는 자료구조이다. 그리고 '큐잉 이론 (queuing theory)'이라는 학문에서 수학적으로 모델링 된 결과의 확인을 위해서 특정 현상을 '시뮬레이션(simulation)'하게 되는데, 이때에도 큐는 중요한 역할을 담당한다. 따라서 우리도 시뮬레이션이라는 주제를 통해서 큐가 활용되는 형태를 적적한 범위 내에서 확인하고자 한다.
시뮬레이션의 주제
알다시피 특정 상황에 놓인 복잡한 문제의 해결을 위해서 실제와 비슷한 상황을 연출하는 것을 가리켜 '시뮬레이션'이라 한다.
다음 예제는 특정한 상황을 기획한 것이다.
패스트푸드점에서 고객을 위한 대기실을 만들기 위해서 시뮬레이션을 하는 것이다.
점심시간 1시간을 기준으로 15초에 1명씩 주문을 한다고 가정을 하고,
치즈버거 12초, 불고기버거 15초, 더블버거 24초 로 제작시간을 가정한다.
만약
수용인원이 30명인 공간은 안정적으로 고객을 수용할 확률 50프로
수용인원이 50명인 공간은 안정적으로 고객을 수용할 확률 70프로
수용인원이 100명인 공간은 안정적으로 고객을 수용할 확률 90프로
수용인원이 200명인 공간은 안정적으로 고객을 수용할 확률 100프로
로 생각한다.
위에서 안정적으로 고객을 수용할 확률이 50%라는 것은 10회 시뮬레이션을 진행한 결과, 대기하는 고객 전부를 수용하는 것이 불가능한 상황이 5회, 즉 50%의 비율로 발생했다는 의미이다.
시뮬레이션의 예제의 작성
실제 현상에 근접한 형태로 시뮬레이션을 하기 위해서는 고려해야 할 사항이 매우 많다. 그러나 큐가 시뮬레이션의 도구가 될 수 있음을 경함하는 것이 우리의 목적인 만큼, 그 목적에 부합하는 정도의 예제를 작성하고자 한다. 그럼 시뮬레이션을 위한 몇 가지 조건을 제시하겠다.
-점심시간은 1시간이고 그 동안 고객은 15초에 1명씩 주문을 하는 것으로 간주한다.
-한명의 고객은 하나의 버거만을 주문한다고 가정한다.
-주문하는 메뉴에는 가중치를 두지 않는다. 모든 고객은 무작위로 메뉴를 선택한다.
-햄버거를 만드는 사람은 1명이다. 그리고 동시에 둘 이상의 버거가 만들어 지지 않는다.
-주문한 메뉴를 받을 다음 고객은 대기실에서 나와서 대기한다.
그리고 고객이 주문하는 메뉴에 가중치를 두지 않기 위해서 다음 함수를 사용하기로 하겠다.
int rand(void) //무작위 메뉴의 선택을 위해서
다음예제에서는 시뮬레이션에서 큐가 어떻게 활용되는지를 보일뿐, 현실적으로 타당한 시뮬레이션 상황을 연출한 것은 아니다.
//HamburgerSim.c
#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()
{
int makeProc = 0 ; //햄버거 제작 진행 상황
int cheOrder =0, bulOrder=0, dubOrder =0;
int sec;
Queue que;
QueueInit(&que);
srand(time(NULL));
//아래 for문의 1회 회전은 1초의 시간 흐름을 의미함
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(" - Bulogogi burger : %d \n", bulOrder);
printf(" - Double burger : %d \n", dubOrder);
printf(" -Wating room size : %d \n", QUE_LEN);
return 0;
}
=======================실행 결과=========================
//CircularQueue.h, CircularQueue.c, HamburgerSim.c
Simulation Report!
- Chees burger : 80
- Bulgogi burger : 72
- Double burger : 88
- Waiting room size : 100
====================실행결과 2===============================
Queue Memory Error!
시뮬레이션 프로그램은 관점과 상황에 따라서 구성방법이 달리진다.
#include "CircularQueue.h"
위 문장에서 보이듯이, 앞서 우리가 구현한 원형 큐를 대기실로 삼고자 하였다. 따라서 대기실에 수용할 수 있는 고객의 수는 다음 문장을 통해서 지정하였다.
#define QUE_LEN 100 //100명을 수용할 수 있는 대기실
위의 문장은 헤더파일 CircularQueue.h에 존재한다. 즉 큐의 길이를 변경하는 것은 대기실의 크기를 변경하는 것이 된다. 따라서 상수 QUE_LEN의 값을 변경함으로써, 다양한 대기실의 크기를 대상으로 시뮬레이션을 진행할 수 있다.
그럼 이어서 예제의 핵심인 for문의 의도를 설명하겠다. 에제는 for문은 총 3600회 반복을 하는데 이것은 1시간의 점심시간을 표현한 것이다. 즉 for문의 1회전은 1초의 흐름을 의미한다. 따라서 for문 안에 다음의 if문이 존재한다.
if(sec % CUS_COME_TERM ==0) //15초에 1회씩 TRUE가 된다.
{
switch(rand() %3) //CHE_BUR, BUL_BUR, DUB_BUR 중 랜덤 선택
{
case CHE_BUR:
Enqueue(&que, CHE_TERM);
...
case BUL_BUR;
Enqueue(&que, BUL_TERM);
...
case DUB_BUR;
Enqueue(&que, DUB_TERM);
...
}
}
그리고 고객의 주문 간격인 CUS_COME_TERM의 값이 15이니, 위의 if문은 15초에 1회씩 TRUE가 되어 다음 세문장 중 한 문장을 실행하게 된다.
Enqueue(&que, CHE_TERM); //치즈버거 주문 후 대기실 이동
Enqueue(&que, BUL_TERM); //불고기버거 주문 후 대기실 이동
Enqueue(&que, DUB_TERM); //더블버거 주문 후 대기실 이동
그리고 위의 세 문장 중 한문장을 실행했다는 것은 다음의 의미를 갖는다.
"햄버거를 주문하고 대기실에 들어간다."
그런데 실제 큐에 저장되는 것은 고객이 주문한 메뉴의 버거를 만드는데 소요되는 시간의 정보이다. 예를 들어 치즈버거가 주문이 되면, 치즈버거를 만드는데 소요되는 시간으로 정의된 상수 CHE_TERM이 저장된다. 그리고 대기실이 꽉 차면 Enqueue 함수의 호출과정에서 다음 메세지가 출력되면서 프로그램이 종료된다.
Queue Memory Error!
즉 예제의 실행 결과로 위의 메세지가 출력되었다는 것이 의미하는 바는 다음과 같다.
"대기하는 고객 전부를 수용하는 것이 불가능한 상황이 발생하였다."
그리고 주문한 메뉴를 받을 다음 고객은 대기실에서 나와서 대기해야 하는데, for문 내에서 이를 표현한 코드는 다음과 같다.
if(makeProc <= 0 && !QIsEmpty(&que))
makeProc = Dequeue(&que); //대기실에 나와서 대기한다.
Dequeue 함수의 반환 값은 makeProc에 저장되고 for문의 마지막 문장에서는 makeProc의 값을 1씩 감소시킨다. 때문에 makeProc의 값이 결국 0이 되고, 이는 버거가 완성되었다는 뜻이니, 그 다음 손님이 대기실에서 나와야 한다. 그리고 이를 위해서 Dequeue 함수를 재호출하게 된다.
끝으로 for문을 무사히 빠져나오면, 이는 1시간 동안 대기실의 자리가 부족하지 않았다는 뜼이 되어, 1시간동안 버거 별 주문 수량이 출력된다.
'휴지통 > 자료구조-C' 카테고리의 다른 글
| 트리 1 (0) | 2021.03.02 |
|---|---|
| 덱(Deque)의 이해와 구현 (0) | 2021.03.01 |
| 큐(Queue) (0) | 2021.02.27 |
| 스택을 활용한 계산기 구현 (0) | 2021.02.24 |
| 스택 (0) | 2021.02.23 |
