[C] 배열로 Queue 만들기

www.notion.so/3-9562fe0842f947a9918b0bab6796ab8a

✔︎ 미션 3

1. 미션 제목

배열로 Queue 만들어보기!

2. 지시문

이번 과제에서는 Queue를 구현해 봅시다! Stack 과 Queue의 구현은 얼핏 보면 비슷해 보이지만 막상 구현해 보면 많은 부분이 다르답니다. 어떻게 구현하면 좋을지 고민이 많이 필요할 수도 있습니다. 이미 구현된 부분들을 잘 살피고 어떤 식으로 구현해야 할 지 생각해서 채워주세요.

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

typedef struct queue {
    int front;
    int rear;
    int size;
    int capacity;
    int* array;
} Queue;

Queue* createQueue(int capacity) {
    Queue* queue = (Queue *)malloc(sizeof(Queue));
    queue->capacity = capacity;
    queue->front = 0;
    queue->size = 0;
    queue->rear = capacity-1; // 왜 이렇게 초기화 했는지 잘 생각해 보세요!
    queue->array = (int *)malloc(sizeof(int)*queue->capacity);
    return queue;
}

int isFull(Queue* queue) {
    return (queue->size == queue->capacity);
}

int isEmpty(Queue* queue) {
    return (queue->size == 0);
}

void enqueue(Queue* queue, int item) {
    if (isFull(queue)) {
        return;
    }
// 이 부분을 구현해 주세요!
    printf("%d enqueued to queue\n", item);
}

int dequeue(Queue* queue) {
    if (isEmpty(queue)) {
        return -9999;
    }
    int item = 0;
    // 이 부분을 구현해 주세요!
    return item;
}


int main() {
    Queue* queue = createQueue(1000);

    enqueue(queue, 10);
    enqueue(queue, 20);
    enqueue(queue, 30);
    enqueue(queue, 40);

    printf("%d dequeued from queue\n\n", dequeue(queue));
    return 0;
}

위의 Main 함수를 실행시키면 Queue 출력 결과가 아래와 같이 나와야 합니다.

 

10 enqueued to queue

20 enqueued to queue

30 enqueued to queue

40 enqueued to queue

10 dequeued from queue

 

Front item is 20

Rear item is 40

 

Queue 도 연결리스트를 이용해서 구현할 수도 있습니다. 과제와 상관없이 Queue를 연결리스트로도 구현해 보면 어떨까요?

 

3. 핵심 개념

#Queue #연결리스트 #Queue 구현

나의 풀이

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

typedef struct queue {
    int front;
    int rear;
    int size;
    int capacity;
    int* array;
} Queue;

Queue* createQueue(int capacity) {
    Queue* queue = (Queue*)malloc(sizeof(Queue));
    queue->capacity = capacity;
    queue->front = 0;
    queue->size = 0;
    queue->rear = capacity - 1; // 왜 이렇게 초기화 했는지 잘 생각해 보세요!
    // --> rear는 queue에서 마지막 데이터가 저장된 위치를 가리킴
    queue->array = (int*)malloc(sizeof(int) * queue->capacity);
    return queue;
}

int isFull(Queue* queue) {
    return (queue->size == queue->capacity);
}

int isEmpty(Queue* queue) {
    return (queue->size == 0);
}

void enqueue(Queue* queue, int item) {
    if (isFull(queue)) {
        return;
    }
    // 이 부분을 구현해 주세요!
    queue->rear = (++queue->rear) % queue->capacity; // rear를 하나 증가시켜서 저장
    queue->array[queue->rear] = item;  // rear가 가리키는 위치에 item 삽입
    queue->size++;
    printf("%d enqueued to queue\n", item);
}

int dequeue(Queue* queue) {
    if (isEmpty(queue)) {
        return -9999;
    }
    int item = 0;
    // 이 부분을 구현해 주세요!
    item = queue->array[queue->front];
    queue->front = (++queue->front) % queue->capacity;
    queue->size--;
    return item;
}


