(C) 자료구조 - 큐의 이해 / 순차 큐의 구현

1. 큐의 개념과 구조

큐(Queue)는 삽입과 삭제의 위치와 방법이 제한된 유한 순서 리스트라는 점은 스택과 같지만, 리스트의 한 쪽 끝에서는 삽입 작업만 이루어지고 반대쪽 끝에서는 삭제 작업만 이루어진다는 점이 스택과 다르다.

 

큐는 삽입된 순서대로 먼저 삽입된 데이터가 먼저 삭제되는 선입선출(FIFO: First In Fisrt Out) 구조로 운영된다.

 

큐는 한쪽 끝을 front(머리)로 정해 삭제 연산만 수행하고, 다른 쪽 끝을 rear(꼬리)로 정하여 삽입 연산만 수행하는 제한 조건을 가진 자료구조이다.

 

<큐의 FIFO 구조>

- front : 가장 먼저 큐에 삽입된 첫 번째 원소 -> 삭제 연산 : deQueue

- rear : 큐에 가장 늦게 삽입된 마지막 원소 -> 삽입 연산 : enQueue

 

< 스택과 큐에서의 삽입과 삭제 연산 비교>

항목 →	삽입	연산	삭제	연산
자료구조 ↓	연산자	삽입 위치	연산자	삭제 위치
스택	push	top	pop	top
큐	enQueue	rear	deQueue	front

 

---

2. 큐의 구현

큐에 대해 정의한 추상 자료형을 순차 자료구조나 연결 자료구조 방식으로 구현할 수 있다.

 

2-1. 순차 자료구조를 이용한 큐의 구현

순차 자료구조를 이용하여 순차 큐와 원형 큐를 구현한다.

 

1) 순차 큐

순차 자료구조인 1차원 배열을 이용하여 순차 큐(Sequential Queue)를 구현한다.

 

- 순차 자료구조를 이용해 순차 큐 구현하기

0) 헤더파일

#define Q_SIZE 4
typedef char element;                // 큐 원소(element)의 자료형을 char로 정의
 
typedef struct {
    element queue[Q_SIZE];        // 1차원 배열 큐 선언
    int front, rear;
} QueueType;

 

1) 공백 순차 큐 생성

// 공백 순차 큐를 생성하는 연산
QueueType* createQueue(void) {
    QueueType* Q;
    Q = (QueueType*)malloc(sizeof(QueueType));
    Q->front = -1;            // front 초깃값 설정
    Q->rear = -1;            // rear 초깃값 설정
    return Q;
}

 

2) 순차 큐의 공백 상태 검사

// 순차 큐가 공백 상태인지 검사하는 연산
int isQueueEmpty(QueueType* Q) {
    if (Q->front == Q->rear) {
        printf("Queue is empty! \n\t ");
        return 1;
    }
    else return 0;
}

3) 순차 큐의 포화 상태 검사

// 순차 큐가 포화 상태인지 검사하는 연산
int isQueueFull(QueueType* Q) {
    if (Q->rear == Q_SIZE - 1) {
        printf(" Queue is full! \n\t ");
        return 1;
    }
    else return 0;
}

 

4) 순차 큐의 rear에 원소 삽입

-> 마지막 원소의 다음 자리에 삽입해야 한다.

1. 마지막 원소의 인덱스, 즉 rear값을 하나 증가시켜 삽입할 자리를 준비한다.

2. 수정한 rear값에 해당하는 배열 원소 Q[rear]에 item을 저장한다.

// 순차 큐의 rear에 원소를 삽입하는 연산
void enQueue(QueueType* Q, element item) {
    if (isQueueFull(Q)) return;            // 포화 상태이면, 삽입 연산 중단
    else {
        Q->rear++;
        Q->queue[Q->rear] = item;
    }
}

 

5) 순차 큐의 front에서 원소 삭제

-> 가장 앞에 있는, 즉 가장 먼저 큐에 들어와 있는 원소부터 삭제해야 한다.

1. front 위치를 한 자리 뒤로 옮김으로써 큐에 남아 있는 원소 중에서 첫 번째 원소의 위치로 이동하여 삭제할 자리를 준비한다.

2. front 자리의 원소를 삭제하여 반환한다.

// 순차 큐의 front에서 원소를 삭제하는 연산
element deQueue(QueueType* Q) {
    if (isQueueEmpty(Q)) return;        // 공백 상태이면, 삭제 연산 중단
    else {
        Q->front++;
        return Q->queue[Q->front];
    }
}

 

6) 순차 큐의 가장 앞에 있는 원소 검색

// 순차 큐의 가장 앞에 있는 원소를 검색하는 연산
element peekQ(QueueType* Q) {
    if (isQueueEmpty(Q)) return;        // 공백 상태이면 연산 중단
    else return Q->queue[Q->front + 1];
}

 

 7) 순차 큐의 원소 출력

// 순차 큐의 원소를 출력하는 연산
void printQ(QueueType* Q) {
    int i;
    printf(" Queue : [");
    for (i = Q->front + 1; i <= Q->rear; i++)
        printf("%3c", Q->queue[i]);
    printf(" ]");
}

 

- 예제 : 순차 큐 연산

#include "queueS.h"
 
int main(void) {
    QueueType* Q1 = createQueue();        // 큐 생성
    element data;
    printf("\n ***** 순차 큐 연산 ****** \n");
    printf("\n 삽입 A>>"); enQueue(Q1, 'A'); printQ(Q1);
    printf("\n 삽입 B>>"); enQueue(Q1, 'B'); printQ(Q1);
    printf("\n 삽입 C>>"); enQueue(Q1, 'C'); printQ(Q1);
    data = peekQ(Q1); printf(" peek item : %c \n", data);
    printf("\n 삭제 >>"); data = deQueue(Q1); printQ(Q1);
    printf("\t삭제 데이터 : %c", data);
    printf("\n 삭제 >>"); data = deQueue(Q1); printQ(Q1);
    printf("\t\t삭제 데이터 : %c", data);
    printf("\n 삭제 >>"); data = deQueue(Q1); printQ(Q1);
    printf("\t\t삭제 데이터 : %c", data);
 
    printf("\n 삽입 D>>"); enQueue(Q1, 'D'); printQ(Q1);
    printf("\n 삽입 E>>"); enQueue(Q1, 'E'); printQ(Q1);
 
    getchar(); return 0;
}