C로 만드는 자료구조- 큐를 이용한 평균 대기 시간 구하기

대기열 시물레이션

큐의 선입선출 특성을 이용하여 다양한 시물레이션을 진행할 수 있다. 지금 해볼 것은 대기열에서 평균 대기 시간이 얼마나 되는지 이다.

예를 들어 한 손님이 은행에 갔다고 생각해보자. 은행에 들어가면 앞에 손님이 없다면 바로 서비스를 받을 수 있지만 손님이 있다면 먼저 온 손님이 모두 서비스를 받고 난 후에야 서비스를 받을 수 있을 것이다. 우리는 이러한 상황을 구현하여 어떤 손님이 은행에서 서비스를 받을 때까지의 대기 시간은 얼마이며, 은행이 문을 닫을때까지 손님들의 총 대기 시간, 평균 대기 시간을 예측할 것이다.

먼저 시물레이션에 사전 조건에 대해서 설명하자면 서비스를 처리하는 곳(은행 창구)는 1개이다. 그리고 손님의 정보로는 도착 시간, 서비스를 처리하는데 드는 시간(서비스시간) 이 있다.

예를 들어 첫번째 손님의 도착 시각은 0이고 서비스시간이 3인데 두번째 고객의 도착 시각은 2라고 해보자. 현재 시각이 2일때 아직 첫번째 손님의 서비스가 끝나지 않았으므로 두번째 고객은 바로 서비스르 받지 못하고 첫번째 고객의 서비스가 끝나는 시각인 3 부터 두번째 고객이 서비스를 받을 수 있게 된다. 이런 경우 두번째 고객의 대기 시간은 1이 된다.

아래 표를 통해 임의의 상황을 표로 정리했다.

아래는 숫자로 정리한 표이다.

고객	도착 시각	서비스 시간	시작 시각	종료 시각 (시작시각+ 서비스 시간)	대기 시간 (시작시각+ 도착 시각)
1 번째 고객	0	3	0	3	0
2 번째 고객	2	2	3	5	1
3 번째 고객	4	1	5	6	1
4 번째 고객	6	1	6	7	0
5 번째 고객	8	-	8	-	0

대기열 시물레이션 구현

이 시스템을 구현하기 위해서 고객 도착 큐, 고객 도착 큐 와 서비스노드 1개를 사용할 것이다.

- 고객 도착 큐: 모든 고객들이 미리 저장되어 있는 큐이다. 이때 도착 시각 순서대로 저장한다고 가정한다.

- 고객 대기 큐: 고객 도착 큐 내의 고객들 중에서 정해진 도착 시각이 되면 고객 대기 큐로 넘어온다. 이때 고객 도착큐에서는 디큐 연산, 고객 대기큐에서는 인큐 연산을 한다.

- 서비스 노드: 서비스 노드에서는 고객이 정해진 시간만큼 서비스를 받는다. 그래서 매 시각 서비스가 종료되었는지 점검한다. 만약 서비스가 종료되면 메모리 해제를 하고 다음 서비스를 받을 노드를 고객 대기 큐에서 받아온다.

그림으로 나타내면 다음과 같다.

소스 파일 구성은 다음과 같다.

파일 이름	내용
linkedqueue.h	큐에 대한 구조체 및 함수 선언(이전 코드 그래로 사용)
linkedqueue.cpp	큐에 대한 함수 구현(이전 코드 그래도 사용)
customer.h	고객에 대한 구조체 선언
queuesimulation.h	대기열 시물레이션 함수 선언
queuesimulation.cpp	대기열 시물레이션 함수 구현
queuesimulationmain.cpp	main 함수 실행

1.customer.h

고객에 대한 구조체를 선언한다. 이때 고객이 해야할 행동은 딱히 없기 때문에 관련 함수는 딱히 없다.

#pragma once