int main() {
    Queue* queue = createQueue(5);

    enqueue(queue, 10);
    enqueue(queue, 20);
    enqueue(queue, 30);
    enqueue(queue, 40);
    enqueue(queue, 50);
    enqueue(queue, 60);
    enqueue(queue, 70);
    enqueue(queue, 80);
    printf("\n-------------------------------\n");
    printf("%d dequeued from queue\n\n", dequeue(queue));
    printf("%d dequeued from queue\n\n", dequeue(queue));

    printf("Front item is %d\n\n", queue->array[queue->front]);
    printf("Rear item is %d\n\n", queue->array[queue->rear]);

    printf("%d dequeued from queue\n\n", dequeue(queue));
    printf("%d dequeued from queue\n\n", dequeue(queue));
    printf("%d dequeued from queue\n\n", dequeue(queue));
    printf("%d dequeued from queue\n\n", dequeue(queue));
    printf("%d dequeued from queue\n\n", dequeue(queue));
    printf("%d dequeued from queue\n\n", dequeue(queue));
    printf("%d dequeued from queue\n\n", dequeue(queue));
    return 0;
}

queue 구조체에는 front, rear, size, capacity, array 이렇게 5개의 멤버를 가진다. front는 큐에 가장 먼저 저장된 아이템의 위치, rear는 가장 마지막에 저장된 아이템의 위치, size는 현재 큐에 들어간 아이템의 개수, capacity는 큐의 최대 용량, array는 실제 큐로 저장 될 배열을 뜻한다.

createQueue

Queue* createQueue(int capacity) {
    Queue* queue = (Queue*)malloc(sizeof(Queue));
    queue->capacity = capacity;
    queue->front = 0;
    queue->size = 0;
    queue->rear = capacity - 1;
    queue->array = (int*)malloc(sizeof(int) * queue->capacity);
    return queue;
}

createQueue 함수를 보면 queue 구조체의 멤버가 어떻게 초기화 되는 지 알 수 있다.

파라미터로 큐의 크기를 입력 받아 그 크기만큼 array 배열을 동적 할당하는 것을 알 수 있다.

아무런 아이템도 없는 상태이기 때문에 front와 size는 0으로 초기화 된다.

 

하지만 rear는 capacity - 1로 초기화가 되었는데 이 점이 의문이었다. 사실 rear가 정말 큐에서 아이템의 마지막 위치를 가리킨다면 초기화 됐을 때 front과 같이 0으로 초기화 되었어야 한다.

 

그래서 처음에는 rear가 capacity - 1로 초기화 된 것과 상관 없이 프로그램을 작성했다. 물론 동작은 제대로 했다. 어떻게 작성했었는지는 뒤에 enqueue() 함수를 설명할 때 설명하겠다.

isFull()

int isFull(Queue* queue) {
    return (queue->size == queue->capacity);
}

isFull 함수는 이름 그대로 큐가 가득 찼는지 검사해서 가득 찼다면 1(true)을 반환한다.

검사 방법은 size와 capacity가 같은지 비교한다.

isEmpty()

int isEmpty(Queue* queue) {
    return (queue->size == 0);
}

isEmpty 함수는 이름 그대로 큐가 비었는지 검사해서 비었다면 1(true)을 반환한다.

검사 방법은 size가 0인지 확인한다.

enqueue()

enqueue 함수는 큐에 입력 받은 아이템(정수)을 삽입하는 함수이다.

큐가 가득 차 있다면 아이템을 삽입할 수 없으므로 isFull 함수로 검사하여 가득 찼다면 아무 동작도 하지 않고 반환한다.

직접 구현할 부분은 다음 부분이다.

위에서 언급한 것과 같이 처음에는 rear의 초기값을 고려하지 않고 코딩하였다. 그것은 다음과 같다.

// 초기에 작성한 enqueue 함수

void enqueue(Queue* queue, int item) {
	if (isFull(queue)) {
		return;
	}
	int index = (queue->front + queue->size) % queue->capacity;
	queue->array[index++] = item;
	queue->rear = index;
	queue->size++;
	printf("%d enqueued to queue\n", item);
}

