[자료구조]큐(Queue)

큐의 구조

 

FIFO: First-In First-Out

큐는 먼저 들어온 데이터가 먼저 나가는 구조이다.

이러한 형태를 선입 선출이라고 한다.

큐는 뒤에서 새로운 데이터가 추가되고 앞에서 데이터가 하나씩 삭제되는 구조를 가지고 있다.

큐에서 삽입이 일어나는 곳을 후단(rear)라 하고 삭제가 일어나는 곳을 전단(front)라고 한다.

그림 1. 큐의 구조

 

 

 

 

큐의 삽입, 삭제

 

큐로의 삽입 연산은 enqueue연산이라고 하고 삭제 연산은 dequeue연산이라고 한다.

enqueue연산은 큐에 요소를 추가하는 연산으로서 큐의 맨 뒤에 새로운 요소를 추가한다.

dequeue연산은 큐의 맨 앞에 있는 요소를 꺼내서 외부로 반환한다.

그림 2. 큐의 삽입, 삭제

그림 2는 큐에서의 enqueue와 dequeue연산을 보여준다.

큐에서 enqueue(A)를 수행하면 A가 삽입되고, front는 A의 앞, rear는 B를 가리키게 된다

마찬가지로 enqueue(B)를 수행하면 큐에 B가 삽입되고, front는 A의 앞, rear는 B를 가리키게 된다.

또 한번 enqueue(C)를 수행하면 큐에 C가 삽입되고, front는 A의 앞, rear는 C를 가리키게 된다.

여기서 dequeue() 연산이 수행된다면 가장 앞에 있는 A가 삭제된다.

이 때 front는 B의 앞, rear는 C를 가리키게 된다.

 

 

큐의 이용

 

큐가 많이 이용되는 분야는 컴퓨터를 이용하여 현실 세계의 실제상황을 시뮬레이션 하는 곳이다. 예를 들면 은행에서 기다리는 사람들의 대기열, 공항에서 이륙하는 비행기들, 인터넷에서 전송되는 데이터 패킷들을 모델링하는데 큐가 이용된다. 큐는 운영체제에서도 중요하게 사용된다. 컴퓨터의 CPU와 주변기기 사이에는 속도 차이가 있기 때문에 CPU를 효율적으로 사용하기 위하여 보통 컴퓨터와 주변기기 사이에는 항상 큐가 존재한다.

 

 

선형큐의 구현

 

C언어로 1차원 배열 큐를 구현해보자.

MAX_QUEUE_SIZE로 큐의 사이즈를 지정해주었다.

element는 편의상 int로 선언하였다.

큐 사이즈 크기의 1차원 배열과 front, rear의 정보를 가지고 있는 QueueType구조체를 선언하였다.

#include <stdio.h>

#define MAX_QUEUE_SIZE 5

typedef int element;

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

배열은 0부터 시작하므로 큐가 비어 있다면 front와 rear는 -1이다.

큐의 front와 rear에 -1을 넣어주는 큐 초기화 함수 init_queue를 작성하였다.

큐가 비어 있다면 front와 rear는 같을 것이다.

이를 이용하여 큐가 비어 있는지를 확인하는 함수 is_empty를 작성하였다.

큐가 가득 찼다면 rear는 큐의 최대 사이즈보다 1이 작을 것이다.

이를 이용하여 큐가 가득 찼는지 확인하는 함수 is_full을 작성하였다.

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

//큐가 비어 있는지 확인
int is_empty(QueueType* q) {
	return (q->front == q-> rear);
}

//큐가 가득 찼는지 확인
int is_full(QueueType* q) {
	return (q->rear == MAX_QUEUE_SIZE - 1);
}

큐의 주요 연산인 enqueue, dequeue함수이다.

enqueue를 하기 전에 큐가 가득 차 있는지 확인 하고,

가득 차 있다면 메세지를 출력하고 아니라면 삽입 연산을 수행한다.

