[7] 큐 ⑤ 응용 : 배열로 구성된 원형 큐 ADT 구현

[ 문제 1-큐 ] 배열로 구성된 원형 큐를 위한 삽입, 삭제 프로그램을 작성하시오.

◦ 주요 전략 : 본 문제의 원형 큐에서는 포화 상태와 공백 상태를 구분하기 위해 한 자리를  비워둠.

 

- front, rear, 배열의 초기 값은 0

- 삽입 시 rear 값을 하나 증가시킨 후 데이터를 큐에 삽입 (출력 예시 1 참고)

- 삭제 시 front 값을 하나 증가시킨 후 front가 가리키는 데이터를 삭제

- front = rea r면 공백 상태로 정의하고, front가 rear보다 하나 앞에 있으면 포화 상태로 정의함

 

※ 주의 

 

주교재가 제시하는 전략에서는 front와 rear가 각각 큐의 맨 앞과 맨 뒤의 원소 위치를 직접 가리키는 방식으로 정의되어 있으나 위 전략은 front가 맨 앞 원소 위치보다 한 셀 앞 위치를 가리키는 방식으로 정의되었다.

 

주교재의 방식으로 변경하여 작성해도 무방하지만, 초기 상태에서 맨 처음 삽입되는 위치는 0번이 아니고, 1번이 되어야 함 (그렇지 않으면 본 문제의 입출력 예시와 다른 결과가 나올 수 있음).

큐의 상태

입출력 형식:
1) 첫 번째 라인 : 양의 정수 q (원형 큐의 크기)

※ q 값에는 제한이 없다. 또한, 동적 할당을 사용할 것.

2) 두 번째 라인 : 양의 정수 n (연산의 개수)
3) 세 번째 이후 라인: n개의 연산이 차례로 입력됨.

 

※ 연산의 종류는 I (삽입), D (삭제), P (출력)

 

- I 10 : 원형 큐에 원소 10을 삽입 (큐 원소는 양의 정수).

- D : 원형 큐에서 원소를 삭제한 후 해당 배열 원소 값을 0으로 치환.

- P : 배열 원소 전체를 차례로 화면에 출력 (입출력 예시 참조).

 

※ overflow 발생 시 (즉, 포화 상태에서 삽입을 시도한 경우), 화면에 overflow와 배열 값들을 모두 출력하고 프로그램 종료.

※ underflow 발생 시 (즉, 공백 상태에서 삭제를, 화면에 underflow를 출력하고 프로그램 종료.)

문제 풀이

헤더 선언 및 큐 구조체

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

typedef int element;

#define N 10

typedef struct {
    element *data; // 데이터 저장 배열
    int front, rear; // 포인터와 리어 변수
    int size;// 배열의 사이즈
} QueueType;

QueueType은 큐를 표현하는 구조체입니다. 구조체의 각 멤버는 다음과 같습니다:

 

• element *data: 큐에 저장할 데이터를 담는 배열의 포인터입니다. 동적으로 메모리를 할당받습니다.

• int front, rear: 큐의 앞(front)과 뒤(rear)를 가리키는 포인터입니다. 이 두 포인터를 사용하여 큐의 삽입과 삭제 연산을 수행합니다.

• int size: 큐의 전체 크기(용량)를 나타냅니다. 큐를 초기화할 때 이 값을 설정합니다.

init 함수

// 큐 초기화 함수
void init(QueueType *Q){
    Q->data = (int*)malloc(sizeof(int)*Q->size);
    Q->front = Q->rear = 0; // 큐의 front와 rear를 초기화
}

• Q->data는 큐가 저장할 배열로, malloc을 사용하여 동적으로 할당합니다.

• Q->front와 Q->rear를 0으로 초기화하여 큐의 시작과 끝을 설정합니다.

isEmpty 함수 /  isFull 함수

// 큐가 비어있는지 확인하는 함수
int isEmpty(QueueType *Q){
    return (Q->front == Q->rear);
}

// 큐가 꽉 차 있는지 확인하는 함수
int isFull(QueueType *Q){
    return (Q->front == (Q->rear + 1) % Q->size);
}

이 두 함수는 각각 큐가 비어있는지와 꽉 차 있는지를 확인하는 함수입니다.

 

• isEmpty

 

이 함수는 큐가 비어있는지를 확인합니다. 큐가 비어 있다면 true를 반환하고, 비어 있지 않다면 false를 반환합니다.

이를 확인하기 위해 큐의 front와 rear가 같은지를 비교합니다. 만약 둘이 같다면 큐는 비어있다는 의미입니다.

 

• isFull

 

