[부스트 코딩 뉴비 챌린지 2020] week6_미션03 : 배열로 Queue 만들기

✔︎ 미션 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));
    if(!queue){
        printf("failed to create queue\n");
        exit(0);
    }
    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)) {
        printf("queue is full. can't enqueue\n");
        return;
    }
    queue->size++;
    queue->rear = (++queue->rear)%(queue->capacity);
    queue->array[queue->rear] = item;
    printf("%d enqueued to queue\n", item);
}

void dequeue(Queue* queue) {
    if (isEmpty(queue)) {
        printf("queue is empty. can't dequeue\n");
        return;
    }
    queue->size--;
    printf("%d dequeued from queue\n", queue->array[queue->front]);
    queue->front = (++queue->front)%(queue->capacity);
}


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

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

    dequeue(queue);
    dequeue(queue);
    dequeue(queue);
    dequeue(queue);
    dequeue(queue);
    return 0;
}

 

실행 결과값

10 enqueued to queue
20 enqueued to queue
30 enqueued to queue
40 enqueued to queue
queue is full. can't enqueue
10 dequeued from queue
20 dequeued from queue
30 dequeued from queue
40 dequeued from queue
queue is empty. can't dequeue
queue is empty. can't dequeue
10 enqueued to queue
20 enqueued to queue
30 enqueued to queue
40 enqueued to queue
queue is full. can't enqueue
10 dequeued from queue
20 dequeued from 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));
    // 메모리 할당 잘 되었는지 확인
    if(!queue){
        printf("failed to create queue\n");
        exit(0);
    }
    queue->capacity = capacity;
    queue->front = 0;
    queue->size = 0;
    queue->rear = capacity-1; //  queue가 공백인 경우와 1개 든 경우에 모두 front=rear이므로 이 두 경우를 구분해주기 위해서.
    //empty인 상황에서 값을 enqueue 하나를 하게 되면 front=rear=0이 된다.
    queue->array = (int *)malloc(sizeof(int)*queue->capacity);
    // 메모리 할당 잘 되었는지 확인
    if(!(queue->array))
        exit(0);
    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)) {    //큐가 꽉 찬 경우 enqueue를 못하므로 종료
        printf("queue is full. can't enqueue\n");
        return;
    }
    queue->size++;  //사이즈를 키워줌
    queue->rear = (++queue->rear)%(queue->capacity);    //0~(capacity-1) 값을 순환함. capacity가 10인 경우 0~9 10개의 값을 순환하게 된다.
    queue->array[queue->rear] = item;   //큐의 rear에 item값을 저장함
    printf("%d enqueued to queue\n", item);
}

void dequeue(Queue* queue) {
    if (isEmpty(queue)) {   //큐가 빈 경우 dequeue를 못하므로 종료
        printf("queue is empty. can't dequeue\n");
        return;
    }
    queue->size--;  //사이즈를 줄여줌
    printf("%d dequeued from queue\n", queue->array[queue->front]); //삭제한다고 먼저 printf한 후 삭제시켜줌
    queue->front = (++queue->front)%(queue->capacity);  //front+1하고 capacity로 나눠줌. 이렇게하면 위와 똑같이 front 또한 0~(capacity-1)값을 순환함
}


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

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

    dequeue(queue);
    dequeue(queue);
    dequeue(queue);
    dequeue(queue);
    dequeue(queue);
    return 0;
}