자료구조 QUEUE

QUEUE

큐(queue)라는 단어의 사전적인 뜻을 찾아보면, “ (무엇을 기다리는 사람·자동차 등의) 줄” 이다. 계산을 기다리는 사람들의 줄을 생각하면 이해가 쉽다.

선입선출 (FIFO : First - In - First - Out)

스택과 비교되는 큐의 중요한 특징이다. 스택에서는 가장 마지막에 들어온 데이터가 가장 먼저 나가는 후입선출(LIFO)의 특징을 가졌다면, 큐는 이와 반대로 먼저 들어온 데이터가 먼저 나가는 구조이다.  즉 큐에서 입력은 뒤쪽에서만 일어나며, 출력은 앞쪽에서만 일어난다. 큐에서 삽입이 일어나는 뒤쪽을 rear(후단), 삭제가 일어나는 앞쪽을 front(전단) 이라고 한다.

선형 큐

큐도 스택과 같이 1차원 배열로 구현이 가능하다. (물론 다른 방법도 존재하나 1차원 배열을 이용하는게 가장 간단하다.) 큐의 첫번째 요소를 가리키는 변수 front 와, 큐의 마지막 요소를 가리키는 변수 rear 을 설정한다. 스택이 비어있는 초기 상태에는 front와 rear이 모두 -1의 값을 가진다. 스택에 요소를 삽입할 때마다 rear은 1씩 커지고, 스택에서 삭제가 일어날 때마다 front도 1씩 커진다.

)

선형 큐의 문제점

1차원 배열로 구현한 선형큐에는 문제점이 있다. 큐에 요소를 삽입하든, 삭제를 하든 front와 rear의 값이 계속 증가만 하게 된다. 그러므로 삽입 삭제를 많이 하게 되면 언젠가는 front와 rear의 값이 배열의 끝 값에 도달하게 될 것이다. 그렇게 되면 배열의 앞부분이 비어 있음에도 불구하고 사용할 수 없게 된다. 따라서 앞부분에 빈 공간이 생기면 모든 요소들을 다시 앞쪽으로 이동시켜야 공간 낭비를 방지할 수 있다. 하지만 이런식으로 매번 데이터들을 이동시키는 것은 상당한 시간이 걸릴 뿐만 아니라 프로그래밍적인 부분에서 코드가 매우 복잡해지기 때문에 비효율적이다.

---

원형 QUEUE

큐는 배열로 구현된 선형의 형태를 가진다. 데이터 삽입삭제시 데이터들을 앞 혹은 뒤로 당겨주는 과정이 필요함, 이는 불필요한 시간 낭비를 발생시킴. 이를 극복시키려고 만든것이 원형큐이다.

REAR은 큐의 맨 뒤, FRONT는 맨 앞이다.

순서

1. 원형 큐의 크기를 사전에 정하고, 빈 리스트를 정의
2. 리스트에 데이터를 삽입하면 rear는 1로 옮겨짐
3. 리스트에서 데이터를 dequeue()해주면,front는 1로 옮겨지며, 1에 저장되어 있는 데이터가 반환됨.

코드

#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 = 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, int data) {
	if (is_full(q)) {
		printf("Queue is full \n");
	}
	else {
		q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
		q->data[q->rear] = data;
	}
}

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

//큐의 모든 요소 출력
void print_queue(QueueType* q) {
	if (is_empty(q)) {
		printf("Empty Queue \n");
	}
	else {
		printf("Queue:");
		if (!is_empty(q)) {
			int i = q->front;
			do {
				i = (i + 1) % MAX_QUEUE_SIZE;
				printf(" %d |", q->data[i]);
				if (i == q->rear)
					break;
			} while (i != q->front);
			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);

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

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

	return 0;

원형QUEUE의 문제점은 맨 뒤로가면 다시 0번째로 가야되는데, 방지책이 하나필요함

해결방법

→ 공백상태와 포함상태를 구별하기 위하여 하나의 공간은 항상 비워둔다.

공백상태 : front == rear

포화상태 : front%M==(rear+1) % M