C언어로 쉽게 풀어 쓴 자료구조 개정 2판 6장 큐 연습문제

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

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

3. 다음 중 큐에 대한 설명 중 맞는 것은?
(4) 큐는 원형으로 요소들이 연결되어 있다고 가정할 수 있다.
(1) FIFO (2) 양쪽 끝

4. 크기가 8인 원형 큐에서 front가 3이고 rear가 5라고 하면 현재 원형 큐에 저장된 요소들의 개수는?
index :  [0]  [1]  [2]  [3]  [4]  [5]  [6]  [7]
pointer :                f          r 
value :   x    x    x    x    o    o   x     x
cf. 원형 큐에서 front는 empty와full을 판별하기 위해 맨 앞 요소의 하나 앞(공백)을 가리킴

5. 다음 중 원형 큐에서 공백 상태에 해당하는 조건은? 또 포화 상태에 해당하는 조건은?
공백 : (3) front == rear // (1)은 공백은 맞는데 1개를 넣고 1개를 빼면 둘 다 1을 가리키면서 공백상태이기 때문에 (1)은 공백상태의 한 종류라 할 수 있음
포화 : (4) front == (rear+1) // 교재 참고

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

7. 다음 중 큐가 사용될 수 있는 상황은?
(2) 키보드에서 입력된 키스트로크를 잠시 저장할 때
풀이 : 키보드는 먼저 입력한 문자들이 모니터에 먼저 출력되므로 큐의 특성(FIFO)에 들어 맞는다고 할 수 있음. ex) 자료구조 -> ㅈ ㅏ ㄹ ㅛ ㄱ ㅜ ㅈ ㅗ

8.

9. 크기가 10이고 front가 3, rear가 5인 원형 큐에서 새로운 항목이 삽입됐을 경우. front와 rear의 새로운 값은?
front는 3, rear는 6
풀이 :
before)
index : [0] [1] [2] [3] [4] [5] [6] [7] [8] [9]
pointer :            f        r
value :  x   x   x   x   o   o  x   x   x   x

after)
index : [0] [1] [2] [3] [4] [5] [6] [7] [8] [9]
pointer :            f             r
value :  x   x   x   x   o   o  o   x   x   x

10. 크기가 10이고 front가 3, rear가 9인 원형 큐에서 새로운 항목이 삽입될 경우, 배열의 어떤 인덱스에 들어가는가?
(1) 0
풀이 : 꽉 차서 0부터(?)

11.

12. 크기가 6인 원형 큐 A에 다음과 같이 삽입과 삭제가 되풀이되었을 경우에 각 단계에서의 원형 큐의 내용을 나타내어라.
(크기가 6이면 empty, full을 판별하는 데 쓰이는 [0]을 제외하여 원형큐를 7칸으로해서 인덱스가 0~6로 설정되게 해야 크기가 6?) 그렇다고 가정하면,
인덱스가 0~5라면 full로 인한 error가 한번 더 나타날듯

front : 0 / 0 / 0 / 1 / 1 / 1 / 1 / 1(full) / 2
rear : 1 / 2 / 3 / 3 / 4 / 5 / 6 / 6(full) / 6
value :
[1]에 1 / [1]에 1, [2]에 2 / [1]에 1, [2]에 2, [3]에 3 / [2]에 2, [3]에 3 / [2]에 2, [3]에 3, [4]에 4 / [2]에 2, [3]에 3, [4]에 4, [5]에 5 / [2]에 2, [3]에 3, [4]에 4, [5]에 5, [6]에 6 / full / [3]에 3, [4]에 4, [5]에 5, [6]에 6 

15. 만약 원형 큐의 C언어 구현에서 저장하려는 항목이 정수가 아니고 다음과 같은 구조체라면 소스의 어떤 부분들이 변경되어야 하는가?

typedef struct {

char name[10]; int student_no; } element; typedef struct { element queue[100]; int front, rear; }QueueType; void enqueue(QueueType *q, char p, int r) { *q->queue[q->rear].name = p; q->queue[q->rear].student_no = r; }

[출처] C언어로 쉽게 풀어쓴 자료구조 6장 큐|작성자 chermy013

19. 원형 큐에 존재하는 요소의 개수를 반환하는 연산 get-count를 추가
int get_count(QueueType *q)
{
    int count = 0;
    if((q->rear) == (q->front)) // 공백이면 count는 0이므로
        return count;
    else
    count = (q->rear) - (q->front) ;
    return count;
}
front가 rear보다 클 때가 있나?

21.