[C언어로 쉽게 풀어쓴 자료구조] Chapter5. 큐 (2)

5.5 덱이란?

 

● 덱:  deque(Double-ended queue)는 이름 줄임말처럼, 큐의 front와 rear에서 모두 삽입, 삭제가 가능한 큐이다.

*여전히 중간에 삽입하거나 삭제하는 것은 허용하지 않는다.

 

add_front, delete_front ->  스택의 push, pop

add_rear, delete_front -> 큐의 enqueue, dequeue

delete_rear -> 덱만 가지는 연산

 

원형큐 코드에 delete_rear, add_front, get_rear 연산을 추가하면 된다.

*add_rear는 enqueue, delete_front는 dequeue, get_front는 peek연산과 동일하다.

 

add_front와 delete_rear는 각각 배열의 앞과 뒤에서 인덱스를 -1씩 이동해야 하므로

front <- (front-1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
rear <- (rear-1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;

와 같이 변경된다. 원형큐를 만들기 위해 MAX_QUEUE_SIZE를 더 해준 뒤 나머지 연산을 수행한다.

#include <stdio.h>
#include <stdlib.h>
#define MAX_QUEUE_SIZE 5

typedef int element;
typedef struct{
	element data[MAX_QUEUE_SIZE];
	int front;
	int rear;
}DequeType;

void error(char *message){
	fprintf(stderr,"%s\n",message);
	exit(1);
}

int is_empty(DequeType *q){
	if(q->front == q->rear) return 1;
	else return 0;
}


void init_deque(DequeType *q){
	q->front = q->rear = 0;
}


int is_full(DequeType *q){
	if((q->rear +1)%MAX_QUEUE_SIZE == q->front) return 1;
	else return 0;
}

void add_rear(DequeType *q,element item){
	if(is_full(q)){
		error("큐가 가득 참");
		exit(1);
	}
	q->rear = (q->rear +1) % MAX_QUEUE_SIZE;
	q->data[q->rear] = item;
}

element delete_front(DequeType *q){
	if(is_empty(q)){
		error("큐가 빔");
		return -1;
	}
	q->front = (q->front +1) % MAX_QUEUE_SIZE;
	element item = q->data[(q->front)];	
	return item;
}

void add_front(DequeType *q,element item){
	if(is_full(q)){
		error("큐가 가득 참");
		exit(1);
	}
	q->data[q->front] = item;
	//front는 맨 앞 요소의 바로 앞을 가리키므로
	//front에 item을 넣은 후 인덱스를 조정해주는 것이 옳다.
	q->front = (q->front -1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
}

element delete_rear(DequeType *q){
	if(is_empty(q)){
		error("큐가 빔");
		return -1;
	}
	int prev = q->rear;
	// 꺼낼 데이터의 인덱스를 prev에 저장
	q->rear = (q->rear -1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
	return q->data[prev];
}


void deque_print(DequeType *q){
	printf("Deque(front=%d rear=%d) = ", q->front,q->rear);
	if(!is_empty(q)){
		int i= q->front;
		do{
			i=(i+1)%MAX_QUEUE_SIZE;
			printf("%d | ",q->data[i]);
			if(i==q->rear) break;
		}while(i != q->front);
	}
	printf("\n");
}


int main(){
	DequeType q;
	init_deque(&q);
	for(int i=0; i<3;i++){
		add_front(&q,i);
		deque_print(&q);
	}
	for(int i=0; i<3;i++){
		delete_rear(&q);
		deque_print(&q);
	}
	return 0;
}

add_front와 delete_rear에 적어놓은 각주를 잘 인지하여야 한다.

 

♠ 167p Quiz

01 enqueue 대신에 add_rear, dequeue 대신에 delete_front을 사용한다.

02 push 대신에 add_front, pop 대신에 delete_front을 사용한다.

 

 

5.6 큐의 응용: 시뮬레이션

큐는 주로 큐잉이론(대기행렬이론)에 따라 시스템의 특성을 시뮬레이션하여 분석하는 데 이용된다.

큐잉모델은 고객에 대한 서비스를 수행하는 서버와 서비스를 받는 고객들로 이루어진다.

제한된 수의 서버 때문에 고객들은 대기 행렬에서 기다리게 되고, 이 기다리는 시간을 줄이는 것이 목표이다.

해당 예제에선 다른 특성 요인들을 배제하고 랜덤한 간격으로 고객이 큐에 들어오고, 랜덤한 서비스 시간을

소요한 뒤 큐에서 빠져나간다. 

다음의 반복 루프로 시뮬레이션이 이루어진다.

170p의 도전문제처럼 종업원이 a와 b 두 명이 있는 예제를 풀어보았다.

1. 현재 시각을 나타내는 clock이라는 변수를 하나 증가
2. [0,10] 사이의 난수를 생성하여 3보다 작으면 새로운 고객이 들어왔다고 판단. 
3. 새로운 고객이 들어오면 고객의 아이디, 도착시간, 랜덤한 서비스 이용시간을 담은 구조체 생성 후 enqueue
4. 전역 변수인 service_time_a와 service_time_b에 현재 처리중인 고객의 서비스 시간을 저장
5. service_time_a랑 service_time이 0이 아니라면 각 직원은 다른 고객을 대응 중임을 의미
6. clock이 하나 증가하면 service_time을 하나씩 감소.
7. service_time_x가 0이라면 큐에서 dequeue하여 직원x에게 고객을 대응시킨다.

* servic_time_x가 0보다 큰 지 검사할 때랑 0인지 검사할 때는 if와 else if를 같은 단계에 걸어서

하나만 검사하고 코드를 넘어가는 일이 없도록한다.

 

   8. 60분 동안 루프를 돌린 후 고객들이 총 기다린 시간을 전부 합하여 화면에 출력

 

#include <stdio.h>
#include <stdlib.h>
#define MAX_QUEUE_SIZE 5

typedef struct{
	int id;
	int arrival_time;
	int service_time;
}element;

typedef struct{
	element data[MAX_QUEUE_SIZE];
	int front;
	int rear;
}QueueType;

void error(char *message){
	fprintf(stderr,"%s\n",message);
	exit(1);
}

int is_empty(QueueType *q){
	if(q->front == q->rear) return 1;
	else return 0;
}


void init_queue(QueueType *q){
	q->front = q->rear = 0;
}


int is_full(QueueType *q){
	if((q->rear +1)%MAX_QUEUE_SIZE == q->front) return 1;
	else return 0;
}

void enqueue(QueueType *q,element item){
	if(is_full(q)){
		error("큐가 가득 참");
		exit(1);
	}
	q->rear = (q->rear +1) % MAX_QUEUE_SIZE;
	q->data[q->rear] = item;
}

element dequeue(QueueType *q){
	if(is_empty(q)){
		error("큐가 빔");
		exit(1);
	}
	q->front = (q->front +1) % MAX_QUEUE_SIZE;
	element item = q->data[(q->front)];	
	return item;
}

void queue_print(QueueType *q){
	printf("QUEUE(front=%d rear=%d) = ", q->front,q->rear);
	if(!is_empty(q)){
		int i= q->front;
		do{
			i=(i+1)%MAX_QUEUE_SIZE;
			printf("%d | ",q->data[i]);
			if(i==q->rear) break;
		}while(i != q->front);
	}
	printf("\n");
}




int main(){
	int minutes =60;
	int total_wait =0;
	int total_customers =0;
	int service_time_a = 0; // 종업원 a의 서비스 시간
	int service_time_b = 0; // 종업원 b의 서비스 시간
	int service_customer;
	QueueType q;
	QueueType q2;
	init_queue(&q);
	init_queue(&q2);
	
	srand(time(NULL));
	for(int clock=0; clock<minutes; clock++){
		printf("현재 시각= %d\n",clock);
		if((rand()%10)<3){ //고객이 들어올 확률 33.33%
			element customer;
			customer.id=total_customers++; // 온 순서에 따라 id부여
			customer.arrival_time=clock; // 도착시간
			customer.service_time=rand()%7 +1; // 손님의 서비스 이용시간도 랜덤
			enqueue(&q,customer);
			printf("고객 %d이 %d분에 들어옵니다. 업무처리시간= %d분\n",
				  customer.id,customer.arrival_time,customer.service_time);
		}
		if(service_time_a>0){
			service_time_a--;
		}
		if(service_time_b>0){ //else if로 처리하면 a만 감소
			service_time_b--;
		}
		if(!is_empty(&q)){
			if(service_time_a>0 && service_time_b>0){
				printf("대기가 필요합니다\n");
			}
			else if(service_time_a==0){
				element customer = dequeue(&q);
				service_customer = customer.id;
				service_time_a = customer.service_time;
				printf("고객 %d이 %d분에 직원a에게 업무를 시작합니다. 대기시간은 %d분이었습니다.\n",
					  customer.id,clock,clock-customer.arrival_time);
				total_wait += clock - customer.arrival_time;
			}
			else if(service_time_b==0){
				element customer = dequeue(&q);
				service_customer = customer.id;
				service_time_b = customer.service_time;
				printf("고객 %d이 %d분에 직원b에게 업무를 시작합니다. 대기시간은 %d분이었습니다.\n",
					  customer.id,clock,clock-customer.arrival_time);
				total_wait += clock - customer.arrival_time;
			}
		}	
	}	
	printf("전체 대기 시간 = %d분 \n",total_wait);
	return 0;
}