[c언어로 쉽게 풀어쓴 자료구조] 5장 큐 문제 풀이

1. 문자 A,B,C,D,E를 큐에 넣었다가 다시 꺼내어 출력하면 어떻게 되는가?

→ A,B,C,D,E

 

2. 원형 큐에서 front가 3이고 rear가 5라고 하면 현재 원형 큐에 저장된 요소들의 개수는?

→ 2개가 들어있다. (rear - front =  5-3 =2)

 

3. 10,20,30,40,50 을 큐ㅔ 넣었다고 가정하고 3개의 항목을 삭제하였다, 남아 있는 항목은?

→ (40, 50) 

      큐는 FIFO이므로 앞에 3개 먼저 삭제됨.

 

4. 다음 중 원형 큐에서 공백상태에 해당하는 조건은? 

→ front == rear 

    원형 큐에서 front와 rear가 같으면 공백 상태임

 

5.크기가 10이고 front가 3, rear가 5인 원형 큐에서 새로운 항목이 삽입되었을 경우, front와 rear의 새로운 값은?

→ front = 3, rear = 6

     새로운 항목 삽입 시 front는 그대로,rear는 1 증가한다.

 

6. 원형 큐에서 (a)에서 (c)까지의 연산을 차례로 수행하고 수행이 완료된 후 큐의 상태를 그려라. 현재 front는 0이고 rear는 2라고 하자.

  

7. 큐에 항목들을 삽입하고 삭제하는 연산은 시간 복잡도가 어떻게 되는가?

→ O(1)

    (a) 삽입, 삭제는 rea와 front를 1씩 증가하는 연산만 필요함

 

 

8. 원형 큐에 존재하는 요소의 개수를 반환하는 연산 get_count를 추가 하여 보라. c언어를 이용하여 구현하여 보라.

int get_count(queue * q){
    if (q-> rear >= q->front);
        return (q -> rear - q->front);
    else    
        return (SIZE - (q->front - q-> rear));
}

 

9. 2개의 스택을 사용하여 큐를 구현할 수 있을까? 2개의 스택을 사용하여 큐를 구현해보자. 입력이 들어오면 스택 #1에 넣는다. 출력 요청이 들어오면 스택 #2에서 요소를 꺼낸다. 스택 #2가 비어 있을 때는 스택 #1의 모든 요소를 꺼내서 스택 #2에 넣는다. 프로그램으로 작성해보자

int main(void){
    stack* s1 = (stack*)malloc(sizeof(stack));
    stack* s2 = (stack*)malloc(sizeof(stack));
    init(s1); init(s2);

    while (1){
        init num;
        printf("deque(0), enque(1): ");
        scanf("%d", &num);

        if(num){
            printf("value: ");
            scanf("%d", &num);
            push(s1, num);
        }
        else{
            if (empty(s2)){
                while (!empty(s1))
                    push(s2,pop(s1));
            }
            printf("deque: %d\n",pop(s2));
        }
    }
}

 

 

10. 피보나치 수열을 효과적으로 계싼하기 위하여 큐를 이용할 수 있다. 만일 피보나치 수열을 순환에 의하여 계산하게 되면 경우에 따라서는 많은 순환 함수의 호출에 의해 비효율적일 수 있다. 이를 개선하기 위하여 큐를 사용하는데 큐에는 처음에는 F(0)와 F(1)의 값이 들어가 있어 다음에 F(2)를 계산할 때 F(0)를 큐에서 제거한다. 그 다음에 계산된 F(b)를 다시 큐에 넣는다. 피보나치 수열은 다음과 같이 정의 된다 큐를 이용하여 피보나치 수열을 계산 하는 프로그램을 작성하라

F(0) = 0, F(1) =1

F(n) = F(n-1) + F(n-2)

int fib(int n){ // N번째 피보나치 값을 반환하는 함수
    queue* q = (queue*)malloc(sizeof(queue));
    init(q);
    enque(q,0); enque(q,1);

    for (int i =1l i <=n; i++)
        enque(q, deque(q) + peek(q));
    return peek(q);

}

 

11. 회문(palindrome)이란 앞뒤 어느 쪽에서 읽어도 같은 말,구,문 등을 의미한다. 예를 들어 "eye","madam","radar"등이다. 여기서 물론 구두점이나 스페이스,대소문자등은 무시하여야한다. 덱을 이용하여 주어진 문자열이 회문인지 아닌지를 결정하는 프로그램을 작성하라. 다음 그림을 참조

// # 11
int check(char* in){ // 회문이면 1, 아니면 0을 반환하는 함수
    queue* q = (queue*)malloc(sizeof(queue));
    init(q);

    while (*in){
        char ch = *in++;
        if(isalpha(ch)) // 문자가 알파벳인 경우에만
            add_front(q, tolower(ch)); // 소문자로 변환 후 front에 삽입
    }
    
    while(!empty(q)){
        char front = delete_front(q);
        if(empty(q)) // front에서 deque 후에 원소가 없는 경우 회문이므로 1 반환
            return 1;
        char rear = delete_rear(q);

        if(front != rear) // front에서의 deque값과, rear에서의 deque값이 다르면 0 반환
            return 0;
    }
    return 1;
}

 

12. 테스크 스케줄링 알고리즘으로 A-Steal 알고리즘이 있다. A-Steal알고리즘에서 각각의 CPU는 자신이 실행할 태스크가 저장된 덱을 가지고 있다. 하나의 CPU가 자신의 태스크를 종료했다면 다른 CPU가 실행할 태스크를 훔쳐서 실행할 수 있다.이때, 다른 CPU의 덱의 끝에 있는 요소를 가져온다,. 간단하게 A-Steal알고리즘을 구현해보자

 

 

 

참고 : 

https://velog.io/@jsa4021/C%EC%96%B8%EC%96%B4%EB%A1%9C-%EC%89%BD%EA%B2%8C-%ED%92%80%EC%96%B4%EC%93%B4-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%97%B0%EC%8A%B5%EB%AC%B8%EC%A0%9C-4%EC%9E%A5-qzopqyws