enum SimStatus{ arrival, start, END};
struct Customer {
	SimStatus status;
	int arrivaltime; //도착 시간
	int servicetime; //서비스 시간
	int starttime;// 시작 시간
	int endtime; // 종료 시각(도착 시간+ 서비스 시간)
};

Simstatus는 고객의 상태를 나타내며 arrival, start ,END 3가지 상태가 있다. 여러가지 시간 관련된 내부 변수들을 포함한다.

2. linkedQueue.h , linkedQueue.cpp

이전에 구현했던 코드를 그대로 사용한다. 단 LinkedQueue 구조체 선언 부분에서 int data를 Customer data로 바꿔주어야 한다. 이에 따라 displayLQ() 함수 또한 변경점이 생기기 때문에 주석 처리 해주었다. 출력 관련해서는 따로 함수를 구현할 예정이다.

코드 구현은 다음과 같다.

#include"customer.h"
using namespace std;

#define TRUE 1
#define FALSE 0

typedef struct QueueNode {
	Customer data;
	struct QueueNode* pLink;
};

typedef struct LinkedQueue {
	int currentSize;
	QueueNode* pFront;
	QueueNode* pRear;
};

LinkedQueue* createLQ(); // 큐 생성
int enqueueLQ(LinkedQueue* pQueue, QueueNode element); // 큐 enqueue
QueueNode* dequeueLQ(LinkedQueue* pQueue); // 큐 dequeue
QueueNode* peekLQ(LinkedQueue* pQueue); // 큐 peek
void deleteLQ(LinkedQueue* pQueue); // 큐 삭제
int isEmptyLQ(LinkedQueue* pQueue); // 빈 큐인지 확인
// void displayLQ(LinkedQueue* pQueue);// 큐 자료 출력


// linkedqueue.cpp 

LinkedQueue* createLQ() {
	LinkedQueue* pReturn = new LinkedQueue;
	if (pReturn != NULL) {
		memset(pReturn, 0, sizeof(LinkedQueue));

	}
	else {
		cout << "메모리 할당 오류" << endl;
	}
	return pReturn;
}
int enqueueLQ(LinkedQueue* pQueue, QueueNode element) {
	int ret = FALSE;
	QueueNode* pNode = new QueueNode;
	if (pQueue != NULL) {

		*pNode = element;

		if (isEmptyLQ(pQueue) == TRUE) {
			pQueue->pFront = pNode;
		}
		else {
			pQueue->pRear->pLink = pNode;
		}
		pQueue->pRear = pNode;
		pQueue->currentSize++;
		ret = TRUE;
	}
	return ret;
}
QueueNode* dequeueLQ(LinkedQueue* pQueue) {
	QueueNode* pReturn = new QueueNode;
	if (pQueue != NULL) {

		if (isEmptyLQ(pQueue) == FALSE) {
			pReturn = pQueue->pFront;
			if (pQueue->currentSize == 1) {
				pQueue->pFront = NULL;
				pQueue->pRear = NULL;
			}
			else {
				pQueue->pFront = pReturn->pLink;
			}
			pQueue->currentSize--;
		}
		else {
			cout << "공백 큐 입니다." << endl;
		}
	}
	return pReturn;
}
QueueNode* peekLQ(LinkedQueue* pQueue) {

	QueueNode* pReturn = new QueueNode;
	if (pQueue != NULL) {
		if (isEmptyLQ(pQueue) == FALSE) {
			pReturn = pQueue->pFront;
		}
		else {
			cout << "공백 큐 입니다." << endl;
		}
	}
	return pReturn;
}
void deleteLQ(LinkedQueue* pQueue) {

	QueueNode *pNode = NULL;
	QueueNode *pDelNode = NULL;
	pNode = pQueue->pFront;
	if (pQueue != NULL) {
		for (int i = 0; i < pQueue->currentSize; i++) {
			pDelNode = pNode;
			pNode = pNode->pLink;
			delete pDelNode;
		}
	}
	delete pQueue;

}
int isEmptyLQ(LinkedQueue* pQueue) {
	int ret = FALSE;
	if (pQueue != NULL) {
		if (pQueue->currentSize == 0) {
			ret = TRUE;
		}
	}
	return ret;
}
/*
void displayLQ(LinkedQueue* pQueue) {
	if (pQueue != NULL) {
		QueueNode *pNode = NULL;
		pNode = pQueue->pFront;
		cout << "현재 자료 개수: " << pQueue->currentSize << endl;
		for (int i = 0; i < pQueue->currentSize; i++) {
			cout << "[" << i << "] - [" << pNode->data << "]" << endl;
			pNode = pNode->pLink;
		}
	}
}
*/

