Data structure
[C언어로 쉽게 풀어쓴 자료구조] Chapter 5 - 큐
MoveForward
2022. 2. 19. 03:15
큐(queue)는 먼저 들어온 데이터가 먼저 나가는 구조 : 선입선출(First-In First-Out)
스택은 삽입과 삭제가 같은 쪽에서 일어난다. 그러나 큐는 삽입은 후단(rear), 삭제는 전단(front)에서 일어난다.
// 선형큐 프로그램
// 선형큐
#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()
{
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 | | |
| | | | |
*/
// 원형큐
선형큐가 가지고 있는 문제점 : 큐 내의 front와 rear의 값이 증가만 하기 때문에 언젠가 MAX_QUEUE_SIZE에 도달하게 되면 사용자가 큐 내의 요소들을 왼쪽으로 이동 시켜 주어야 한다.
이러한 문제점을 원형큐로 해결 하였다.
원형큐는 rear의 값이 MAX_QUEUE_SIZE - 1인 상황에서 다시 push()가 발생하면, rear 값은 0이 된다.
선형큐에서 front, rear의 초기값은 -1이었지만, 원형큐에서는 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("큐가 포화상태입니다.");
// 1. rear값을 먼저 1만큼 이동 시킨다.
q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
// 2. item을 삽입 한다.
q->data[q->rear] = item;
}
// 삭제 함수
element dequeue (QueueType *q)
{
if (is_empty(q))
error("큐가 공백상태입니다.");
// 1. front값을 먼저 1만큼 이동 시킨다.
q->front = (q->front+1)%MAX_QUEUE_SIZE;
// 2. front값의 인덱스에 위치해 있던 요소를 반환한다.
return q->data[q->front];
}
// 피크함수
element peek (QueueType *q)
{
if (is_empty(q))
error("큐가 공백상태입니다.");
// front한칸 앞에 위치한 요소를 즉시 반환한다.
return q->data[(q->front+1)%MAX_QUEUE_SIZE];
}
int main()
{
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;
}
/*출력값
--데이터 추가 단계--
정수를 입력하시오: 11
QUEUE(front=0 rear=1) = 11 |
정수를 입력하시오: 22
QUEUE(front=0 rear=2) = 11 | 22 |
정수를 입력하시오: 33
QUEUE(front=0 rear=3) = 11 | 22 | 33 |
정수를 입력하시오: 44
QUEUE(front=0 rear=4) = 11 | 22 | 33 | 44 |
큐는 포화 상태 입니다.
--데이터 삭제 단계--
꺼내진 정수 : 11
QUEUE(front=1 rear=4) = 22 | 33 | 44 |
꺼내진 정수 : 22
QUEUE(front=2 rear=4) = 33 | 44 |
꺼내진 정수 : 33
QUEUE(front=3 rear=4) = 44 |
꺼내진 정수 : 44
QUEUE(front=4 rear=4) =
큐는 공백상태입니다.
*/
// 큐 응용 프로그램 (버퍼)
// 큐의 응용 : 버퍼
/*
버퍼 (buffer) : 데이터를 한 곳에서 다른 한곳으로 전송하는 동안 실시적으로 그 데이터를 보관하는 메모리의 영역
*/
// 큐 응용 프로그램 (버퍼)
#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("큐가 포화상태입니다.");
// 1. rear값을 먼저 1만큼 이동 시킨다.
q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
// 2. item을 삽입 한다.
q->data[q->rear] = item;
}
// 삭제 함수
element dequeue (QueueType *q)
{
if (is_empty(q))
error("큐가 공백상태입니다.");
// 1. front값을 먼저 1만큼 이동 시킨다.
q->front = (q->front+1)%MAX_QUEUE_SIZE;
// 2. front값의 인덱스에 위치해 있던 요소를 반환한다.
return q->data[q->front];
}
// 피크함수
element peek (QueueType *q)
{
if (is_empty(q))
error("큐가 공백상태입니다.");
// front한칸 앞에 위치한 요소를 즉시 반환한다.
return q->data[(q->front+1)%MAX_QUEUE_SIZE];
}
/* ********************************* */
int main()
{
QueueType queue;
int element;
init_queue(&queue);
srand(time(NULL));
for(int i=0; i<100; i++){
if (rand()%5 == 0){
enqueue(&queue, rand()%100);
}
queue_print(&queue);
if(rand()%10 == 0){
int data = dequeue(&queue);
}
queue_print(&queue);
}
return 0;
}
// 원형덱
덱(deque) : 전단, 후단 모두에서 삽입과 삭제가 일어나는 큐
// 덱 (deque) : double-ended queue , 큐의 전단 / 후단 모두에서 삽입과 삭제가 가능한 큐
#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("덱이 포화상태입니다.");
//1. 현재 front가 가지고 있는 인덱스에 즉시 요소 추가
q->data[q->front] = val;
//2. front를 한단계 앞으로 (원형덱 인덱스 -1만큼 이동) , front가 음수가 되면 안됨으로 MAX_QUEUE_SIZE 만큼 더해주고 나머지를 구한다.
q->front = (q->front-1+MAX_QUEUE_SIZE)%MAX_QUEUE_SIZE;
}
// 삭제 함수 (후단) , 기존 원형큐에서 없던것
element delete_rear(DequeType *q)
{
int prev = q->rear; // 현재 rear값을 prev에 저장
if (is_empty(q))
error("덱이 공백상태입니다.");
// 1. rear 값을 한단계 앞으로
q->rear = (q->rear - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
// 2. prev에 저장해 놓았던 rear값 (1번 이전의 rear 값)의 인덱스에 저장된 요소 반환
return q->data[prev];
/* prev를 굳이 선언 하는 이유
// 1. 요소를 반환 (return)
return q->data[rear];
// 2. rear 조정
p->rear = (q->rear -1 +MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
위와 같은 방식으로 한다면,
"컴파일러는 return 문 뒤에 배치된 문을 찾으면 접근할 수 없는 코드에 대한 경고 진단 메시지를 실행할 수 있습니다."
이와 같은 문제가 발생할 수 있기 떄문에 별도로 선언하는 것 같다.
*/
}
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) =
*/
// 은행 서비스 시뮬레이션 프로그램
// 은행 서비스 시뮬레이션 프로그램
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int id, arrival_time, 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("큐가 포화상태입니다.");
// 1. rear값을 먼저 1만큼 이동 시킨다.
q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
// 2. item을 삽입 한다.
q->data[q->rear] = item;
}
// 삭제 함수
element dequeue (QueueType *q)
{
if (is_empty(q))
error("큐가 공백상태입니다.");
// 1. front값을 먼저 1만큼 이동 시킨다.
q->front = (q->front+1)%MAX_QUEUE_SIZE;
// 2. front값의 인덱스에 위치해 있던 요소를 반환한다.
return q->data[q->front];
}
// 피크함수
element peek (QueueType *q)
{
if (is_empty(q))
error("큐가 공백상태입니다.");
// front한칸 앞에 위치한 요소를 즉시 반환한다.
return q->data[(q->front+1)%MAX_QUEUE_SIZE];
}
int main()
{
int minutes = 60; // 60분 동안의 total_wait 를 출력하기 때문
int total_wait = 0; // 고객들이 기다린 시간 전부 합
int total_customers = 0; // 총 고객의 수
int service_time = 0; // 0이면, 현재 서비스 중인 고객이 없음.
int service_customer;
QueueType queue;
init_queue(&queue);
srand(time(NULL)); // 난수생성을 위한 함수
// clock 변수 생성 , 1씩 증가 (제한 시간 60으로 설정)
for (int clock = 0; clock < minutes; clock++){
printf("현재시각=%d\n", clock);
// 3이하의 난수가 생성되면, 고객이 입장한다고 설정
if ((rand()%10) < 3) {
element customer; // customer 객체 생성
customer.id = total_customers++; // 방문한 순서에 따라 id 부여
customer.arrival_time = clock;
customer.service_time = rand() % 3+1; // (1<service_time<3) , 고객당 필요한 서비스 시간
enqueue(&queue, customer); // customer 객체(구조체) 큐에 삽입
printf("고객id : %d \n입장시간 : %d \n업무처리시간 : %d분\n",
customer.id, customer.arrival_time, customer.service_time);
}
if (service_time > 0){
printf("고객 %d 업무처리중입니다. \n", service_customer);
service_time--;
}
else { // service_time = 0 : 현재 서비스중인 고객이 없다. => 큐에서 새로운 고객을 꺼낸다.
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;
}