Queue(큐) - 2 [Deque(덱)]

4. 덱(Deque)

 - Double-ended queue의 줄임말로서 큐의 전단과 후단에서 모두 삽입과 삭제가 가능한 큐를 의미한다.

 

 1) 덱 추상 데이터 타입

  - 객체 : n개의 element형의 요소들의 순서 있는 모임

  - 연산 :

• create()
• init(dq)
• is_empty(dq)
• is_full(dq)
• add_front(dq, e) : 덱의 앞에 요소를 추가한다.
• add_rear(dq, e) : 덱의 뒤에 요소를 추가한다.
• delete_front(dq) : 덱의 앞에 있는 요소를 반환한 다음 삭제한다.
• delete_rear(dq) : 덱의 뒤에 있는 요소를 반환한 다음 삭제한다.
• get_front(dq) : 덱의 앞에서 삭제하지 않고 앞에 있는 요소를 반환한다.
• get_rear(dq) : 덱의 뒤에서 삭제하지 않고 앞에 있는 요소를 반환한다.

 

 2) 덱의 구현

  - 덱은 보통 이중 연결 리스트로 구현된다. 그 이유는 전단과 후단에서 모두 삽입, 삭제가 가능해야 하기 때문에 양쪽으로 링크를 가지고 있어야 편리하기 때문이다.

 

#define TRUE 1
#define FALSE 0
typedef int element;		// 요소의 타입

typedef struct DlistNode {	// 노드의 타입
	element data;
	struct DlistNode *llink;
	struct DlistNode *rlink;
} DlistNode;

typedef struct DequeType {	// 덱의 타입
	DlistNode *head;
	DlistNode *tail;
} DequeType;
//
void error(char *message)
{
	fprintf(stderr, "%s\n", message);
	exit(1);
}
//
void init(DequeType *dq)
{
	dq->head = dq->tail = NULL;
}

//
DlistNode *create_node(DlistNode *llink, element item, DlistNode *rlink)
{
	DlistNode *new_node = (DlistNode *)malloc(sizeof(DlistNode));
	if (new_node == NULL)
		error("메모리 할당 오류");
	new_node->llink = llink;
	new_node->data = item;
	new_node->rlink = rlink;
	return new_node;
}
//
int is_empty(DequeType *dq)
{
	if (dq->head == NULL) return TRUE;
	else return FALSE;
}
//
void add_rear(DequeType *dq, element item)
{
	DlistNode *new_node = create_node(dq->tail, item, NULL);

	if (is_empty(dq))
		dq->head = new_node;
	else
		dq->tail->rlink = new_node;
	dq->tail = new_node;
}
//
void add_front(DequeType *dq, element item)
{
	DlistNode *new_node = create_node(NULL, item, dq->head);

	if (is_empty(dq))
		dq->tail = new_node;
	else
		dq->head->llink = new_node;
	dq->head = new_node;
}
//
element delete_front(DequeType *dq)
{
	element item;
	DlistNode *removed_node;

	if (is_empty(dq))  error("공백 덱에서 삭제");
	else {
		removed_node = dq->head;
		item = removed_node->data;
		dq->head = dq->head->rlink;
		free(removed_node);
		if (dq->head == NULL)
			dq->tail = NULL;
		else
			dq->head->llink = NULL;
	}
	return item;
}
//
element delete_rear(DequeType *dq)
{
	element item;
	DlistNode *removed_node;

	if (is_empty(dq))  error("공백 덱에서의 삭제");
	else {
		removed_node = dq->tail;
		item = removed_node->data;
		dq->tail = dq->tail->llink;
		free(removed_node);

		if (dq->tail == NULL)
			dq->head = NULL;
		else
			dq->tail->rlink = NULL;
	}
	return item;
}
//
void display(DequeType *dq)
{
	DlistNode *p;
	printf("( ");
	for (p = dq->head; p != NULL; p = p->rlink) {
		printf("%d ", p->data);
	}
	printf(")\n");
}

void main()
{
	DequeType deque;

	init(&deque);
	add_front(&deque, 10);
	add_front(&deque, 20);
	add_rear(&deque, 30);
	display(&deque);

	delete_front(&deque);
	delete_rear(&deque);
	display(&deque);
}

 