3.queuesimulationmain.h

먼저 대기열 시물레이션의 전체적인 구조부터 설명 하겠다.

코드 구현은 다음과 같다.

#include "stdafx.h"
#include "linkedqueue.h"
#include"queuesimulation.h"
int main()
{
	int currenttime = 0;
	int endtime = 10;
	int serviceUsercount = 0;
	int total = 0;

	LinkedQueue *pArrivalQueue = NULL; // 고객 도착 큐
	LinkedQueue *pWaitQueue = NULL; // 고객 대기 큐
	QueueNode* pServiceNode=NULL;// 서비스 노드


	pArrivalQueue = createLQ();
	pWaitQueue = createLQ();
	insertCustomer(0, 3, pArrivalQueue); // 첫번째 고객
	insertCustomer(2, 2, pArrivalQueue); // 두번째 고객
	insertCustomer(4, 1, pArrivalQueue); // 세번째 고객
	insertCustomer(6, 1, pArrivalQueue); // 네번째 고객
	insertCustomer(8, 3, pArrivalQueue); // 다섯번째 고객

	for (currenttime = 0; currenttime < endtime; currenttime++) {
		processArrival(currenttime, pArrivalQueue, pWaitQueue);
		
		//서비스 종료 처리

		if (pServiceNode != NULL) {
			pServiceNode = processServiceNodeEnd(currenttime, pServiceNode, &serviceUsercount, &total);
		}
		//서비스 시작 처리
		if (pServiceNode == NULL) {
			pServiceNode = processServiceNodeStart(currenttime, pWaitQueue);
		}

		//대기 큐 상태 출력
		displayWaitQueueStatus(currenttime, pWaitQueue);
	}
	//최종 시물레이션 결과 출력
	
	printReport(pWaitQueue, serviceUsercount, total);

	//메모리 해제
	if (pServiceNode != NULL) {
		delete pServiceNode;
	}
	deleteLQ(pArrivalQueue);
	deleteLQ(pWaitQueue);
    return 0;
}

먼저 시스템이 돌아가는 총 시간은 0초에서 9초 까지이고 시간의 흐름은 for문을 이용하여 나타냈다. 사용할 2개의 큐와 1개의 노드를 선언 해주었다.

for문 내의 구조는 먼저 processArrival()함수를 이용해 현재 시각에 도착한 고객이 있는지 확인하다. 있다면 pWaitQueue에 저장된다. 도착한 고객 확인 후에는 먼저 서비스 노드에 있는 고객의 서비스가 종료되었는지 확인한다. 이때 processServiceNodeEnd() 함수를 사용한다. 서비스 종료 확인 후에 만약 서비스 노드가 비어있다면 서비스 시작처리를 한다. 이때 pWaitQueue에서 가장 앞에 있는 노드를 꺼내온다. 그 후에는 pWaitQueue의 상태를 출력 하여 현재 시각 몇명의 고객이 대기열에 있는지 출력한다.

위 작업이 모두 끝나면 전체 결과를 출력하고 메모리 해제를 해준다. 이때 전체 결과는 처리한 고객 수, 평균 대기 시간, 현재 대기열의 고객 수가 있다.

4.queuesimulation.h

