[자료구조] 2. Queue

2.1 큐란?

FIFO(First in, First out)을 특성으로 하는 자료구조이다.
스택과 달리 먼저 들어온 데이터가 먼저 처리되는 구조이다. 가장 자연스럽게 생각할 수 있는 자료구조 형태이다. 계산대에서 가장 먼저 줄을 선 고객의 계산을 먼저 처리해주는 것도 큐의 예시라고 할 수 있다.

스택의 경우, top변수를 정의한 바 있다. 하지만 큐에선 rear에서 새로운 데이터가 들어오게 되고, front에서 데이터가 처리된다. 그렇기 때문에 두개의 변수를 정의해 큐를 구현해보려고 한다.

2.2 큐의 추상자료형(ADT)

객체 : 0개 이상의 원소를 가지는 유한 선형 리스트
연산 :

init(q): 큐를 초기화

is_full(q)
	if(element의 수 == size) return TRUE;
    else return FALSE;

is_empty(q)
	if(element의 수 == 0) return TRUE;
    else return FALSE;
    
enqueue(q, item)
	if(is_full(q)) return ERROR_OVERFLOW;
    else rear에 item 추가
    
dequeue(q)
	if(is_empty(q)) return ERROR_UNDERFLOW;
    else front의 요소를 제거해 반환

peek(q)
	if(is_empty(q)) return ERROR_EMPTY;
    else front의 요소를 제거하지 않고 반환

2.3 선형큐의 구현

#include <stdio.h>
#include <stdlib.h>
#define max_queue_size 5

typedef int element;

typedef struct {
	element data[max_queue_size];
    int front;
    int rear;
} QueueType;
// 큐를 저장할 배열, 첫번째 요소 위치, 마지막 요소 위치를 하나의 구조체로 구성

// rear : 한 칸 이동 후 데이터 추가(마지막 요소를 가리킴)
// front : 한 칸 이동 후 데이터 삭제(첫 요소의 한 칸 앞을 가리킴)
// |   | a | b | c |   |
// | ^ |   |   | ^ |   |
// | f |   |   | r |   |

// 큐 초기화 함수
void init_queue(QueueType *q){
    q->rear = -1;
    q->front = -1;
}	// 배열의 첫 요소의 위치가 0이므로 두 포인터 모두 -1로 초기화

// 공백 상태 검출 함수
int is_empty(QueueType *q){
    return (q->front == q->rear);
}

// 포화 상태 검출 함수
int is_full(QueueType *q){
    return (q->rear == max_queue_size-1);
}

// 삽입 함수
void enqueue(QueueType *q, int x){
    if(is_full(q)){
        fprintf(stderr, "큐가 포화상태입니다.");
        exit(1);
    }
    q->data[++(q->rear)] = x; 
}

// 삭제 함수
int dequeue(QueueType *q){
    if(is_empty(q)){
        fprintf(stderr, "큐가 공백상태입니다.");
        exit(1);
    }
    int item = q->data[++(q->front)];
    return item;
}

// 큐의 흐름을 잘 이해할 수 있도록 출력 함수 작성
// 중요한 내용 아님
void queue_print(QueueType *q){
    for(int i=0; i<max_queue_size; i++){
        if(i <= q->front || i > q->rear)
            printf(" |");
        else 
            printf("%d|", q->data[i]);
    }
    printf("\n");
}

int main()
{   
    int item = 0;
    QueueType q;
    init_queue(&q);

    enqueue(&q, 1); queue_print(&q);
    enqueue(&q, 2); queue_print(&q);
    enqueue(&q, 3); queue_print(&q);

    dequeue(&q); queue_print(&q);
  	dequeue(&q); queue_print(&q);
    dequeue(&q); queue_print(&q);
    
    return 0;
}

-실행결과-

1| | | | |
1|2| | | |
1|2|3| | |
 |2|3| | |
 | |3| | |
 | | | | |

선형큐의 단점

구현된 선형큐를 살펴보면 rear와 front가 계속하여 증가하는 구조이고, rear가 배열의 끝에 도달하게 되면 배열의 앞쪽이 비어있음에도 불구하고 포화상태로 처리되어 메모리의 낭비가 발생하게 된다. 이를 해결할 수 있는 방법으로 front에서 데이터가 삭제될 때마다 전체 배열의 요소를 앞으로 당겨주는 방법이 있다. 하지만 이러한 방법은 코드가 복잡해질 뿐 아니라 연산 과정이 많아지기 때문에 그리 효율적이라 할 수 없다. 또 다른 방법은 배열을 원형으로 생각하는 방법이다. 다음 절에서 원형큐에 대해 알아보자.

