반응형
큐 추상 데이터 타입
선입선출(FIFO: First-In First-Out)
큐 초기화 init(q)
비었나? in_empty(q)
가득 찼나? is_full(q)
q에 끝에 e를 추가 enqueue(q, e)
q의 맨 앞에 있는 e를 제거하여 반환 dequeue(q)
q의 맨 앞에 있는 e를 읽어서 반환 peek(q)
선형큐
#include <stdio.h>
#include <stdlib.h>
#define MAX_QUEUE_SIZE 5
typedef int element;
typedef struct { // 큐 타입
int front;
int rear;
element data[MAX_QUEUE_SIZE];
} QueueType;
// 오류 함수
void error(char *message)
{
fprintf(stderr, "%s\n", message);
exit(1);
}
void init_queue(QueueType *q)
{
q->rear = -1;
q->front = -1;
}
void queue_print(QueueType *q)
{
for (int i = 0; i<MAX_QUEUE_SIZE; i++) {
if (i <= q->front || i> q->rear)
printf(" | ");
else
printf("%d | ", q->data[i]);
}
printf("\n");
}
int is_full(QueueType *q)
{
if (q->rear == MAX_QUEUE_SIZE - 1)
return 1;
else
return 0;
}
int is_empty(QueueType *q)
{
if (q->front == q->rear)
return 1;
else
return 0;
}
void enqueue(QueueType *q, int item)
{
if (is_full(q)) {
error("큐가 포화상태입니다.");
return;
}
q->data[++(q->rear)] = item;
}
int dequeue(QueueType *q)
{
if (is_empty(q)) {
error("큐가 공백상태입니다.");
return -1;
}
int item = q->data[++(q->front)];
return item;
}
int main(void)
{
int item = 0;
QueueType q;
init_queue(&q);
enqueue(&q, 10); queue_print(&q);
enqueue(&q, 20); queue_print(&q);
enqueue(&q, 30); queue_print(&q);
item = dequeue(&q); queue_print(&q);
item = dequeue(&q); queue_print(&q);
item = dequeue(&q); queue_print(&q);
return 0;
}실행결과
원형큐
원형큐에서는 하나의 자리는 항상 비워둔다 왜냐하면, 포화상태와 공백 상태를 구별하기 위해서이다. 만약 한 자리를 비워두지 않는다면 포화 상태와 공백 상태를 구분할 수 없을 것이다. front==rear이면 공백 상태가 되고 front가 rear 보다 하나 앞에 있으면 포화상태가 된다.
#include <stdio.h>
#include <stdlib.h>
// ===== 원형큐 코드 시작 ======
#define MAX_QUEUE_SIZE 5
typedef int element;
typedef struct { // 큐 타입
element data[MAX_QUEUE_SIZE];
int front, rear;
} QueueType;
// 오류 함수
void error(char *message)
{
fprintf(stderr, "%s\n", message);
exit(1);
}
// 공백 상태 검출 함수
void init_queue(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 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");
}
// 삽입 함수
void enqueue(QueueType *q, element item)
{
if (is_full(q))
error("큐가 포화상태입니다");
q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
q->data[q->rear] = item;
}
// 삭제 함수
element dequeue(QueueType *q)
{
if (is_empty(q))
error("큐가 공백상태입니다");
q->front = (q->front + 1) % MAX_QUEUE_SIZE;
return q->data[q->front];
}
// 삭제 함수
element peek(QueueType *q)
{
if (is_empty(q))
error("큐가 공백상태입니다");
return q->data[(q->front + 1) % MAX_QUEUE_SIZE];
}
// ===== 원형큐 코드 끝 ======
int main(void)
{
QueueType queue;
int element;
init_queue(&queue);
printf("--데이터 추가 단계--\n");
while (!is_full(&queue))
{
printf("정수를 입력하시오: ");
scanf("%d", &element);
enqueue(&queue, element);
queue_print(&queue);
}
printf("큐는 포화상태입니다.\n\n");
printf("--데이터 삭제 단계--\n");
while (!is_empty(&queue))
{
element = dequeue(&queue);
printf("꺼내진 정수: %d \n", element);
queue_print(&queue);
}
printf("큐는 공백상태입니다.\n");
return 0;
}실행결과
큐의 응용: 버퍼
큐에 일정한 비율(20%)로 난수를 생성하여 큐에 입력하고, 일정한 비율(10%)로 큐에서 정수를 꺼내는 프로그램을 작성해 보자. 생산자가 소비자보다 빠르므로 큐가 포화 상태가 될 가능성이 높아진다.
#include <stdio.h>
#include <stdlib.h>
// ===== 원형큐 코드 시작 ======
#define MAX_QUEUE_SIZE 5
typedef int element;
typedef struct { // 큐 타입
element data[MAX_QUEUE_SIZE];
int front, rear;
} QueueType;
// 오류 함수
void error(char *message)
{
fprintf(stderr, "%s\n", message);
exit(1);
}
// 공백 상태 검출 함수
void init_queue(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 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");
}
// 삽입 함수
void enqueue(QueueType *q, element item)
{
if (is_full(q))
error("큐가 포화상태입니다");
q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
q->data[q->rear] = item;
}
// 삭제 함수
element dequeue(QueueType *q)
{
if (is_empty(q))
error("큐가 공백상태입니다");
q->front = (q->front + 1) % MAX_QUEUE_SIZE;
return q->data[q->front];
}
// 삭제 함수
element peek(QueueType *q)
{
if (is_empty(q))
error("큐가 공백상태입니다");
return q->data[(q->front + 1) % MAX_QUEUE_SIZE];
}
// ===== 원형큐 코드 끝 ======
int main(void)
{
QueueType queue;
int element;
init_queue(&queue);
srand(time(NULL));
for(int i=0;i<100; i++){
if (rand() % 5 == 0) { // 5로 나누어 떨어지면
enqueue(&queue, rand()%100);
}
queue_print(&queue);
if (rand() % 10 == 0) { // 10로 나누어 떨어지면
int data = dequeue(&queue);
}
queue_print(&queue);
}
return 0;
}실행결과
덱이란?
덱(deque)은 double-ended queue의 줄임말로서 큐의 전단(front)과 후단(rear)에서 모두 삽입과 삭제가 가능한 큐를 의미한다. 그렇지만 여전히 중간에 삽입하거나 삭제하는 것은 허용하지 않는다.
원형 덱 프로그램
#include <stdio.h>
#include <stdlib.h>
#define MAX_QUEUE_SIZE 5
typedef int element;
typedef struct { // 큐 타입
element data[MAX_QUEUE_SIZE];
int front, rear;
} DequeType;
// 오류 함수
void error(char *message)
{
fprintf(stderr, "%s\n", message);
exit(1);
}
// 초기화
void init_deque(DequeType *q)
{
q->front = q->rear = 0;
}
// 공백 상태 검출 함수
int is_empty(DequeType *q)
{
return (q->front == q->rear);
}
// 포화 상태 검출 함수
int is_full(DequeType *q)
{
return ((q->rear + 1) % MAX_QUEUE_SIZE == q->front);
}
// 원형큐 출력 함수
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");
}
// 삽입 함수
void add_rear(DequeType *q, element item)
{
if (is_full(q))
error("큐가 포화상태입니다");
q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
q->data[q->rear] = item;
}
// 삭제 함수
element delete_front(DequeType *q)
{
if (is_empty(q))
error("큐가 공백상태입니다");
q->front = (q->front + 1) % MAX_QUEUE_SIZE;
return q->data[q->front];
}
// 삭제 함수
element get_front(DequeType *q)
{
if (is_empty(q))
error("큐가 공백상태입니다");
return q->data[(q->front + 1) % MAX_QUEUE_SIZE];
}
void add_front(DequeType *q, element val)
{
if (is_full(q))
error("큐가 포화상태입니다");
q->data[q->front] = val;
q->front = (q->front - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
}
element delete_rear(DequeType *q)
{
int prev = q->rear;
if (is_empty(q))
error("큐가 공백상태입니다");
q->rear = (q->rear - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
return q->data[prev];
}
element get_rear(DequeType *q)
{
if (is_empty(q))
error("큐가 공백상태입니다");
return q->data[q->rear];
}
int main(void)
{
DequeType queue;
init_deque(&queue);
for (int i = 0; i < 3; i++) {
add_front(&queue, i);
deque_print(&queue);
}
for (int i = 0; i < 3; i++) {
delete_rear(&queue);
deque_print(&queue);
}
return 0;
}실행결과
큐의 응용: 시뮬레이션
1. 먼저 현재시각을 나타내는 clock이라는 변수를 하나 증가한다.
2. [0,10] 사이의 난수를 생성하여 3보다 작으면 새로운 고객이 들어왔다고 판단한다. 새로운 고객이 들어오면 구조체를 생성하고 여기에 고객의 아이디, 도착시간, 서비스 시간 등 의 정보를 복사한다. 여기서 고객이 필요로 하는 서비스 시간도 역시 난수로 생성한다. 이 구조체를 enqueue()를 호출하여서 큐에 추가한다. 전역 변수인 service_time에 현재 처리 중인 고객의 서비스 시간을 저장해 둔다.
3. service_time이 0인지 아닌지를 살펴본다. 만약 service_time이 0이 아니면 어떤 고객이 지금 서비스를 받고 있는 중임을 의미한다. clock이 하나 증가했으므로 service_time을 하나 감소시킨다. 만약 service_time이 0이면 현재 서비스받는 고객이 없다는 것을 의미한다. 따라서 큐에서 고객 구조체를 하나 꺼내어 서비스를 시작한다. 즉 서비스를 시작한다는 의미는 전역 변수 service_time에 고객의 서비스 시간을 저장한다는 것이다. 보다 복잡한 처리를 시뮬레이션하려면 코드를 추가해야 한다.
4. 60분의 시간이 지나면 고객들이 기다린 시간을 전부 합하여 화면에 출력한다.
# include <stdio.h>
# include <stdlib.h>
// 프로그램 5.2에서 다음과 같은 부분을 복사한다.
// ================ 원형큐 코드 시작 =================
typedef struct { // 요소 타입
int id;
int arrival_time;
int service_time;
} element; // 교체!
// ================ 원형큐 코드 종료 =================
// ===== 원형큐 코드 시작 ======
#define MAX_QUEUE_SIZE 5
typedef struct { // 큐 타입
element data[MAX_QUEUE_SIZE];
int front, rear;
} QueueType;
// 오류 함수
void error(char *message)
{
fprintf(stderr, "%s\n", message);
exit(1);
}
// 공백 상태 검출 함수
void init_queue(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 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");
}
// 삽입 함수
void enqueue(QueueType *q, element item)
{
if (is_full(q))
error("큐가 포화상태입니다");
q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
q->data[q->rear] = item;
}
// 삭제 함수
element dequeue(QueueType *q)
{
if (is_empty(q))
error("큐가 공백상태입니다");
q->front = (q->front + 1) % MAX_QUEUE_SIZE;
return q->data[q->front];
}
// 삭제 함수
element peek(QueueType *q)
{
if (is_empty(q))
error("큐가 공백상태입니다");
return q->data[(q->front + 1) % MAX_QUEUE_SIZE];
}
// ===== 원형큐 코드 끝 ======
int main(void)
{
int minutes = 60;
int total_wait = 0;
int total_customers = 0;
int service_time = 0;
int service_customer;
QueueType queue;
init_queue(&queue);
srand(time(NULL));
for (int clock = 0; clock < minutes; clock++) {
printf("현재시각=%d\n", clock);
if ((rand()%10) < 3) {
element customer;
customer.id = total_customers++;
customer.arrival_time = clock;
customer.service_time = rand() % 3+1;
enqueue(&queue, customer);
printf("고객 %d이 %d분에 들어옵니다. 업무처리시간= %d분\n",
customer.id, customer.arrival_time, customer.service_time);
}
if (service_time > 0) {
printf("고객 %d 업무처리중입니다. \n", service_customer);
service_time--;
}
else {
if (!is_empty(&queue)) {
element customer = dequeue(&queue);
service_customer = customer.id;
service_time = customer.service_time;
printf("고객 %d이 %d분에 업무를 시작합니다. 대기시간은 %d분이었습니다.\n",
customer.id, clock, clock - customer.arrival_time);
total_wait += clock - customer.arrival_time;
}
}
}
printf("전체 대기 시간=%d분 \n", total_wait);
return 0;
}이건 직접 복붙하여 실행 해 보길 바란다...
관심이 있으신 분들에게 유용한 정보였길 바라며
다음은 5장 연습문제 해설을 가져오도록 하겠습니다.
반응형