대기열 시물레이션을 구현하는 함수들을 선언한다. 자세한 설명은 함수 구현 부분에서 하겠다.

코드 구현은 다음과 같다.

#pragma once
#include"linkedqueue.h"


void insertCustomer(int arrivaltime, int servicetime, LinkedQueue *pQueue); // 고객 도착 큐에 손님 추가
void processArrival(int currenttime,LinkedQueue* pArrivalQueue, LinkedQueue *pWaitQueue); // 고객 도착 처리
QueueNode* processServiceNodeStart(int currenttime, LinkedQueue *pWaitQueue); // 서비스 시작 처리
QueueNode* processServiceNodeEnd(int currenttime, QueueNode *pServiceNode,int *pServiceUserCount,int *ptotal); // 서비스 종료 처리
void displayCustomer(int currenttime, Customer customer); // 고객의 상태 출력
void displayWaitQueueStatus(int currenttime, LinkedQueue *pWaitQueue); // 대기열의 상태를 출력
void printReport(LinkedQueue *pWaitQueue,int serviceUserCount,int total); //최종 시물레이션 결과 출력

4.queuesimulation.cpp

- insertCustomer

void insertCustomer(int _arrivaltime, int _servicetime, LinkedQueue *pQueue) {
	if (pQueue) {
		QueueNode node;
		node.data.status = arrival;
		node.data.arrivaltime = _arrivaltime;
		node.data.servicetime = _servicetime;
		node.data.starttime = 0;
		node.data.endtime = 0;
		enqueueLQ(pQueue, node); //고객 대기 큐에 노드를 인큐
	}
} // 고객 도착 큐에 손님 추가

고객 도착 큐에 고객을 추가하는 함수이다. 고객에 대한 기본적인 정보들을 저장해주고 큐에 인큐 연산을 실행한다.
이 함수를 사용할 때 처음 오는 고객부터 큐에 저장한다고 가정한다.

- processArrival

void processArrival(int currenttime, LinkedQueue* pArrivalQueue, LinkedQueue *pWaitQueue) {
	QueueNode* pArrivalNode = NULL;
	int isEmpty = 0;
	isEmpty = isEmptyLQ(pArrivalQueue);
	while (isEmpty == FALSE) {
		pArrivalNode = peekLQ(pArrivalQueue); // 피크연산을 이용 하여 도착시간과 현재시각 이 같은지 확인 만약 같다면 

		if (pArrivalNode->data.arrivaltime == currenttime) {// 현재 시각이 도착 시각인지 비교
			enqueueLQ(pWaitQueue, *pArrivalNode);
			displayCustomer(currenttime, pArrivalNode->data);
			delete dequeueLQ(pArrivalQueue);
		}
		else { break; }
		isEmpty = isEmptyLQ(pArrivalQueue);
	}
} // 고객 도착 처리

고객 도착 큐에 있는 고객들이 도착했는지 확인한다. 만약 현재 시각이 도착 시각과 일치한다면 해당 고객 노드를 고객 대기 큐에 인큐 연산을 실행하고 고객 도착 큐에서는 디큐 연산을 실행 핸준다.
이때 도착했는지 안했는지 확인할 때는 피크 연산을 이용해 비교한다.

- processServicenodeStart

QueueNode* processServiceNodeStart(int currenttime, LinkedQueue *pWaitQueue) {
	QueueNode* pServiceNode = NULL;
	QueueNode *pReturn = NULL;
	int isEmpty = 0;
	
	isEmpty = isEmptyLQ(pWaitQueue);

	if (isEmpty == FALSE) {
		pServiceNode = dequeueLQ(pWaitQueue);

		if (pServiceNode != NULL) {
			pServiceNode->data.status = start;
			pServiceNode->data.starttime = currenttime;
			displayCustomer(currenttime, pServiceNode->data);

			pReturn = pServiceNode;
		}
	}
	return pReturn;
} // 서비스 시작 처리

