[자료구조] 큐(Queue) in C

추상 데이터 타입 큐

큐는 먼저 들어올 데이터가 먼저 나가는 구조로 일명 줄서기 구조이다. 이러한 특성을 선입선출(FIFO: First-In First-Out) 이라고 한다. 데이터 삽입은 맨 뒤 삭제는 맨 앞에서 일어나게 된다. 스택과 달리 삽입과 삭제가 서로 다른 곳으로 나간다.

큐의 특징 및 사용 예시

특징: 큐는 스택과 달리 삽입, 삭제가 양 끝단에서 일어나기 때문에 큐에서는 이에 대한 변수가 2개가 필요하다. 삽입이 일어나는 (후단)rear 이고 삭제가 일어나는 곳 (전단)front 라고 한다.

예시: 큐는 실생활에서 많이 볼 수 있다. 매표소의 대기열, 프린터 인쇄 과정, 통신 데이터 패킷 모델링 등 여러 곳에서 볼 수 있다. 이러한 큐가 적용된 모델을 큐잉 모델이라고도 한다.

큐의 연산 및 구현

큐는 enqueue라는 삽입 연산과 dequeue라는 삭제 연산이 핵심이다.

init_queue(size)

최대 크기가 size인 배열을 초기화한다. rear와 front는 -1로 저장한다.

void init_queue(QueueType *q)
{
	q->rear = -1;
    q->front = -1;
}

is_empty

큐가 비어있는지 확인한다. 큐의 front와 rear 가 같으면 큐가 비어있다.

int is_empty(QueueType *q)
{
	return q->front == q->rear;
}

is_full

큐가 가득찼는지 확인한다.
큐의 size - 1 이 rear 와 같을 경우 포화상태이다.

