[8] 트리 ③ 원형 큐

728x90

원형 큐를 이용한 이진트리 구현

원형 큐를 이용하여 이진 트리를이진트리를 구현하는 과정과 그 코드에 대해 설명드리겠습니다. 이번 포스팅에서는 C 언어로 작성된 코드를 사용하여 원형 큐를 구현하고, 이를 이용하여 이진트리를 구성하는 방법을 살펴보겠습니다.

원형 큐

원형 큐(Circular Queue)는 선형 큐에서 마지막 위치와 첫 번째 위치를 연결하여 하나의 원처럼 만든 자료 구조입니다. 이러한 구조를 통해 원형 큐는 선형 큐의 단점을 보완하여 효율적인 메모리 사용이 가능하게 합니다.

원형 큐와 일반큐의 차이점

큐는 FIFO(First In, FirstOut) 구조를 가지고 있어, 먼저 들어온 데이터가 먼저 나가는 특징을 갖습니다. 원형 큐와 일반 큐는 이러한 기본적인 큐의 특성을 공유하지만, 메모리 사용과 구현 방식에서 차이점이 있습니다. 아래에서 두 큐의 차이점을 비교하여 설명하겠습니다.

일반 큐

일반 큐는 선형 큐(Linear Queue)라고도 불리며, 배열 또는 연결 리스트를 이용하여 구현됩니다.

배열 기반 구현: 배열을 이용해 큐를 구현할 경우, 배열의 처음과 끝에서만 삽입과 삭제가 일어납니다.
메모리 낭비: 큐의 앞쪽에 데이터가 삭제되더라도, 해당 공간은 재사용되지 않습니다. 예를 들어, 큐의 앞에서 여러 개의 데이터가 삭제되면, 삭제된 위치는 사용되지 않으므로 메모리 낭비가 발생할 수 있습니다.
쉬운 구현: 일반 큐는 구현이 상대적으로 간단하며, 큐의 크기를 넘어서지 않는다면 잘 동작합니다.

원형 큐

원형 큐(Circular Queue)는 선형 큐의 단점을 보완하여, 배열의 처음과 끝이 연결된 구조를 가집니다.

배열 기반 구현: 배열의 처음과 끝이 연결되어 원형으로 동작합니다.
효율적인 메모리 사용: 큐가 가득 차거나 비어있는지 여부를 모호하게 판단하는 문제를 해결하기 위해, front와 rear 포인터를 사용합니다. 원형 큐는 빈 공간을 재사용할 수 있어 메모리 효율이 높습니다.
복잡한 구현: 원형 큐는 선형 큐에 비해 구현이 다소 복잡할 수 있지만, 메모리 효율성 면에서 장점을 가집니다.

주요 차이점 비교

구조	선형	원형 (시작과 끝이 연결됨)
메모리 사용	비효율적 (메모리 낭비 발생)	효율적 (빈 공간 재사용 가능)
구현 복잡도	상대적으로 쉬움	다소 복잡
포인터 이동	front와 rear 단순 증가	front와 rear 원형 이동
공간 재사용	불가능	가능

원형 큐 구현

아래는 원형 큐를 C 언어로 구현한 코드입니다.

구조체 정의

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

QueueType 구조체는 원형 큐의 핵심 데이터 구조입니다.
data는 큐의 데이터를 저장하는 배열입니다.
front와 rear는 큐의 앞과 뒤를 가리키는 인덱스입니다.
size는 큐의 크기를 나타냅니다.

초기화 함수

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

init 함수는 큐를 초기화합니다. 데이터 배열을 동적으로 할당하고, front와 rear를 0으로 설정합니다

삽입 함수

void enqueue(QueueType *Q, element e) {
    if (isFull(Q)) {
        printf("overflow ");
        printQue_R_TO_E(Q);
        exit(1);
    } else {
        Q->rear = (Q->rear + 1) % Q->size;
        Q->data[Q->rear] = e;
    }
}

enqueue 함수는 큐에 원소를 삽입합니다. 큐가 꽉 차있을 경우 overflow 메시지를 출력하고 프로그램을 종료합니다.
그렇지 않으면 rear를 이동시켜 데이터를 삽입합니다.

