[5장] 큐

큐에 대한 문제풀이 내용이다.
큐(Queue)란?

 - 한마디로 표현하면 선입선출, FIFO(First In, First Out) 형태의 자료구조이다.

 - 자동차로 비유하면 각 지방도로에서 톨게이트를 거쳐서 인라인하게 데이터가 줄지어 지는것이다. (순차적 처리)

 

앞서 활용한 배열 리스트 형태로 원형 큐를 구현해보자.    ※ 연결 리스트 큐는 6장 연결 리스트를 선행한 뒤 참조

(배열의 인덱스 한계가 있기 때문에 마지막 인덱스에 도달하면 첫번째 인덱스를 가리키게 한다.)

 

원형 배열 큐

#include <stdio.h>

#include <stdlib.h>

#define MAX_QUEUE_SIZE 100

 

typedef int element;

typedef struct{

        element queue[MAX_QUEUE_SIZE];

        int front, rear;

}QueueType;

 

void error(char *message){

        fprintf(stderr,"%s\n",message);

        exit(1);

}

void init(QueueType *q){

        q->front = q->rear = 0;

}

int is_empty(QueueType *q){

        return (q->front == q->rear);

}

int is_full(QueueType *q){

        return (q->front == (q->rear+1) % MAX_QUEUE_SIZE);

}

void enqueue(QueueType *q, element item){

        if(is_full(q))

                error("큐가 포화상태입니다");

        q->rear = (q->rear+1) % MAX_QUEUE_SIZE;

        q->queue[q->rear] = item;

}

element dequeue(QueueType *q){

        if(is_empty(q))

                error("큐가 공백상태입니다");

        q->front = (q->front+1) % MAX_QUEUE_SIZE;

        // 삭제 연산

        // display(q);

        // printf("front = %d rear = %d\n", q->front, q->rear);

        // get_count(q);

        return q->queue[q->front];

}

element peek(QueueType *q){

        if(is_empty(q))

                error("큐가 공백상태입니다");

        return q->queue[(q->front+1) % MAX_QUEUE_SIZE];

}

void display(QueueType *q)

{

        int i,j,count=0;

        if(q->front <= q->rear){

                for(i=q->front+1; i<=q->rear; i++){

                        printf("%d-> ",q->queue[i]);

                        count++;

                }

        }

        else{

                for(i=q->front+1; i<MAX_QUEUE_SIZE; i++){

                        printf("%d-> ",q->queue[i]);

                        count++;

                }

                for(j=0; j<=q->rear; j++){

                        printf("%d-> ",q->queue[j]);

                        count++;

                }

        }

        printf("\n"); 

}

/*

void display(QueueType *q)

{

        int i;

        int count;

        i = q->front+1;

        count = i;

        printf("front = %d rear = %d\n", q->front, q->rear);

        // count = i-1;

        while (count != q->rear){

               count = i % MAX_QUEUE_SIZE;

               printf("%d-> ", q->queue[count]);

               i++;

        }

        printf("\n")

}

*/

element get_count(QueueType *q)

{

        int i,j,count=0;

        if(is_empty(q)){

                printf("현재 큐의 item의 개수 : %d개\n",count);

                return count;

        }

        if(q->front <= q->rear)

                for(i=q->front+1; i<=q->rear; i++)

                        count++;

                else{

                        for(i=q->front+1; i<MAX_QUEUE_SIZE; i++)

                                count++;

                        for(j=0; j<=q->rear; j++)

                                count++;

                }

                printf("현재 큐의 item의 개수 : %d개\n", count);

                return count;

}

void main(){

        QueueType q;

        init(&q);

        // printf("front = %d rear = %d\n",q.front, q.rear);

        enqueue(&q,1);

        enqueue(&q,2);

        display(&q);

        dequeue(&q);

        display(&q);

        get_count(&q);

        // printf("front = %d rear = %d\n",q.front, q.rear);

}

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

    (1) A, B, C, D, E                  (2) E, D, C, B, A

    (3) A, B, C, E, D                  (4) B, A, C, D, E

 

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

 

03. 다음 중 큐에 대한 설명 중 맞는 것은?

    (1) 큐는 LIFO 방식으로 동작한다.

    (2) 큐는 한쪽 끝을 사용하여 입출력을 한다.

    (3) 큐의 삭제연산보다 스택의 삭제연산이 훨씬 쉽다.

    (4) 큐는 원형으로 요소들이 연결되어 있다고 가정할 수 있다.

 

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

(1) 1           (2) 2           (3) 3           (4) 4

 

05. 다음 중 원형 큐에서 공백 상태에 해당하는 조건은? 또 포화 상태에 해당되는 조건은?

    (1) front ==0 && rear == 0

    (2) front == (MAX_QUEUE_SIZE-1) && rear == (MAX_QUEUE_SIZE-1)

    (3) front == rear           // 공백 상태

    (4) front == (rear+1)      // 포화 상태 

 

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

    (1) O(1)                                    (2) O(log2n)

    (3) O(n)                                    (4) O(n2)

 

