[ C언어 ] 자료구조_큐(Array)

[ C언어 ] 자료구조_스택(배열)

저번 배열을 사용해서 스택을 구현하였는데 이번에는 큐 를 배열을 사용해서 구현해 보겠습니다.

 

1. 큐 자료구조 설명

큐 는 선입선출(FIFO) 구조로 스택은 마지막에 들어온 데이터를 먼저 내보내지만 큐는 들어온 순서대로 내보내는 자료구조입니다.

 

일상생활에서는 대기줄과 동일한 구조로 흔히 은행에서 들어온 순서대로 번호표를 제공하고 순서대로 일을 처리하게 되죠 이때 시스템에서 큐 를 사용하여 관리를 하는 것이죠

 

2. 큐 자료구조 구현 방법(배열)

배열을 사용해서 구현하는 방법은 여러 가지가 있겠지만 여기서는 3가지 방식을 살펴보고 가장 효율적인 방식을 실제로 구현해 보겠습니다.

 

1. 선형 큐 v1

선형 큐는 데이터를 삽입할 때 index 뒤쪽에서 를 1씩 증가시키면서 삽입한 뒤 꺼낼때는 반대로 index 를 앞에서 1씩 감소시키는 방식 입니다. 이런경우 구현은 간단하지만 결국에는  뒷쪽에 공간은 남아있더라도 앞쪽에서 포화상태가 되기 때문에 데이터를 담을 수 없게 되는 문제가 있습니다.

 

2. 선형 큐 v2

두 번째 버전에서는 위 선형 큐의 단점을 보완해서 데이터를 꺼내고 나면 모든 데이터를 앞으로 한 칸씩 이동시키는 방식으로 공간을 확보할 수 있습니다.

 

하지만 문제는 시간복잡도가 증가한다는 것입니다. 데이터를 꺼낼 때마다 한 간씩 이동해야 하기 때문에 O(n)의 시간이 걸리게 됩니다.

 

3. 원형 큐

위 문제를 해결하기 위해서는 v1 방식에서 데이터 포화상태가 되면 다시 앞쪽으로 넘어가서 데이터를 담으면 됩니다.

 

그림으로 살펴보겠습니다. 위 이미지는 index를 원형으로 표현하였는데요 여기서 index의 번호는 개념적으로 중요하지 않습니다.

물론 배열에 값을 담고 꺼낼 때는 index를 통해 접근을 해야 하지만 큐의 시작과 끝 index는 값을 담고 꺼낼 때마다 변하기 때문입니다.

 

원형 큐에서 중요한 요소는 큐의 앞부분과 뒷부분입니다. 앞부분을 front 뒷부분을 rear이라고 칭하겠습니다.

그리고 원향 큐에서는 반드시 하나의 index는 비워 놓아야 합니다. 이유는 이후에 설명하겠습니다.

 

1번

초기에는 값이 하나도 없는 공백 상태입니다.

공백 상태를 구분하기 위해서는 front의 index와 rear의 index 번호가 동일하다는 것을 통해 구분할 수 있습니다.

 

2, 3, 4번

이제 값을 넣어보겠습니다. 먼저 rear 의 index를 1 증가시킨 후 해당 index에 값을 삽입합니다.

위 과정을 동일하게 3번 반복시킴으로 큐에 순서대로 1, 2, 3 이 들어갔습니다.

 

5번

이제 들어간 값을 하나 꺼내보겠습니다.

큐 자료구조는 선입선출 구조이니 처음에 들어간 값 1을 꺼내야 합니다. 이를 위해 front의 index를 1 증가시키면 처음에 넣은 값의 index에 위치하게 됩니다. 그럼 해당 index의 값을 꺼낼 수 있게 됐습니다.

 

n번

이런 방식으로 데이터를 담고 꺼낼 수 있지만 배열의 크기는 한정적이기 때문에 포화상태가 발생할 수 있습니다.

이때 포화상태인지 구분하기 위해서는 front의 다음 index 가 rear이라면 포화상태입니다.

 

여기서 위에서 하나의 index는 비워야 한다고 했는데 이유는 공백상태와 포화상태를 구분하기 위함입니다.

 

지금까지 배열을 사용하여 큐를 구현하는 방법을 3가지 살펴보았는데요

1번 방밥은 메모리상 비 효율적이기 때문에 절대 사용하면 안 됩니다.

2번 방법은 값을 꺼내면 모든 값을 1칸씩 앞으로 이동시키기 때문에 메모리를 효율적으로 사용할 수 있습니다.

하지만 큐의 길이가 길어질수록 값을 꺼낼 때 시간이 오래 걸리게 됩니다.

3번째 방법은 무조건 index 하나를 비워 놓아야 하지만 1, 2번 의 장점을 모두 가지고 있기 때문에 가장 효율적인 방식입니다.

 

그러면 가장 효율적인 3번 방식을 실제로 구현해 보겠습니다.

 

Queue.h

#define QUEUE_SIZE 10

typedef int element;

typedef struct queue {
	element data[QUEUE_SIZE];
	int front;
	int rear;
}queue;

void init(queue* q);

int isEmpty(queue* q);

int isFull(queue* q);

int enqueue(queue* q, element data);

element dequeue(queue* q);

void queue_print(queue* q);

 

Queue.c

#include <stdio.h>
#include "Queue.h"

void init(queue* q)
{
	q->front = 0;
	q->rear = 0;
}

int isEmpty(queue* q)
{
	return q->front == q->rear;
}

int isFull(queue* q)
{
	return (q->rear + 1) % QUEUE_SIZE == q->front;
}

int enqueue(queue* q, element data)
{
	if (isFull(q)) return -1;
	q->rear = (q->rear + 1) % QUEUE_SIZE;
	q->data[q->rear] = data;
    return 0;
}

element dequeue(queue* q)
{
	if (isEmpty(q)) return -1;
	q->front = (q->front + 1) % QUEUE_SIZE;
	return q->data[q->front];
}

void queue_print(queue* q)
{
    if (isEmpty(q)) {
        printf("(empty)\n");
        return;
    }

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

 

main.c

#include <stdio.h>
#include "Queue.h"

int main()
{
	queue q;
	init(&q);

	for (int i = 0; i < 7; i++) 
	{
		printf("%d 삽입\n", i);
		enqueue(&q, i);
	}
	queue_print(&q);

	for (int i = 0; i < 5; i++)
	{
		printf("%d 제거\n", dequeue(&q));
	}
	queue_print(&q);

	for (int i = 0; i < 7; i++)
	{
		printf("%d 삽입\n", i);
		enqueue(&q, i);
	}
	queue_print(&q);

	return 0;
}

 

실행결과

 

이상으로 큐 자료구조를 알아보았습니다. 저의 글을 읽어 주셔서 감사드립니다.