기존의 큐의 하단을 가리키고 있었던 rear에 1을 더해준 후 배열의 rear 인덱스에 데이터를 넣도록 작성하였다.

dequeue를 하기 전에 큐가 비어 있는지 확인 하고,

비어 있다면 메세지를 출력하고 아니라면 삭제 연산을 수행한다.

큐의 전단에 1을 더해준 후 해당 인덱스에 있었던 데이터를 data변수에 대입한다.

data변수를 return한다.

//큐가 가득 차 있는지 확인 후 삽입 연산
void enqueue(QueueType* q, int data) {
	if (is_full(q)) {
		printf("Queue is full \n");
	}
	else {
		q->data[++(q->rear)] = data;
	}
}

//큐가 비어 있는지 확인 후 삭제 연산
element dequeue(QueueType* q) {
	if (is_empty(q)) {
		printf("Queue is empty \n");
		exit(1);
	}
	else {
		int data = q->data[++(q->front)];
		return data;
	}
}

큐의 모든 element를 출력하는 함수이다.

큐가 비어 있다면 빈 큐라는 메세지를 출력한다.

그렇지 않다면 큐를 출력한다.

//큐의 모든 요소 출력
void print_queue(QueueType* q) {
	if (is_empty(q)) {
		printf("Empty Queue \n");
	}
	else {
		printf("Queue:");
		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");
	}
}

main함수에서는 QueueType을 선언해주고 각 element들을 enqueue, dequeue한 후 출력을 해 주었다.

int main() {

	QueueType queue;

	int item = 0;
	init_queue(&queue);

	enqueue(&queue, 3);
	print_queue(&queue);

	enqueue(&queue, 4);
	print_queue(&queue);

	enqueue(&queue, 5);
	print_queue(&queue);

	item = dequeue(&queue);
	print_queue(&queue);

	enqueue(&queue, 6);
	print_queue(&queue);

	item = dequeue(&queue);
	print_queue(&queue);

	return 0;
}

 

전체 코드

 

#include <stdio.h>

#define MAX_QUEUE_SIZE 5

typedef int element;

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

//큐 초기화 
void init_queue(QueueType* q) {
	q->front = q->rear = -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 data) {
	if (is_full(q)) {
		printf("Queue is full \n");
	}
	else {
		q->data[++(q->rear)] = data;
	}
}

//큐가 비어 있는지 확인 후 삭제 연산
element dequeue(QueueType* q) {
	if (is_empty(q)) {
		printf("Queue is empty \n");
		exit(1);
	}
	else {
		int data = q->data[++(q->front)];
		return data;
	}
}

//큐의 모든 요소 출력
void print_queue(QueueType* q) {
	if (is_empty(q)) {
		printf("Empty Queue \n");
	}
	else {
		printf("Queue:");
		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() {

	QueueType queue;

	int item = 0;
	init_queue(&queue);

	enqueue(&queue, 3);
	print_queue(&queue);

	enqueue(&queue, 4);
	print_queue(&queue);

	enqueue(&queue, 5);
	print_queue(&queue);

	item = dequeue(&queue);
	print_queue(&queue);

	enqueue(&queue, 6);
	print_queue(&queue);

	item = dequeue(&queue);
	print_queue(&queue);

	return 0;
}

그림 3. 출력 결과

 

 

선형 큐의 문제점

선형 큐는 이해하기는 쉽지만 front와 rear값이 계속 증가하기만 한다는 문제점이 있다.

언젠가는 배열의 끝에 도달하게 되고 배열의 앞부분이 비어 있더라도 사용하지 못하게 된다.

따라서 주기적으로 모든 요소를 왼쪽으로 이동시켜야 한다. 

모든 요소들을 이동시키면 해결은 되지만 매번 이동시키려면 상당한 시간이 걸리고 프로그램 또한 복잡해진다. 

이러한 문제를 해결한 것이 원형 큐 이다. 

다음 글에서는 원형 큐를 다룰 것이다.