이 함수는 큐가 꽉 차 있는지를 확인합니다. 큐가 꽉 차 있다면 true를 반환하고, 꽉 차 있지 않다면 false를 반환합니다.

이를 확인하기 위해 큐의 front와 rear의 다음 위치를 나타내는 (Q->rear + 1) % Q->size와 front가 같은지를 비교합니다.

만약 둘이 같다면 큐는 꽉 차 있다는 의미입니다.

 

이러한 함수들을 사용하여 큐가 비어있거나 꽉 차 있는지를 확인할 수 있습니다.

enqueue 함수

void enqueue(QueueType *Q, element e){
    if (isFull(Q)) {
        printf("overflow ");
        print(Q);
        exit(1);
    } else {
        Q->rear = (Q->rear + 1) % Q->size; // rear를 다음 위치로 이동
        Q->data[Q->rear] = e; // 데이터를 rear 위치에 삽입
    }
}

1. 먼저 isFull(Q) 함수를 사용하여 큐가 가득 찼는지 확인합니다.

2. 만약 큐가 가득 찼다면 오버플로우(overflow)가 발생했다는 메시지를 출력하고, 현재 큐의 상태를 출력한 후 프로그램을 종료합니다.

3. 만약 큐가 가득 차지 않았다면, Q->rear를 다음 위치로 이동시킨 후 해당 위치에 데이터를 삽입합니다.

dequeue 함수

// 큐에서 원소를 삭제하는 함수
element dequeue(QueueType *Q){
    // 공백 상태에서 삭제를 시도한 경우 처리
    if (isEmpty(Q)) {
        printf("underflow "); // underflow 메시지 출력
        exit(1); // 프로그램 종료
    } else {
        Q->front = (Q->front + 1) % Q->size; // front 이동
        int del = Q->data[Q->front]; // 삭제된 원소 저장
        Q->data[Q->front] = 0; // 삭제된 위치를 0으로 초기화
        return del; // 삭제된 원소 반환
    }
}

1. 먼저 isEmpty(Q) 함수를 사용하여 큐가 비어 있는지 확인합니다.

2. 만약 큐가 비어 있다면 언더플로우(underflow)가 발생했다는 메시지를 출력하고, 프로그램을 종료합니다.

3. 만약 큐가 비어 있지 않다면, Q->front를 다음 위치로 이동시킨 후 해당 위치의 데이터를 삭제하고 반환합니다.

print 함수

// 큐의 상태를 출력하는 함수
void print(QueueType *Q){
    for(int j=0; j<Q->size; j++){
        printf(" %d", Q->data[j]); // 배열의 모든 원소 출력
    }
    printf("\n");
}

1. 큐의 모든 원소를 순회하면서 배열의 각 원소를 출력합니다.

2. 각 원소는 공백을 사이에 두고 출력됩니다.

3. 모든 원소를 출력한 후에는 개행 문자(\n)를 출력하여 줄을 바꿉니다.

// 메인 함수
int main(){
    int q, n, e; // 큐의 크기, 연산의 개수, 원소
    scanf("%d", &q); // 큐의 크기 입력
    scanf("%d", &n); // 연산의 개수 입력
    getchar(); // 개행 문자 처리

    char F; // 연산을 나타내는 문자
    QueueType Q; // 큐 선언
    Q.size = q; // 큐의 크기 설정
    init(&Q); // 큐 초기화

    // 큐에 원소 삽입 전 모든 원소를 0으로 초기화
    for (int i = 0; i < Q.size; i++) {
        Q.data[i] = 0;
    }

    // 연산 수행
    for (int i = 0; i < n; i++) {
        scanf("%c", &F); // 연산 입력
        getchar(); // 개행 문자 처리

        switch (F) {
            case 'I':
                scanf("%d", &e); // 삽입할 원소 입력
                getchar(); // 개행 문자 처리
                enqueue(&Q, e); // 큐에 원소 삽입
                break;

            case 'D':
                dequeue(&Q); // 큐에서 원소 삭제
                break;

            case 'P':
                print(&Q); // 큐의 상태 출력
                break;
        }
    }
}

1. 사용자로부터 큐의 크기와 연산의 개수를 입력받습니다.

2. 큐를 초기화하고, 큐의 배열에 0으로 초기화된 원소들을 넣습니다.

3. 사용자로부터 연산을 입력받고, 해당 연산에 따라 적절한 동작을 수행합니다.

     - 'I' 이면 enqueue 함수를 호출하여 원소를 큐에 삽입한다.

     - 'D' 이면 dequeue 함수를 호출하여 원소를 큐에서 삭제한다.

     - 'P' 이면 print 함수를 호출하여 큐의 상태를 출력한다

5. 모든 연산을 처리한 후 프로그램이 종료됩니다.