[자료구조] 큐

✍️ 큐(Queue)

큐란? 먼저 들어온 데이터가 먼저 나가는 자료구조
ex. 매표소의 대기열

큐의 ADT는 다음과 같다.

여기서 유의할 점은 스택에서 top을 이용했다는 점과 다르게 큐는 front, rear를 이용한다는 점이다.
삽입은 큐의 뒷부분인 rear에서만 일어나고, 삭제는 큐의 앞부분인 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);
	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_QUEUE_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 |    |    | 
   |    |    |    |    | 

front와 rear는 -1로 초기화한다.
함수 enqueue는 stack의 함수 push와 동일하지만 함수 dequeue는 stack의 함수 pop과는 다르게 전위 연산자임을 기억하자.

✍️ 원형 큐

션형 큐는 front와 rear 값이 계속 증가하게 되면 배열의 앞부분이 비어있어도 사용할 수가 없고 앞부분이 비었을 때 앞으로 땡겨야하는데 그 비용이 크다.
따라서 front와 rear의 개념을 약간 변경한 게 원형 큐이다.

• front: 첫번째 요소 하나 앞의 인덱스
• rear: 마지막 요소의 인덱스

또한 원형 큐의 MAX SIZE까지 data를 다 쓴다면 공백상태인 empty와 포화상태인 full을 구분할 수가 없다.
따라서 별도로 data를 몇개 넣었는지 셀 수 있는 변수인 count 변수를 생성하거나 MAX SIZE -1까지 data를 쓰면 해결된다.

#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->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]);
				if (i == q->rear)
					break;
			} while (i != q->front);
		}
	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];
}

// 삭제 함수
element peek(QueueType *q)
{
	if (is_empty(q))
		error("큐가 공백상태입니다");
	return q->data[(q->front + 1) % MAX_QUEUE_SIZE];
}


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

front와 rear는 0으로 초기화한다.
여기서 유의할 점은 포화상태일 때 count 변수를 따로 두지 않고 MAX SIZE -1만큼 쓰기로 했기 때문에 q->rear+1임을 기억하자.
또한 원형 큐이므로 삽입 알고리즘과 삭제 알고리즘에서 % MAX_QUEUE_SIZE 연산하는 것을 기억하자.

✍️ 덱(Deque)

덱이란? 큐의 전단(front)와 후단(rear)에서 모두 삽입과 삭제가 가능한 큐
double-ended queue의 줄임말

덱의 ADT는 다음과 같다.

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

typedef int element;
typedef struct { // 큐 타입
	element  data[MAX_QUEUE_SIZE];
	int  front, rear;
} DequeType;

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

// 초기화 
void init_deque(DequeType *q)
{
	q->front = q->rear = 0;
}

// 공백 상태 검출 함수
int is_empty(DequeType *q)
{
	return (q->front == q->rear);
}

// 포화 상태 검출 함수
int is_full(DequeType *q)
{
	return ((q->rear + 1) % MAX_QUEUE_SIZE == q->front);
}

// 원형큐 출력 함수
void deque_print(DequeType *q)
{
	printf("DEQUE(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]);
			if (i == q->rear)
				break;
		} while (i != q->front);
	}
	printf("\n");
}

// 삽입 함수
void add_rear(DequeType *q, element item)
{
	if (is_full(q))
		error("큐가 포화상태입니다");
	q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
	q->data[q->rear] = item;
}

// 삭제 함수
element delete_front(DequeType *q)
{
	if (is_empty(q))
		error("큐가 공백상태입니다");
	q->front = (q->front + 1) % MAX_QUEUE_SIZE;
	return q->data[q->front];
}


element get_front(DequeType *q)
{
	if (is_empty(q))
		error("큐가 공백상태입니다");
	return q->data[(q->front + 1) % MAX_QUEUE_SIZE];
}

// 삽입 함수
void add_front(DequeType *q, element val)
{
	if (is_full(q))
		error("큐가 포화상태입니다");
	q->data[q->front] = val;
	q->front = (q->front - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
}
// 삭제 함수
element delete_rear(DequeType *q)
{
	int prev = q->rear;
	if (is_empty(q))
		error("큐가 공백상태입니다");
	q->rear = (q->rear - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
	return q->data[prev];
}

element get_rear(DequeType *q)
{
	if (is_empty(q))
		error("큐가 공백상태입니다");
	return q->data[q->rear];
}

int main(void)
{
	DequeType queue;

	init_deque(&queue);
	for (int i = 0; i < 3; i++) {
		add_front(&queue, i);
		deque_print(&queue);
	}
	for (int i = 0; i < 3; i++) {
		delete_rear(&queue);
		deque_print(&queue);
	}
	return 0;
}

출력결과

DEQUE(front=4 rear=0) = 0 | 
DEQUE(front=3 rear=0) = 1 | 0 | 
DEQUE(front=2 rear=0) = 2 | 1 | 0 | 
DEQUE(front=2 rear=4) = 2 | 1 | 
DEQUE(front=2 rear=3) = 2 | 
DEQUE(front=2 rear=2) = 

여기서 유의할 점은 함수 add_front와 delete_rear에서 front와 rear같은 포인터가 뒤로 이동해야 하므로 q->front - 1 + MAX_QUEUE_SIZE와 q->rear - 1 + MAX_QUEUE_SIZE임을 기억하자.