[자료구조] 큐 Queue, 선형 큐, 원형 큐 구현

큐 Queue

나중에 들어온 데이터가 먼저 나가는 스택 자료구조와 달리 큐는 먼저 들어온 데이터가 먼저 나가는 자료구조입니다.

선입선출(FIFO: First-In First-Out) 큐를 사용하는 방식에는 선형 큐, 원형 큐, 덱이 있습니다.

 

선형 큐

배열을 선형으로 사용하여 구현된 큐이며, 삽입을 계속하기 위해서는 요소들을 이동시켜야 합니다.

데이터를 넣을때마다 번거로움이 있다는 문제점이 있는 방식입니다.

 

또한 인덱스를 감소하지는 않고 증가만 하면서 사용하는 방식이기에, 실제로 앞부분에는 데이터가 없을 때에도 비어있는 공간을 활용할 수 없기 때문에 비효율적인 부분이 있습니다.

 

#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);
	exit(1);
}
// 선형 큐 초기화
void init_queue(QueueType *q)
{
	q->rear = -1;
	q->front = -1;
}
// 선형 큐 상태 출력
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 is_full(QueueType *q)
{
	if (q->rear ==  MAX_QUE_SIZE - 1 )
		return 1;
	else
		return 0;
}
// 선형 큐가 공백상태인가?
int is_empty(QueueType *q)
{
	if ( q->front == q->rear )
		return 1;
	else
		return 0;
}
// 선형 큐에 데이터 삽입
void enqueue(QueueType *q, int item)
{
	if (is_full(q)) {
		error("큐가 포화상태입니다.");
		return;
	}
	q->data[  ++(q->rear)  ] = item;
}
// 선형 큐에서 데이터 제거
int dequeue(QueueType *q)
{
	if (is_empty(q)) {
		error("큐가 공백상태입니다.");
		return -1;
	}
	int item = q->data[ ++(q->front) ];
	return item;
}	
// 메인
int main(void)
{
	int item = 0;
	QueueType q;

	init_queue(&q);

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

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

/* 실행결과
10 |    |    |    |    |
10 | 20 |    |    |    |
10 | 20 | 30 |    |    |
   | 20 | 30 |    |    |
   |    | 30 |    |    |
   |    |    |    |    |
*/

 

원형 큐

선형 큐의 대안으로 나온 것이 원형 큐입니다. 큐의 전단과 후단을 관리하기 위한 2개의 변수가 필요합니다.

- front 첫번째 요소 바로 앞의 인덱스

- rear 마지막 요소의 인덱스

 

공백상태는 front == rear 인 상태이며 포화상태는 front == (rear+1) % MAX_QUEUE_SIZE 의 값으로 판단합니다.

위 그림에서 큐의 맥스 크기는 8입니다. 만약 front가 2에 있을 때 포화상태라면 rear가 1에 있어야 하겠죠. 그 값을 우변에서 계산하면 (1+1) % 8 = 2가 되므로 front와 rear값이 같아 포화상태인 것을 알립니다. 공백상태와 포화상태를 구별하기 위하여 하나의 공간은 항상 비워둡니다.

 

#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  ; // 0이 아니라 다른 수로 해도 상관 없습니다. 원형이기 때문입니다.
}
// 공백 상태 검출 함수
int is_empty(QueueType *q)
{
	return ( q->front == q->rear );
}
// 포화 상태 검출 함수
int is_full(QueueType *q)
{
	return ((q->rear + 1) % MAX_QUEUE_SIZE == q->front);
}
// 원형 큐 출력 함수
void queue_print(QueueType *q)
{
	printf("QUEUE(front=%d rear=%d) = ", q->front, q->rear);
	if (!is_empty(q)) {
		int i = q->front;
		do {
			i = (i + 1) % (MAX_QUEUE_SIZE);
			printf("%d | ", q->data[i]);
		} while ( i == q->rear );
	}
	printf("\n");
}
// 삽입 함수
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];
}
// 메인
int main(void)
{
	QueueType queue;
	int element;

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

	printf("--데이터 삭제 단계--\n");
	while (!is_empty(&queue))
	{
		element = dequeue(&queue);
		printf("꺼내진 정수: %d \n", element);
		queue_print(&queue);
	}
	printf("큐는 공백상태입니다.\n");
	return 0;
}

/*
--데이터 추가 단계--
정수를 입력하시오: 10
QUEUE(front=0 rear=1) = 10 |
정수를 입력하시오: 20
QUEUE(front=0 rear=2) = 10 | 20 |
정수를 입력하시오: 30
QUEUE(front=0 rear=3) = 10 | 20 | 30 |
정수를 입력하시오: 40
QUEUE(front=0 rear=4) = 10 | 20 | 30 | 40 |
큐는 포화상태입니다.

--데이터 삭제 단계--
꺼내진 정수: 10
QUEUE(front=1 rear=4) = 20 | 30 | 40 |
꺼내진 정수: 20
QUEUE(front=2 rear=4) = 30 | 40 |
꺼내진 정수: 30
QUEUE(front=3 rear=4) = 40 |
꺼내진 정수: 40
QUEUE(front=4 rear=4) =
큐는 공백상태입니다.
*/