[C언어로 쉽게 풀어쓴 자료구조] Chapter 5 - 큐

큐(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;
}