07. 다음 중 큐가 사용될 수 있는 상황은?

    (1) 후위표기법으로 작성된 수식을 계산하는 경우

    (2) 키보드에서 입력된 키스트로크를 잠시 저장할 때

    (3) 다항식의 항들을 저장할 때

    (4) 미로 문제에서 가장 최근에 지나온 길들을 기억할 때

  

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

    (1) front은 4, rear는 5

    (2) front은 3, rear는 6

    (3) front은 4, rear는 6

    (4) 포화상태가 된다.

 

10. 크기가 10이고 front가3, rear가 9인 원형 큐에서 새로운 항목이 삽입되었을 경우, 배열의 어떤 인덱스에 들어가는가?

    (1) 0                                       (2) 9      

    (3) 8                                       (4)  10

 

11. 공백상태의 연결된 큐에서 새로운 항목이 삽입되었다. 변화되는 포인터는?

(1) front    (2) rear    (3) front와rear     (4) 둘 다 변화되지 않는다.

 

12. 크기가 6인 원형 큐 A에 다음과 같이 삽입과 삭제가 되풀이되었을 경우에 각 단계에서의 원형 큐의 내용(1차원의 내용, front와 rear의 값)을 나타내시오. 

                  front   rear

enqueue(A, 1);     0     1

enqueue(A, 2);     0     2

enqueue(A, 3);     0     3

dequeue(A);        1     3

enqueue(A, 4);     1     4

enqueue(A, 5);     1     5

enqueue(A, 6);     1     0

enqueue(A, 7);     1     0    // 포화 에러

dequeue(A);        2     0

 

14. 원형 큐에서 front와 rear의 초기 값이 0이 아니고 만약 1로 시작하였다면 이것이 문제를 일으키는가?

원형 배열을 이용해서 만든 큐이기 때문에 초기 값은

front와 rear가 0 ~ MAX_QUEUE_SIZE-1 중 아무거나 같기만 하면 상관없다.

 

15. 본문에 나와있는 원형 큐의 C언어 구현에서 peek 연산은 구현되어 있지 않다.

    peek 함수는 원형 큐의 맨 앞에 있는 항목을 삭제하지 않고 읽어오는 연산이다.

    peek 연산을 구현하여 보라.

element peek(QueueType *q){

        if(is_empty(q))

                error("큐가 공백상태입니다");

        return q->queue[(q->front+1) % MAX_QUEUE_SIZE];

}

 

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

element get_count(QueueType *q)

{

        int i,j,count=0;

        if(is_empty(q)){

                printf("현재 큐의 item의 개수 : %d개\n",count);

                return count;

        }

        if(q->front <= q->rear)

                for(i=q->front+1; i<=q->rear; i++)

                        count++;

                else{

                        for(i=q->front+1; i<MAX_QUEUE_SIZE; i++)

                                count++;

                        for(j=0; j<=q->rear; j++)

                                count++;

                }

                printf("현재 큐의 item의 개수 : %d개\n", count);

                return count;

}

 

심화과정 Linked Queue(연결 리스트를 활용한 큐)

#include <stdio.h>

#include <stdlib.h>

typedef int element;

typedef struct QueueNode{

        element item;

        struct QueueNode *link;

} QueueNode;

typedef struct{

        QueueNode *front, *rear;

} QueueType;

void error(char *message){

        fprintf(stderr,"%s\n",message);

        exit(1);

}

void init(QueueType *q){

        q->front = q->rear = 0;

}

int is_empty(QueueType *q){

        return (q->front == NULL);

}

int is_full(QueueType *q){

        return 0;

}

void enqueue(QueueType *q, element item){

        QueueNode *Newnode = (QueueNode *)malloc(sizeof(QueueNode));

        if(Newnode == NULL)

                error("메모리를 할당할 수 없습니다");

        else{

                Newnode->item = item;

                Newnode->link = NULL;

                if(is_empty(q)){

                        q->front = Newnode;

                        q->rear = Newnode;

                }

                else{

                        q->rear->link = Newnode;

                        q->rear = Newnode;

                }

        }

}

element dequeue(QueueType *q){

        QueueNode *NewNode = q->front;

        element item;

        if(is_empty(q))

                error("큐가 비어 있습니다");

        else{

                item = NewNode->item;

                q->front = q->front->link;

                if(q->front == NULL)

                        q->rear = NULL;                              

                free(NewNode);

                return item;

        }

}

element peek(QueueType *q){

        if(is_empty(q))

                error("큐가 비어 있습니다");

        else{

                return q->front->item;

        }

}

 

void display(QueueType *q){

        QueueNode *temp = q->front;

        while(temp != NULL){

                printf("%d-> ",temp->item);

                temp = temp->link;

        }

        printf("\n");

}

 

element get_count(QueueType *q){

        QueueNode *temp = q->front;

        int count=0;

        while(temp != NULL){

                count++;

                temp = temp->link;

        }

        printf("현재 item의 개수 : %d개\n", count);

        return count;

}

void main(){

        QueueType q;

 

        init(&q);

        enqueue(&q, 1);

        enqueue(&q, 2);

        enqueue(&q, 3);

        display(&q);

        get_count(&q);

        dequeue(&q);

        display(&q);

        get_count(&q);

}