5. 큐의 응용

 - 큐는 서로 다른 속도로 실행되는 두 프로세스 간의 상호 작용을 조화시키는 버퍼 역할을 담당한다.

 - 은행 서비스 시뮬레이션 프로그램

 

/* simulation.c */

#include <stdlib.h>
#include <stdio.h>
#include <math.h>

#define TRUE 1
#define FALSE 0
#define MAX_QUEUE_SIZE 100
typedef struct {
	int id;
	int arrival_time;
	int service_time;
} element;

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

// 초기화 함수
void init(QueueType *q)
{
	q->front = q->rear = 0;
}
// 공백 상태 검출 함수
int is_empty(QueueType *q)
{
	return (q->front == q->rear);
}
// 포화 상태 검출 함수
int is_full(QueueType *q)
{
	return ((q->rear + 1) % MAX_QUEUE_SIZE == q->front);
}
// 삽입 함수
void enqueue(QueueType *q, element item)
{
	if (is_full(q)) {
		fprintf(stderr, "큐가 포화상태입니다.\n");
		return;
	}
	q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
	q->queue[q->rear] = item;
}
// 삭제 함수
element dequeue(QueueType *q)
{
	if (is_empty(q)) {
		fprintf(stderr, "큐가 공백상태입니다.\n");
		exit(1);
	}
	q->front = (q->front + 1) % MAX_QUEUE_SIZE;
	return q->queue[q->front];
}
// [0..1] 사이의 난수 생성 함수
double random()
{
	return rand() / (double)RAND_MAX;
}

// 시뮬레이션에 필요한 여러가지 상태 변수
int duration = 10; // 시물레이션 시간 
double arrival_prob = 0.7; // 하나의 시간 단위에 도착하는 평균 고객의 수
int max_serv_time = 5; // 하나의 고객에 대한 최대 서비스 시간
int clock;

// 시뮬레이션의 결과
int customers;			// 전체고객수
int served_customers;	// 서비스받은 고객수
int waited_time;	// 고객들이 기다린 시간

					// 랜덤 숫자를 생성하여 고객이 도착했는지 도착하지 않았는지를 판단
int is_customer_arrived()
{
	if (random() < arrival_prob)
		return TRUE;
	else return FALSE;
}
// 새로 도착한 고객을 큐에 삽입
void insert_customer(int arrival_time)
{
	element customer;

	customer.id = customers++;
	customer.arrival_time = arrival_time;
	customer.service_time = (int)(max_serv_time * random()) + 1;
	enqueue(&queue, customer);
	printf("고객 %d이 %d분에 들어옵니다. 서비스시간은 %d분입니다.\n",
		customer.id, customer.arrival_time, customer.service_time);
}
// 큐에서 기다리는 고객을 꺼내어 고객의 서비스 시간을 반환한다.
int remove_customer()
{
	element customer;
	int service_time = 0;

	if (is_empty(&queue)) return 0;
	customer = dequeue(&queue);
	service_time = customer.service_time - 1;
	served_customers++;
	waited_time += clock - customer.arrival_time;
	printf("고객 %d이 %d분에 서비스를 시작합니다. 대기시간은 %d분이었습니다.\n",
		customer.id, clock, clock - customer.arrival_time);
	return service_time;
}
// 통계치를 출력한다.
void print_stat()
{
	printf("서비스받은 고객수 = %d\n", served_customers);
	printf("전체 대기 시간 = %d분\n", waited_time);
	printf("1인당 평군 대기 시간 = %f분\n", (double)waited_time / served_customers);
	printf("아직 대기중인 고객수 = %d\n", customers - served_customers);
}
// 시뮬레이션 프로그램
void main()
{
	int service_time = 0;

	clock = 0;
	while (clock < duration) {
		clock++;
		printf("현재시각=%d\n", clock);
		if (is_customer_arrived()) {
			insert_customer(clock);
		}
		if (service_time > 0)
			service_time--;
		else {
			service_time = remove_customer();
		}
	}
	print_stat();
}

 

 

[Reference]

• 천인국, 공용해, 하상호, 「C언어로 쉽게 풀어쓴 자료구조」, 생능출판, 2009년