원형 큐에서 Q->rear = (Q->rear + 1) % Q->size;와 같은 로직을 사용하는 이유는 큐가 원형 구조를 유지하기 위해서입니다.

삭제 함수

element dequeue(QueueType *Q) {
    if (isEmpty(Q)) {
        printf("underflow ");
        exit(1);
    } else {
        Q->front = (Q->front + 1) % Q->size;
        int del = Q->data[Q->front];
        Q->data[Q->front] = 0;
        return del;
    }
}

dequeue 함수는 큐에서 원소를 삭제합니다. 큐가 비어있을 경우 underflow 메시지를 출력하고 프로그램을 종료합니다.
그렇지 않으면 front를 이동시켜 데이터를 삭제합니다.

큐 상태 출력 함수

void printQue_R_TO_E(QueueType *Q) {
    for (int j = 0; j < Q->size; j++) {
        printf("[%c] ", Q->data[j]);
    }
    printf("\n");
}

printQue_R_TO_E 함수는 큐의 현재 상태를 출력합니다.

원형 큐에서 모듈로 연산의 필요성

원형 큐는 선형 큐의 단점을 보완하기 위해 고안되었습니다. 선형 큐에서는 데이터가 삭제되면 빈 공간이 생기고, 이러한 빈 공간은 재사용되지 않기 때문에 비효율적인 메모리 사용이 발생할 수 있습니다.

원형 큐는 배열의 끝과 처음을 연결하여 이러한 문제를 해결합니다.

모듈로 연산 (%)의 역할

모듈로 연산 %는 배열의 인덱스를 원형으로 만들기 위해 사용됩니다. 예를 들어, 배열의 크기가 10일 때, 인덱스가 9까지 차 있다면 다음 인덱스는 10이 되어야 합니다. 그러나 배열의 크기를 초과하는 인덱스를 사용하면 안 되므로, 10을 다시 0으로 만들어 처음으로 돌아가야 합니다. 이를 위해 모듈로 연산을 사용합니다.

Q->rear = (Q->rear + 1) % Q->size;

Q->rear는 현재 큐의 마지막 원소가 저장된 위치를 가리킵니다.
(Q->rear + 1)는 새로운 원소가 삽입될 위치를 의미합니다.
% Q->size는 배열의 크기로 나눈 나머지를 구하는 연산입니다.
이 연산을 통해 인덱스가 배열의 크기를 넘어가는 경우 다시 0으로 돌아가도록 합니다.

예시를 통한 설명

예를 들어, 큐의 크기가 5 (Q->size = 5)인 경우를 생각해 봅시다. 큐가 다음과 같은 상태라고 가정합니다:

Index:  0  1  2  3  4
Data:   A  B  C  D
Front:  0
Rear:   3

enqueue 연산을 통해 새로운 원소 E를 삽입하고자 할 때:

1. Q->rear는 현재 3입니다.

2. (Q->rear + 1) % Q->size를 계산하면 (3 + 1) % 5 = 4가 됩니다.

3. Q->rear는 4가 되고, E는 Q->data[4]에 저장됩니다.

Index:  0  1  2  3  4
Data:   A  B  C  D  E
Front:  0
Rear:   4

다시 새로운 원소 F를 삽입하려고 할 때:

1. 현재 Q->rear는 4입니다.

2. (Q->rear + 1) % Q->size를 계산하면 (4 + 1) % 5 = 0이 됩니다.

3. Q->rear는 0이 되고, F는 Q->data[0]에 저장됩니다.

Index:  0  1  2  3  4
Data:   F  B  C  D  E
Front:  0
Rear:   0

이처럼 모듈로 연산을 사용하면 배열의 크기를 초과하지 않고, 인덱스가 자동으로 순환하여 원형 큐의 구조를 유지할 수 있습니다.

Q->rear = (Q->rear + 1) % Q->size;와 같은 로직을 사용하는 이유는 원형 큐가 배열의 끝과 처음을 연결하여 메모리를 효율적으로 사용하기 위함입니다. 모듈로 연산 %는 인덱스가 배열의 크기를 넘어갈 때 처음으로 돌아가도록 하여 원형 큐의 특성을 유지하게 합니다. 이를 통해 큐의 모든 공간을 효율적으로 활용할 수 있습니다.

main 함수

