[자료구조 - C언어] 자료구조 제18강: 큐(queue)의 개념과 구현(2)

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎

 

1. 환형(circular) 배열

• 배열은 개수가 정해져 있기 때문에 인덱스가 배열의 범위를 벗어나게 되면 어떻게 되는지
• 배열로 구현한 큐는 front부터 rear까지 꽉 차 있어야 한다.
  • 배열의 범위를 벗어난다고 해서 reallocate를 할 수 없는 이유 → ②처럼 빈 공간이 남아 있기 때문

⇒ 환형 배열을 이용해서 큐를 구현할 수 있다.

 

2. 환형 배열을 이용한 큐 구현

• queueADT_array.c

//  queueADT_array.c

#include <stdio.h>
#include <stdlib.h>
#include "queueuADT.h"

#define INIT_CAPACITY 100

struct queue_type{
    Item *contents;    //배열~ 포인터 선언: 배열을 동적 할당으로 받겠다
    int front;              //배열에서 index로 활용
    int rear;
    int size;                //저장된 데이터의 개수
    int capacity;         //배열 contents의 크기
};

//오류 발생시 메세지 출력 함수
void terminate(const char *message){
    printf("%s\\n", message);
    exit(EXIT_FAILURE);
}

//큐의 사이즈를 리턴하는 함수
int get_size(Queue q){
    return q->size;
}

Queue create(){
    //큐를 할당 받고
    Queue q = malloc(sizeof(struct queue_type));
    if(q==NULL)
        terminate("Error in create: queue could not be created.");
    //큐 안에 contents 배열도 할당 받음
    q->contents = (Item *)malloc(INIT_CAPACITY * sizeof(Item));
    if(q->contents == NULL){
        free(q);
        terminate("Error in create: queue could not be created.");
    }
    
    //초기화
    q->front = 0;
    q->rear = -1;
    q->size = 0;
    q->capacity = INIT_CAPACITY;
    return q;
}

//큐안에 contents가 동적으로 할당 ~ contents를 먼저 free, 큐를 free
void destroy(Queue q){
    free(q->contents);
    free(q);
}

//큐를 비우는 함수 - 초기상태로
void make_empty(Queue q){
    q->front = 0;
    q->rear = -1;
    q->size = 0;
}

bool is_empty(Queue q){
    return q->size == 0;
}

bool is_full(Queue q){
    return q->size == q->capacity;
}

void reallocate(Queue q){
    //크기가 2배인 배열을 할당 받음
    Item *tmp = (Item *)malloc(2 * q->capacity * sizeof(Item));
    if(tmp == NULL)
        terminate("Error in create: queue could not be expanded.");

    //큐에서는 어디가 front이고 rear인지가 중요
    //큐에서는 front ~ rear까지 데이터가 꽉 차있어야 한다.
    //인덱스를 그대로 옮기면 front부터 rear까지 데이터가 꽉 차있지 않는 문제가 발생
    //-> 데이터를 복사해 오는 순서를 front부터
    int j = q->front;
    for(int i=0; i<q->size; i++){    //size개 만큼 복사
        //원래 큐에서 j번째 데이터(= front)를 i번째(= 0부터 시작)로 복사
        tmp[i] = q->contents[j];
        //j는 배열의 끝에 도달하면 다시 돌아가야 하니까
        j = (j+1) % q->capacity;
    }
    free(q->contents);
    
    q->front = 0;
    q->rear = q->size -1;
    //새로운 배열 tmp를 contents로
    q->contents = tmp;
    q->capacity *= 2;
}

//rear에 새로운 데이터를 삽입
void enqueue(Queue q, Item i){
    //큐가 꽉 찼다면 - 재할당
    if(is_full(q))
        reallocate(q);
    
    //원형 배열이기 때문에
    //1 증가시킨 범위가 배열 인덱스의 범위를 벗어나면 안되기 때문에
    //끝에 도달하면 다시 처음으로 돌아오게 함
    q->rear = (q->rear + 1) % q->capacity;
    q->contents[q->rear] = i;
    q->size++;
}

//front에 저장된 데이터를 리턴하고 삭제하는 함수
Item dequeue(Queue q){
    if(is_empty(q))
        terminate("Error in dequeue: queue is empty.");
    
    //front 값을 변경하기 전에 값을 저장하고 리턴해야 함
    Item result = q->contents[q->front];
    //front 자체도 한 칸 전진 && 원형 배열
    q->front = (q->front + 1) % q->capacity;
    q->size--;
    return result;
}

Item peek(Queue q){
    if(is_empty(q))
        terminate("Erron in peek: queue is empty.");
    return q->contents[q->front];
}

• main.c

int main(){
    Queue q = create();
    printf("enqueue: ");
    enqueue(q, 1);enqueue(q, 2);enqueue(q, 3);enqueue(q, 4);enqueue(q, 5);
    print_array(q);
    
    printf("dequeue: ");
    dequeue(q);dequeue(q);dequeue(q);
    print_array(q);
    
    printf("원형 배열 활용 && reallocate(): ");
    enqueue(q, 6);enqueue(q, 7);enqueue(q, 8);enqueue(q, 9);
    print_array(q);
}

//enqueue: 1 2 3 4 5 
//dequeue: 4 5 
//원형 배열 활용 && reallocate(): 4 5 6 7 8 9

2-1. void reallocate(Queue q)

void reallocate(Queue q){
    ...

    //-> 데이터를 복사해 오는 순서를 front부터
    int j = q->front;
    for(int i=0; i<q->size; i++){    //size개 만큼 복사
        //원래 큐에서 j번째 데이터(= front)를 i번째(= 0부터 시작)로 복사
        tmp[i] = q->contents[j];
        //j는 배열의 끝에 도달하면 다시 돌아가야 하니까
        j = (j+1) % q->capacity;
    }
    free(q->contents);
    
    q->front = 0;
    q->rear = q->size -1;
    //새로운 배열 tmp를 contents로
    q->contents = tmp;
    q->capacity *= 2;
}

 

 

 

 

---

부경대학교 권오흠 교수님의 [c로 배우는 자료구조 및 여러 가지 예제 실습] 강의 정리입니다. 감사합니다.

https://youtu.be/TcWQvwL2tPM