int is_full(QueueType *q)
{
	return q->rear == MAX_QUEUE_SIZE -1;

enqueue(item)

큐의 후단에 item을 삽입한다.
rear을 1증가 시키고 해당 위치에 항목을 삽입한다.

void enqueue(QueueType *q, element item)
{
	if(is_full(q)) // 포화 상태 확인
    	return;
    q->data[++(q->rear)] = item;
}

dequeue

큐의 전단에 item을 삭제한다. front를 1증가 시켜 삭제하고 항목을 반환한다.

여기서 주의해야 할 점은 front가 하나 앞의 항목을 가리키기 때문에 front + 1 의 위치에 있는 항목이 우리가 삭제하고자 하는 항목이다. 따라서 front를 증가시켜 항목을 삭제하고 이를 반환한다.

element dequeue(QueueType *q)
{
	if(is_empty(q)) // 공백 상태 확인
    	return -1;
    return q->data[++(q->front)];

전체 코드(선형 큐)

앞서 구현한 코드 및 전체코드는 선형 큐를 예시로 든 코드이다.

#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;

// 에러 출력 함수
void error(char *message)
{
    fprintf(stderr, "%s\n", message);
}

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

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

// 포화 상태 확인 함수
int is_full(QueueType *q)
{
    return q->rear == MAX_QUEUE_SIZE - 1;
}

// 삽입 함수
void enqueue(QueueType *q, element item){
    if(is_full(q)){
        error("큐 포화 에러");
        return;
    }
    q->data[++q->rear] = item;
}

// 삭제 함수
element dequeue(QueueType *q){
    if(is_empty(q)){
        error("큐 공백 에러");
        return -1;
    }
}

void queue_print(QueueType *q){
    for(int i = 0; i < MAX_QUEUE_SIZE; i++)
        if(i <= q->front || i > q->rear)
            printf("\t|\t");
        else
            printf("%d\t|\t", q->data[i]);

    printf("\n");
}

int main(void){
    QueueType q;

    init_queue(&q);

    enqueue(&q, 10); queue_print(&q);
    enqueue(&q, 20); queue_print(&q);
    enqueue(&q, 30); queue_print(&q);

    dequeue(&q); queue_print(&q);
    dequeue(&q); queue_print(&q);
    dequeue(&q); queue_print(&q);

    return 0;
}

⭐ front가 하나 앞을 가리키는 이유

queue에서 front와 rear 을 -1 로 설정하는데 front는 현재 자신이 가리키고 있는 값보다 하나 앞을 가리키게 된다.

front가 실제 가장 앞 원소를 가리키게 되면 첫 원소를 삽입시 또는 첫 원소 삭제시에 front 또는 rear를 동시에 바꿔주어야 하기 때문에 구현이 까다롭다.
따라서 front를 실제 가리키는 값보다 하나 앞에 두어 값을 설정한다.

원형 큐? 선형 큐?

앞서 구현한 우리가 일반적으로 아는 배열의 구조로 구현한 큐는 선형 큐이다. 그러면 원형 큐는 무엇일까?

앞서 배웠던 선형 큐는 한가지 문제점이있다. 값 삭제시에 인덱스가 증가하고 값 삽입시에도 인덱스가 증가하기 때문에 삭제시 빈공간을 사용하지 못한다.

다음과 같이 0 과 1 인덱스의 공간이 비어있음에도 더이상 값을 넣을 수 없다!

원형큐

원형큐는 이러한 선형큐의 문제점을 개선한 자료구조이다. 배열을 하나의 원이라고 생각하여 처음과 끝을 연결시켜 사용한다. 개념상에서 원형으로 배열의 인덱스를 변화시켜 시계방향으로 회전하는 것이 특징이다. 이러한 방식으로 작동하면 빈 공간을 효과적으로 줄일 수 있다.

원형 큐 구현

원형큐에서는 front와 rear을 0으로 설정하고 원형큐의 마지막 공간 하나는 비워둔다. 공간을 비워두는 이유는 포화상태와 공백상태를 비교하기 위해서이다. 다음 코드를 보자.

⭐시계방향으로 회전 시키는 방법

(i + 1) % MAX_SIZE와 같은 방법으로 하면 배열을 시계방향으로 회전시킬 수 있다. MAX_SIZE는 배열의 크기이다.

init_queue

큐를 초기화 한다.

void init_queue(QueueType *q)
{
	q->front = q->rear = 0;
}

is_empty

공백 상태는 front와 rear이 같을 경우를 말한다.

int is_empty(QueueType *q)
{
	return q->front == q->rear;
}

is_full

포화 상태는 rear에 +1을 할 때 front와 같은 경우를 말한다. 여기서 +1을 할때 시계 방향으로 회전시켜서 구현한다.

int is_full(QueueType *q)
{
	return (q->rear + 1) % MAX_QUEUE_SIZE == q->front;
}

enqueue

rear를 시계방향으로 1 증가시킨후 항목을 추가한다.

void enqueue(QueueType *q, element item)
{
	if(is_full(q))
  		error("포화 상태 오류");
  	q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
  	q->data[q->rear] = item;
}

dequeue

front를 1 시계방향으로 1 증가시켜 항목을 삭제한다.

element dequeue(QueueType *q)
{
  	if(is_empty(q))
  		error("공백 상태 오류");
  	q->front = (q->front + 1) % MAX_QUEUE_SIZE;
  	return q->data[q->front];

전체 코드(원형 큐)

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

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

void error(char *message){
    fprintf(stderr, "%s\n", message);
    exit(1);
}

void init_queue(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->data[q->rear] = item;
}

element dequeue(QueueType *q)
{
    if (is_empty(q))
        error("공백 상태 오류");
    q->front = (q->front + 1) % MAX_QUEUE_SIZE;
    return q->data[q->front];
}

void queue_print(QueueType *q)
{
    printf("Queue front: %d rear: %d\n|", q->front, q->rear);
    int i = q->front;
    while (i != q->rear)
    {
        i = (i + 1) % MAX_QUEUE_SIZE;
        printf(" %d |", q->data[i]);
    }
    printf("\n");
}

int main(void)
{
    QueueType queue;
    element item;

    init_queue(&queue);
    printf("--데이터 추가 단계--\n");
    while (!is_full(&queue))
    {
        printf("정수를 입력하시오:");
        scanf("%d", &item);
        enqueue(&queue, item);
        queue_print(&queue);
    }
    printf("큐는 포화상태입니다.");

    printf("--데이터 삭제 단계--\n");
    while (!is_empty(&queue))
    {
        item = dequeue(&queue);
        printf("꺼내진 정수 %d \n", item);
        queue_print(&queue);
    }

    printf("큐는 공백상태입니다.");
    return 0;
}

마무리

오늘은 큐에 대해 알아보고 선형큐와 원형큐 차이를 파악하고 원형큐를 구현해 보았다. 원형 큐의 시계방향으로 회전하는 개념은 배열의 인덱스 뿐 아니라 다양한 곳에서 사용되므로 잘 기억해 두자.

📕 참고 문헌

다음의 책을 참고했습니다.
C언어로 쉽게 풀어쓴 자료구조 [ 개정3판 ]
천인국, 공용해, 하상호 저 | 생능출판사 | 2021년 08월 20일