Chapter 05 큐
1. 큐(Queue)
① 큐란?
삽입은 맨 뒤에서 진행되고 삭제는 맨 앞에서 진행되는 것이 큐
큐: 먼저 들어온 데이터가 먼저 나가는 자료구조
- 선입선출(FIFO: First-In First-Out)
- (예) 매표소의 대기열
자료구조에서 가장 중요한 것(핵심)은 삽입&삭제
② 큐ADT
객체: 0개 이상의 요소들로 구성된 선형 리스트
연산은 다음과 같다.
create(max_size) :: = 최대 크기가 max_size인 공백큐를 생성한다.
init(q) ::= 큐를 초기화한다.
is_empty(q) ::= if(size == 0) return TRUE;
else return FALSE;
is_full(q) ::= if (size == max_size) return TRUE; (enqueue에 대한 보조연산이라 할 수 있다.)
else return FALSE;
enqueue(q, e) ::= if(is_full(q)) queue_full 오류;
else q의 끝에 e를 추가한다.
dequeue(q) ::= if(is_empty(q)) queue_empty 오류;
else q의 맨 앞에 있는 e를 제거하여 반환한다.
peek(q) ::= if( is_empty(q) ) queue_empty 오류;
else q의 맨 앞에 있는 e를 읽어서 반환한다.
선형이란 것은 한 줄로 나열되어 순서가 있는 것이다. 앞, 뒤가 있는 리스트 그것을 선형 리스트라고 한다. 선형리스트는 순서가 있는 데이터의 집합이라고 생각하면 된다.
③ 큐의 응용
직접적인 응용
- 시뮬레이션의 대기열(공항에서의 비행기들, 은행에서의 대기열)
실제로 일어나진 않았지만 모의실험을 하는 것을 시뮬레이션이라고 한다. 일상에서 모든 것을 순서대로 실행되는 경우가 많지 않다. 온 순서대로 처리하는 것을 큐를 이용할 수 있다. (ex 은행)
- 통신에서의 데이터 패킷들의 모델링에 이용
- 프린터와 컴퓨터 사이의 버퍼링
간접적인 응용
- 스택과 마찬가지로 프로그래머의 도구
- 많은 알고리즘에서 사용됨
2. 선형 큐
① 선형 큐란?
배열을 선형으로 사용하여 큐를 구현
- 삽입을 계속하기 위해서는 요소들을 이동시켜야 함
큐를 create 한다는 것은 배열을 선언하는 것이다.
구현할 때는 front가 실제보다 하나 앞을 가리키도록 할 것이다. 그러면 프로그램이 간단해지기 때문이다.
0. 초기 상태에서는 front와 rear가 -1
1. 새로운 데이터가 삽입되면 rear가 바뀐다.
2. 기존의 데이터가 삭제되면 front가 바뀐다.
3. (예외) 비어있는 q에 처음으로 데이터가 들어가면 front도 바뀌어야 한다.
4. 마찬가지로 1명 줄 서 있는데 삭제되면 rear도 바뀌어야 한다. 그런데 front가 하나 앞을 가리키므로 그럴 일이 없다.
결과적으로, 삽입이 일어나면 rear가 바뀌고 삭제가 일어나면 front가 바뀐다.
선형 큐의 응용으로는 작업 스케줄링이 있다.
② 선형 큐의 구현
표현: 한 개의 배열과 2개의 인덱스(front, rear)
typedef struct{
int front, rear;
element data[MAX_QUEUE_SIZE];
} QueueType;
#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)]; // int가 아니고 q에 들어가는 데이터를 element로 하기로 했다. 이거는 q에 들어가는 데이터가 int만 들어가기로 하는 것, int가 아니라 element가 맞다.
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;
}
<실행결과>
10 | | | | |
10 | 20 | | | |
10 | 20 | 30 | | |
| 20 | 30 | | |
| | 30 | | |
| | | | |
enqueue, inqueue는 반드시 주소 값이 바뀌어야 한다. 그런데 is_full은 굳이 주소 값을 받을 필요는 없다.
ex) init.queue(&q); enqueue(&q, 10);
enqueue 선언
- enqueue는 is_full 검사 후, 사용 가능 (가득차면 쓸 수 없다.)
enqueue(q, item)
1. q의 rear를 1증가시킨다.
2. q의 배열(data)의 rear위치에 item을 삽입한다.
void enqueue(QueueType *q, element item){
(q -> rear)++;
q -> data[q->rear] = item; // 두줄로 쓴 경우
// 한 줄로 쓴 경우 : q->data[++(q->rear)] = item;
선형 큐는 배열을 통해 단순하게 일직선으로 구현하므로 구현이 매우 단순하고 쉽지만 치명적인 약점이 있다.
1) 큐에 데이터가 꽉 찼다면 데이터를 더 추가할 수 없다. (물론 큐 사이즈를 늘리고 원소를 다시 복사하면 된다. 근데 시간이 할애된다.).
2) 공간의 효율성을 고려해야 한다. 배열로 단순히 구현하면 front가 뒤로 계속 밀려 앞의 공간이 남게 된다. 따라서 하나의 원소가 빠져나가면 그 다음부터 모든 원소들을 앞으로 당겨와야 하므로 속도 측면에서 상당히 느린 것이 된다. 작은 데이터들의 경우 상관없지만, 최근 동향은 사이즈가 크고 많은 데이터를 처리하기에, 이와 같은 경우 무리가 있다. 결론적으로, 사용하기에는 그 단점이 불편하므로 원형 큐를 많이 사용한다.
#define MAX_QUEUE_SIZE 5는 전처리기 지시문이다. 이 지시문은 MAX_QUEUE_SIZE라는 이름을 5라는 값으로 정의한다. 이 지시문은 코드에서 MAX_QUEUE_SIZE라는 이름을 사용할 때마다 전처리기가 이를 5로 대체한다. 따라서 코드에서 MAX_QUEUE_SIZE를 사용하는 부분은 모두 5로 대체되어 컴파일 된다.
이러한 방식으로 상수를 정의하는 이유는 코드의 가독성과 유지보수성을 높이기 위해서이다. 예를 들어, 큐의 최대 크기를 나타내는 상수를 MAX_QUEUE_SIZE로 정의하면 코드에서 이 상수를 사용할 때 큐의 최대 크기가 얼마인지 쉽게 알 수 있다. 또한 큐의 최대 크기를 변경해야 할 경우에는 #define MAX_QUEUE_SIZE 5라는 한 줄만 변경하면 되므로 유지보수가 용이하다.
enqueue(q, item)
1. rear를 1증가
2. data[rear] = item
dequeue(q)
1. front를 1증가
2. data[front]를 return
full (rear값이 배열의 크기 n-1번째 인덱스, front는 -1)
empty (rear와 front 모두 -1, front와 rear 값이 같은 것)
선형 큐는 앞에 빈칸이 있음에도 불구하고 끝에 차 있으므로 더 들어가지 못하는 문제점이 있다. 물론, 삭제가 일어날 때마다 뒤의 데이터를 한 칸씩 앞으로 이동하면 된다. 그러나 그때마다 하나씩 이동을 하는 것은 굉장히 비효율적이다. 따라서 원형 큐를 사용한다. [4]의 뒤가 [0]이라고 생각하는 것, 계속 이어서 삽입이 가능해진다.
3. 원형 큐(Circular Queue)
① 원형 큐란?
선형 큐와 같은 front와 rear가 존재하지만 원형 큐에서의 front와 rear는 배열의 끝에 도달하면 다시 배열의 처음을 가리키는 개념이다. 실제로 큐의 끝과 끝이 연결되는 것이 아니라 인덱스를 이용하여 순환을 구현한 것이다.
원형 큐의 공백상태: front와 rear가 같을 때
원형 큐의 포화상태: front가 rear보다 하나 앞에 있을 때 (포화상태일때 한 칸은 비워져 있어야 함.)
큐는 선입선출(FIFO) 구조로 먼저 들어간 값이 가장 먼저 나온다는 뜻이다.
원형 큐는 일반 큐와 다르게 큐는 배열을 지정하고 쓰면 앞부분이 계속 빈다. 그 비는 부분을 사용하기 위해서 처음부터 다시 큐를 채우는 것을 원형 큐라고 한다.
원형 큐의 구조
- 큐의 전단과 후단을 관리하기 위한 2개의 변수 필요
- front: 첫 번째 요소 하나 앞의 인덱스
- rear: 마지막 요소의 인덱스
원형 큐의 동작
- front, rear를 0으로 초기화
- 원소 삽입/삭제시, rear를 시계방향으로 증가시키고, 그 위치에 항목을 삽입하거나 삭제
- rear <- (rear + 1) mod n
- front <- (front + 1) mod n
공백상태: front == rear
포화상태: front % M==(rear+1) % M
공백상태와 포화상태를 구별하기 위하여 하나의 공간은 항상 비워 둔다.
배열의 크기가 8이면 7개까지만 집어넣고 그 이상 채워 넣지 않겠다는 것이다. 그렇게 해서 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);
}
// 공백 상태 검출 함수 (값을 0으로 초기화)
void init_queue(QueueType* q)
{
q->front = q->rear = 0;
}
// 공백 상태 검출 함수 (읽어오기만 하는 것)
int is_empty(QueueType* q)
{
return (q->front == q->rear);
}
// 포화 상태 검출 함수 (front = 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];
}
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;
}
[문제]
원형 큐에서 front와 rear가 가리키는 것은 무엇인가?
front 맨 앞의 하나 앞, rear은 맨 뒤의 값
front: 큐에서 가장 앞쪽의 요소를 가리키는 포인터
rear: 큐에서 가장 뒤쪽의 요소 다음을 가리키는 포인터
3. 큐의 응용
① 큐의 응용
Q. 큐는 어디에 사용될까?
A. 큐는 서로 다른 속도로 실행되는 두 프로세스 간의 상호작용을 조화시키는 버퍼 역할 을 담당한다. ex) CPU와 프린터 사이의 프린팅 버퍼, 또는 CPU와 키보드 사이의 키보드 버퍼 등이 이에 해당한다.
Q. 큐의 대표적인 응용 분야는?
A. 생성자-소비자 프로세스: 큐를 버퍼로 사용한다.
B. 교통 관리 시스템: 컴퓨터로 제어되는 신호등에서는 신호등을 순차적으로 제어하는데 원형 큐가 사용된다.
C. CPU: 스케줄링: 운영체제는 실행 가능한 프로세스들을 저장하거나 이벤트를 기다리는 프로세스들을 저장하기 위하여 몇 개의 큐를 사용한다.
② 버퍼(Buffer)
버퍼(Buffer)란 임시 저장 공간으로, 두 장치가 서로 입출력을 수행할 때 속도차이를 극복하기 위해 사용한다.
(ex. 스트리밍 사이트에서 동영상을 볼 때 서버로부터 동영상을 받는 부분 앞으로 다운로드가 남은 부분이 버퍼)
③ 은행 시뮬레이션
큐잉 모델은 고객에 대한 서비스를 수행하는 서버와 서비스를 받는 고객들로 이루어진다.
은행에서 고객이 들어와서 서비스를 받고 나가는 과정을 시뮬레이션
- 고객들이 기다리는 평균시간을 계산
- 고객은 랜덤한 간격으로 도착
- 고객 서비스 시간을 랜덤하게 결정
큐 데이터 원소를 고객 정보 구조체로 생성하고 큐 함수들을 가져다가 main함수만 바꿔주면 된다.
ⅰ. 주어진 시간동안 고객은 랜덤한 간격으로 큐에 들어온다.
ⅱ. 고객들의 서비스 시간도 한계값 안에서 랜덤하게 결정된다.
ⅲ. 한 고객의 서비스가 끝나면 큐의 맨 앞에 있는 다른 고객이 서비스를 받기 시작한다.
ⅳ. 정해진 시간동안의 시뮬레이션이 끝나면 고객들의 전체대기시간을 계산하여 출력한다.
# include <stdio.h>
# include <stdlib.h>
// ================ 원형큐 코드 시작 =================
typedef int element;
typedef struct { // 요소 타입
int id;
int arrival_time;
int service_time;
} element; // 교체!
// ...
// ================ 원형큐 코드 종료 =================
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;
}
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;
}
<실행결과>
현재시각 = 0
현재시각 = 1
고객 0이 1분에 들어옵니다.업무처리시간 = 2분
고객 0이 1분에 업무를 시작합니다.대기시간은 0분이었습니다.
현재시각 = 2
고객 0 업무처리중입니다.
현재시각 = 3
고객 1이 3분에 들어옵니다.업무처리시간 = 1분
고객 0 업무처리중입니다.
현재시각 = 4
고객 1이 4분에 업무를 시작합니다.대기시간은 1분이었습니다.
현재시각 = 5
고객 1 업무처리중입니다.
현재시각 = 6
고객 2이 6분에 들어옵니다.업무처리시간 = 2분
4. 덱(deque)
① 덱이란?
- 덱은 double-ended queue의 줄임말로서 큐의 전단(front)와 후단(rear)에서 모두 삽입과 삭제가 가능한 큐
- 삽입이 앞과 뒤 모두에서 일어날 수 있다.
② 덱 ADT
덱(deque, double-ended queue)은 양쪽 끝에서 삽입과 삭제가 가능한 자료 구조
객체: 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(q): 덱의 앞에서 삭제하지 않고 앞에 있는 요소를 반환한다.
get_rear(q): 덱의 뒤에서 삭제하지 않고 뒤에 있는 요소를 반환한다.
③ 배열을 이용한 덱의 구현
delete_rear
1. item <- data[rear]
2. rear <- (rear – 1)%MAX
3. return item
add_front
1. data[front] <- item //현재 배열의 front위치에 item을 집어넣는다.
2. front = (front – 1)%MAX
#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;
}
<실행결과>
DEQUE(front = 4 rear = 0) = 0 |
DEQUE(front = 3 rear = 0) = 1 | 0 |
DEQUE(front = 2 rear = 0) = 2 | 1 | 0 |
DEQUE(front = 2 rear = 4) = 2 | 1 |
DEQUE(front = 2 rear = 3) = 2 |
DEQUE(front = 2 rear = 2) =