2.4 원형큐의 개념 및 구현

원형큐의 기본적 아이디어는 rear가 배열 끝에 도달하면 다음 index로 0을 가지도록 해 배열의 빈 앞 부분에도 차례로 데이터를 저장할 수 있도록 하는 것이다. 그렇다면 max_queue_size가 5인 문제 상황을 가정해 살펴보자. rear가 5가 될 때 인덱스 값으로 0을 반환해야 한다. 우리는 이 문제를 '%'를 통해 해결한다. % 연산자는 나머지를 반환하기 때문에 인덱스 값을 rear%5로 설정하면 원하는 값을 얻을 수 있다. front의 경우에도 마찬가지로 5에 도달할 수 있는 가능성이 있기 때문에(원형큐이므로) 인덱스 값을 역시 front%5로 설정한다. 결과적으로 rear와 front는 계속 증가하지만 rear%5와 front%5는 0,1,2,3,4 값을 반복적으로 가지게 된다.

이외에도 init_queue(), is_empty(), is_full()가 선형큐와 다르므로 코드를 확인하며 알아보자.

#include <stdio.h>
#include <stdlib.h>

#define max_queue_size 5

typedef int element;
typedef struct {
    int front;
    int rear;
    element data[max_queue_size];
} QueueType;

// rear : 한 칸 이동 후 데이터 추가
// front : 한 칸 이동 후 데이터 삭제
// |   | a | b | c |   |
// | ^ |   |   | ^ |   |
// | f |   |   | r |   |

// 큐 초기화 함수
void init_queue(QueueType *q){
    q->rear = -1;
    q->front = -1;
}

// 공백 상태 검출 함수
int is_empty(QueueType *q){
    return (q->rear == q->front);
}	// rear와 front가 같으면 공백

// 포화 상태 검출 함수
int is_full(QueueType *q){
    return ((q->rear-q->front) >= max_queue_size);
}	// rear와 front의 index 차이가 max_queue_size이면 데이터의 수가 max_queue_size이므로 포화

// 삽입 함수
void enqueue(QueueType *q, element x){
    if(is_full(q)){
        fprintf(stderr, "큐가 포화상태입니다.");
        exit(1);
    }
    q->rear = q->rear+1;
    q->data[q->rear % max_queue_size] = x;
    // 6번째 자료가 삽입된다면, rear=5이므로 데이터는 data[0]에 삽입
}

// 삭제 함수
int dequeue(QueueType *q){
    if(is_empty(q)){
        fprintf(stderr, "큐가 공백상태입니다.");
        exit(1);
    }
    q->front = q->front+1;
    return q->data[q->front % max_queue_size];
}

// 큐의 흐름을 잘 이해할 수 있도록 출력 함수 작성
// 중요한 내용 아님
void queue_print(QueueType *q){
    int front_index = q->front % max_queue_size;
    int rear_index = q->rear % max_queue_size;
    
    if(front_index <= rear_index){
        if(q->rear-q->front < max_queue_size){
            for(int i=0; i<max_queue_size; i++){
                if(i<=front_index || i>rear_index) printf(" |");
                else printf("%d|", q->data[i]);
            }
        }
        else 
            for(int i=0; i<max_queue_size; i++)
                printf("%d|", q->data[i]);
    }
    else{
        for(int i=0; i<max_queue_size; i++){
            if(rear_index < i && i <= front_index) printf(" |");
            else printf("%d|", q->data[i]);
        }
    }
    printf("\n");
}

int main()
{
    QueueType q;
    init_queue(&q);

    enqueue(&q, 1); queue_print(&q);
    enqueue(&q, 2);queue_print(&q);
    enqueue(&q, 3);queue_print(&q);
    dequeue(&q);queue_print(&q);
    dequeue(&q);queue_print(&q);
    enqueue(&q, 4);queue_print(&q);
    enqueue(&q, 5);queue_print(&q);
    enqueue(&q, 6);queue_print(&q);
    dequeue(&q);queue_print(&q);
    
    return 0;
}

-실행결과-

1| | | | |
1|2| | | |
1|2|3| | |
 |2|3| | |
 | |3| | |
 | |3|4| |
 | |3|4|5|
6| |3|4|5|
6| | |4|5|

큐의 경우 front나 rear의 위치, 초기화 값 등에 따라 다양한 설계가 가능하므로 이해하기 쉬운 방식을 택하면 된다.