서비스 노드가 비어있을 때 다음 고객을 서비스 노드에 넣어주는 함수이다. 고객 대기 큐가 빈 큐가 아니라면 고객 대기 큐에서 디큐 연산 실행 후 그 노드를 pReturn에 저장 후 반환한다.

- processServicenodeEnd

QueueNode* processServiceNodeEnd(int currenttime, QueueNode *pServiceNode, int *pServiceUserCount, int *ptotal) {
	int endtime = 0;
	int waittime = 0;
	QueueNode *pReturn = NULL;

	endtime = pServiceNode->data.starttime + pServiceNode->data.servicetime;
	if (endtime <= currenttime) {
		waittime = pServiceNode->data.starttime - pServiceNode->data.arrivaltime;

		(*pServiceUserCount)++;
		(*ptotal) += waittime;

		pServiceNode->data.status = END;
		pServiceNode->data.endtime = currenttime;
		displayCustomer(currenttime, pServiceNode->data);

		delete pServiceNode;
		pReturn= NULL;
	}
	else {
		pReturn = pServiceNode; // 별다른 행동 하지 않음
	}
	return pReturn;
} // 서비스 종료 처리

서비스 노드의 노드가 현재 시각에서 서비스가 종료되었는지 아닌지 확인하고 만약 종료되었다면 메모리 해제를 해주는 함수이다. 시작 시각과 서비스 시간의 합을 이용해 종료 시각을 구하고 만약 종료시각이라면 전체 대기시간, 처리된 고객 수를 최신화 해준다. 최신화 한 후에는 없어져도 되는 노드이기 때문에 메모리 해제를 진행한다. 만약 아직 서비스가 진행 중이라면 별다른 행동을 하지 않는다.

나머지 함수 구현 코드는 다음과 같다.

별다른 어려움이 없는 출력 함수들은 다음과 같이 구현했다.

void displayCustomer(int currenttime, Customer customer) {
	cout << "[" << currenttime << "]";
	if (customer.status == arrival) {
		cout << "고객 도착" << endl;
	}
	else if (customer.status == start) {
		cout << "서비스 시작, 도착 시간: " << customer.arrivaltime << "  대기 시간: " << customer.starttime - customer.arrivaltime << endl;
	}
	else {
		cout << "서비스 종료, 도착 시간: " << customer.arrivaltime << "  대기 시간: " << customer.starttime - customer.arrivaltime <<
			"  시작 시간 : " << customer.starttime << "  서비스 시간 : " << customer.endtime-customer.starttime << endl;
	}
} // 고객의 상태 출력

void displayWaitQueueStatus(int currenttime,LinkedQueue *pWaitQueue) {
	cout << "[" << currenttime << "]" << "현재 대기 고객 수: " << pWaitQueue->currentSize << endl;
} // 대기열의 상태를 출력

void printReport(LinkedQueue *pWaitQueue, int serviceUserCount, int total) {
	cout << "최종 결과" << endl;
	cout << "서비스 고객 수: " << serviceUserCount << endl;
	if (serviceUserCount > 0) {
		cout << "평균 대기 시간: " << ((float)total / serviceUserCount);
	}
	cout << ",  현재 대기 열의 고객 수: " << pWaitQueue->currentSize << endl;
}//최종 시물레이션 결과 출력

실행결과는 다음과 같다.

728x90

저작자표시 비영리 (새창열림)

'컴퓨터 공학 > 자료구조' 카테고리의 다른 글

C로 만드는 자료구조- 이진 트리의 순회 (0)	2021.01.20
C로 만드는 자료구조- 연결 리스트로 구현한 이진 트리 (0)	2020.09.25
C로 만드는 자료구조- 연결 리스트로 구현한 큐 (0)	2020.09.11
C로 만드는 자료구조-배열로 구현한 큐+(원형 큐) (0)	2020.09.06
C로 만드는 자료구조- Queue란? (0)	2020.09.06