[부스트 코딩 뉴비 챌린지 2020] week3_미션03

✔︎ 문제 3. Queue를 만들어보자!

 

1. 미션 제목
Queue 를 만들어 보자!

 

2. 지시문
배열을 이용하여 Queue 를 만들어 보자.
특정 업무를 할 때, 우리는 일을 들어온 순서대로 해야할 때가 있다. 은행 업무를 예를 들어보자. 은행업무를 보기 위한 고객들이 10명이 있다고 치고, 각자 대기표가 있다. 그럼 은행원들은 각자 업무가 끝나면 대기한 고객을 순서대로 뽑아야 할 것이다. 이때 필요한 것이 Queue 이다. (1) 대기표를 뽑는다 (Queue 에 데이터를 삽입). (2) 대기인원을 보여준다 (queue 에 쌓여있는 데이터 조회). (3) 순서대로 대기인원을 호출한다 (queue 를 하나씩 pop 한다).

- Queue 자료구조를 array를 이용해 구현
1. add (1), pop (2), display (3), quit (4) 기능 구현
2. 입력 한 옵션 (1, 2, 3, 4) 에 따라 switch 문을 사용하여 각각의 기능을 수행하도록 구현
3. 필요한 함수 목록: insert(), delete(), display()
    - 각 함수의 파라미터는 필요하면 정의하기
4. add() 함수의 정의
    - queue 가 꽉찼는지 확인 (Queue 의 max 크기는 10으로 정의), queue 가 꽉찼으면 “Queue가 꽉 찼습니다.” 를 출력
    - queue 에 삽입이 가능하면, 값을 입력 받아 queue 배열에 삽입 (hint: front, rear 변수를 사용하여 queue 의 현재 위치를 저장한다)
5. pop() 함수의 정의
    - queue 가 비었는지 확인, 비었으면 “Queue가 비었습니다.” 를 출력
    - queue 가 비어있지 않으면, 가장 먼저 들어온 순서로 값을 하나 가져와 출력 (hint: front 변수값 조정 필요)
6. display() 함수의 정의
    - 반복문을 사용하여 배열의 모든 요소를 출력 (hint: front, rear 변수 범위로 배열값을 출력)

 

TODO: 여기서 출력 예시 보여주기

 

3. 핵심 개념 (키워드 제시)
#배열 #Queue #switch문 #반복문 #표준입출력

 

4. 부가 설명 (만약 존재한다면)
- Queue: https://en.wikipedia.org/wiki/Queue_(abstract_data_type)
- switch: https://docs.microsoft.com/ko-kr/cpp/c-language/switch-statement-c?view=vs-2019
- 표준입출력: https://www.tutorialspoint.com/cprogramming/c_input_output.htm

Queue (abstract data type) - Wikipedia

:::no-loc(switch)::: Statement (C)

C - Input and Output - Tutorialspoint

 

문제 풀이

#include <stdio.h>
#include <cs50.h>

#define MAX 10

int queue_array[MAX];
int rear = -1;
int front = -1;

void insert();
void delete();
void display();

int main(void){
     int num;

    while(1){
        num = get_int("원하는 기능을 숫자로 작성하시오.\n(1) add\n(2) pop\n(3) display\n(4) quit\n입력: ");

        switch(num) {
            case 1: //add
                insert();
                break;
            case 2: //pop
                delete();
                break;
            case 3: //display
                display();
                break;
            case 4: //quit
                return 1;
            default:
                printf("1 ~ 4 사이의 수를 입력하세요.");
        }
    }

    return 0;
}


void insert(){
    int add_item;

    //현재 꼬리의 위치 확인
    if(rear == MAX-1){
        printf("Queue가 꽉 찼습니다.\n");
    }else{
        if(front == -1) //초기값
            front++;

        printf("삽입할 값 : ");
        scanf("%d", &add_item);
        rear++;
        queue_array[rear] = add_item;   //꼬리에 값을 넣음
    }

}

void delete(){
    if(front == -1 || front > rear){
        printf("Queue가 비어있습니다.\n");
        return ;
    }else{
        printf("Queue에서 %d가 삭제되었습니다.\n", queue_array[front]);
        front++;
    }
}

void display(){
    int i;
    if(front == -1){
        printf("Queue가 비어있습니다.\n");
    }else{
        printf("Queue: ");

        for(i = front; i <= rear; i++)
            printf("%d ", queue_array[i]);

        printf("\n");
    }

}

 

add	empty	1	2	3	4	5	6	7	8	9	10
front	-1	0
rear	-1	0	1	2	3	4	5	6	7	8	9

 

(1) void insert()

1. 만일 rear == 9 (MAX)라면,

2.    queue가 꽉 찼다고 출력

3. 만일 front == -1 라면, (1의 만족을 충족하지 않으므로 queue에 값을 넣을 수 있음)

4.    front++ (front = 0) 하여 queue에 값이 있는 사태가 됨

5.    queue에 추가할 값을 scanf함

6.    rear++

7.    queue[rear]번째에 입력받은 값을 넣음

 

delete	empty	1	2	3	4	5	6	7	8	9	10
front	-1	현재값+1
rear	-1	0	1	2	3	4	5	6	7	8	9

queue에 1, 2, ... 10개의 숫자가 있는 경우에 delete()로 하나를 삭제한 경우

(2) void delete()

1. 만약 front == -1 이라면 (queue가 빈 상태)

2.    queue가 비어있다고 출력

3.    함수 종료

4. queue에 값이 들어있다면,

5.    queue[front]값이 삭제된다고 알려줌

6.    front++ 하여 front 뒤의 값(front+1)을 헤더로 저장함

 

(3) void display()

1. 만일 front == -1라면,

2.     queue가 비어있다고 알림

3. 그게 아니라면, for i를 from front to rear 까지 돌며 queue[i]을 출력