메인 함수에서는 큐를 초기화하고 임의의 데이터를 삽입하고 삭제하며 큐의 상태를 출력합니다. 이를 통해 원형 큐가 정상적으로 작동하는지 확인할 수 있습니다.

전체 코드

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

typedef char element;

#define MAX 10

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

void print(QueueType *Q);
void printQue_R_TO_E(QueueType *Q);

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

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

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

// 큐에 원소를 삽입하는 함수
void enqueue(QueueType *Q, element e){
    // 포화 상태에서 삽입을 시도한 경우 처리
    if (isFull(Q)) {
        printf("overflow "); // overflow 메시지 출력
        printQue_R_TO_E(Q); // 현재 큐의 상태 출력
        exit(1); // 프로그램 종료
    } 
    else {
        Q->rear = (Q->rear + 1) % Q->size; // rear 이동
        Q->data[Q->rear] = e; // 데이터 삽입
    }
}

// 큐에서 원소를 삭제하는 함수
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; // 삭제된 원소 반환
    }
}

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

void printQue(QueueType *Q){
    int i = Q->front;
    while (i != Q->rear) {
        i = (i + 1) % Q->size;
        printf("%c ", Q->data[i]);
    }
    printf("\n");
}

void printQue_R_TO_E(QueueType *Q){
     for(int j=0; j<Q->size; j++){
        printf("[%c] ", Q->data[j]); // 배열의 모든 원소 출력
    }
    printf("\n");
}

// 메인 함수
int main(){
    QueueType Q; // 큐 선언
    Q.size = MAX; // 큐의 크기 설정
    init(&Q); // 큐 초기화
    for (int i = 0; i < Q.size; i++) {Q.data[i] = ' ';}

    srand(time(NULL));

    for (int i = 0; i < 7; i++) enqueue(&Q, rand()% 26 + 65);printQue_R_TO_E(&Q);
    for (int i = 0; i < 3; i++) printf("[%c] is dequeded.\n",dequeue(&Q));printQue_R_TO_E(&Q);
    
    for (int i = 0; i < 3; i++) enqueue(&Q, rand()% 26 + 65);printQue_R_TO_E(&Q);
    for (int i = 0; i < 1; i++) printf("[%c] is dequeded.\n",dequeue(&Q));printQue_R_TO_E(&Q);

    for (int i = 0; i < 3; i++) enqueue(&Q, rand()% 26 + 65);printQue_R_TO_E(&Q);

    enqueue(&Q, rand()% 26 + 65);printQue_R_TO_E(&Q);
}

728x90

저작자표시

'Datastructure > [8] 트리' 카테고리의 다른 글

[8] 트리 ⑥ 응용 (1) : 연결리스트를 이용한 트리 구현 (1)	2024.06.05
[8] 트리 ⑤ 스택을 이용한 이진 트리 (1)	2024.06.04
[8] 트리 ④ 레벨 순회 : 원형 큐 이용 (0)	2024.06.03
[8] 트리 ② 트리의 구현 : ADT (0)	2024.05.30
[8] 트리 ① 트리의 정의 (1)	2024.05.29

일	월	화	수	목	금	토
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30	31

우당탕탕 코딩 제작소

[8] 트리 ③ 원형 큐

원형 큐를 이용한 이진트리 구현

원형 큐

원형 큐와 일반큐의 차이점

일반 큐

원형 큐

주요 차이점 비교

원형 큐 구현

구조체 정의

초기화 함수

삽입 함수

삭제 함수

큐 상태 출력 함수

원형 큐에서 모듈로 연산의 필요성

모듈로 연산 (%)의 역할

main 함수

전체 코드

'Datastructure > [8] 트리' 카테고리의 다른 글

티스토리툴바

[8] 트리 ③ 원형 큐

원형 큐를 이용한 이진트리 구현

원형 큐

원형 큐와 일반큐의 차이점

일반 큐

원형 큐

주요 차이점 비교

원형 큐 구현

구조체 정의

초기화 함수

삽입 함수

삭제 함수

큐 상태 출력 함수

원형 큐에서 모듈로 연산의 필요성

모듈로 연산 (%)의 역할

main 함수

전체 코드

'Datastructure > [8] 트리' 카테고리의 다른 글

'Datastructure/[8] 트리' 관련글

티스토리툴바