위의 소스 코드를 보면 아이템이 삽입될 위치인 index를 구하는데 front와 size, capacity를 사용한다. (front + size) % capacity를 하면 아이템이 삽입될 위치를 바로 구할 수 있다. 그리고 index를 하나 증가시켜서 rear에 저장했다.

이 코드에서 나는 rear를 앞으로 아이템이 저장 될 위치로 생각하여 코딩하였고, 사실 굳이 rear를 사용하지 않아도 되는 코드를 작성하였다.

 

물론 위처럼 짜도 제대로 동작한다.

 

하지만 주어진 미션에서 rear를 capacity - 1로 초기화 한 것을 사용하지 않았기 때문에 어떤 의도에서 위처럼 초기화 했을 지 고민하다가 도출해낸 결과는 다음과 같다.

// 미션 의도에 맞춘 새로 작성한 enqueue 함수

void enqueue(Queue* queue, int item) {
    if (isFull(queue)) {
        return;
    }
    queue->rear = (++queue->rear) % queue->capacity;
    queue->array[queue->rear] = item;
    queue->size++;
    printf("%d enqueued to queue\n", item);
}

우선 아이템을 삽입하는 과정이 5line에서 3line으로 줄었으며, 데이터 삽입 위치를 구할 때 front와 size를 더하는 산수 과정도 생략되었다.

 

새로 작성한 코드에서는 위 코드와 다르게 rear를 앞으로 아이템이 저장 될 위치가 아닌 현재 큐에 마지막으로 저장 된 위치로 생각하였다.

 

또한 front와 size를 더하지 않고 rear를 직접 가져와서 사용했다.

 

rear는 초기화 될 때 capacity - 1로 초기화 되어서 큐의 마지막을 가리키고 있다. 그렇기 때문에 (++queue->rear) % queue->capacity로 계산하면 0번 인덱스를 가리키게 된다.

 

array의 해당 위치에 item을 삽입하고 size를 하나 늘려주는 동작을 하는 함수가 작성되었다.

dequeue()

dequeue 함수는 enqueue함수와 반대로 큐에서 아이템을 추출하는 함수이다.

int dequeue(Queue* queue) {
    if (isEmpty(queue)) {
        return -9999;
    }
    int item = 0;
    item = queue->array[queue->front];
    queue->front = (++queue->front) % queue->capacity;
    queue->size--;
    return item;
}

가장 먼저 큐가 비었는지 검사하고, 큐가 비었다면 -9999를 return 하면서 함수는 종료된다.

큐는 FIFO(First In First Out) 구조이므로 가장 먼저 들어온 아이템이 가장 먼저 빠져 나가게 되고, front가 가장 먼저 들어온 아이템을 가리키고 있다.

그렇기 때문에 array에서 front가 가리키는 위치에 접근하여 아이템을 item 변수에 저장하고, front를 하나 증가해서 저장하고, size를 하나 줄이는 함수가 작성되었다.

main 함수와 결과창

기존에 주어진 main함수에서 capacity를 5로 조정하고, 조금 더 많은 아이템을 enqueue(삽입), dequeue(삭제) 해보았습니다.

queue에 10~80까지 아이템을 enqueue하였는데 capacity가 5이기 때문에 아이템은 50까지만 삽입이 되었고, 그 이후로는 아무런 동작 없이 바로 return 되었습니다.

 

이후 아이템 dequeue를 2회 진행하고 front의 값과, rear의 값을 확인해 보았습니다. 큐에는 10과 20이 제거되어 30, 40, 50이 순차적으로 저장된 상태이므로 front값은 30, rear값은 50을 정상적으로 가리키고 있습니다.

 

이후 아이템 dequeue를 7회 더 진행해보았는데 큐에 남아있던 3개의 아이템이 삽입된 순서대로 제거되었고, 아이템이 모두 제거되어 큐가 비어있는 상태에서 계속해서 dequeue를 진행해보니 큐가 비어있기 때문에 -9999를 반환하는 결과를 볼 수 있었습니다.