[자료구조] 큐(Queue)란?

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

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

 

• rear : 큐의 삽입(enqueue)이 일어나는 곳
• front : 큐의 삭제(dequeue)가 일어나는 곳

 

---

 

1. 선형큐 (linear queue)

아래와 같이 1차원 배열을 사용하여 만든 큐이다.

선형큐

 

선형큐를 C언어로 작성하면 아래와 같다.

#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->front = -1;
	q->rear = -1;
}

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 queue_print(QueueType* q) {
	for (int i = 0; i < MAX_QUEUE_SIZE; i++) {
		if (i <= q->front || i > q->rear)
			printf("\t|");
		else
			printf("\t%d|", q->data[i]);
	}
	printf("\n");
}

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;
	}
	return q->data[++(q->front)];
}

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

 

 

⚠️ 문제점 ⚠️
front와 rear의 값이 계속 증가하여 언젠간 배열 끝네 도달하게 되고 배열의 앞이 비어있어도 사용 못 함

 

---

2. 원형큐 

⭐ front와 rear의 값이 MAX_QUEUE_SIZE가 되면 증가되는 값이 0으로 되게 설정한다.

✅ front  ← (front+1) % MAX_QUEUE_SIZE
✅ rear ← (rear+1) % MAX_QUEUE_SIZE

 

⭐ front와 rear의 초기값은 0 이다.

⭐ 포화 상태와 공백 상태를 구별하기 위해 항상 하나의 자리는 비워둔다!

 

 

원형큐의 코드는 다음과 같다.

#define _CRT_SECURE_NO_WARNINGS
#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->front = q->rear = 0;
}

int is_full(QueueType* q) {
	return ((q->rear + 1) % MAX_QUEUE_SIZE == (q->front) % MAX_QUEUE_SIZE);
}

int is_empty(QueueType* q) {
	return q->rear == 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, int item) {
	if (is_full(q)) { // 큐 꽉찼는지 확인
		error("큐가 포화 상태");
	}
	q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
	q->data[q->rear] = item;
}

int dequeue(QueueType* q) {
	if (is_empty(q)) {
		error("큐가 공백 상태");
	}
	q->front = (q->front + 1) % MAX_QUEUE_SIZE;
	return q->data[q->front];
}

int peek(QueueType* q) {
	if (is_empty(q))
		error("큐가 공백 상태");
	return q->data[(q->front + 1) % MAX_QUEUE_SIZE];
}

int main() {
	QueueType queue;
	int element;

	init_queue(&queue);

	while (!is_full(&queue)) {
		printf("정수를 입력하세요 : ");
		scanf("%d", &element);
		enqueue(&queue, element);
		queue_print(&queue);
	}
	printf("큐는 포화 상태");

	while (!is_empty(&queue)) {
		element = dequeue(&queue);
		printf("꺼내진 정수 : %d\n", element);
		queue_print(&queue);
	}
	printf("큐는 공백 상태");
	return 0;
}

---

3. 덱 (Deque : double - ended queue)

큐의 전단(front)과 후단(rear)에서 모두 삽입과 삭제가 가능한 큐를 의미한다.

원형큐를 확장하면 덱을 구현할 수 있다.

⭐ delete_rear()와 add_front()는 원형큐의 반대 방향으로 회전해야 된다.

✅ front  ← (front - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE
✅ rear ← (rear - 1  + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE

 

#define _CRT_SECURE_NO_WARNINGS
#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];
}DequeType;

void error(char* message) {
	fprintf(stderr, "%s\n", message);
	exit(1);
}
// 초기화
void init_deque(DequeType* q) {
	q->front = q->rear = 0;
}
// 포화 상태 확인
int is_full(DequeType* q) {
	return ((q->rear + 1) % MAX_QUEUE_SIZE == (q->front) % MAX_QUEUE_SIZE);
}
//공백 상태 확인
int is_empty(DequeType* q) {
	return q->rear == 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_rear(DequeType* q) {
	int item = q->data[q->rear];
	if (is_empty(q)) {
		error("큐가 공백 상태");
	}
	q->rear = (q->rear - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
	return item;
}
// 전단 삽입
void add_front(DequeType* q, element item) {
	if (is_full(q)) {
		error("큐가 포화 상태");
	}
	q->data[q->front] = item;
	q->front = (q->front - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
}
// 전단 삭제
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_rear(DequeType* q) {
	if (is_empty(q))
		error("큐가 공백 상태");
	return q->data[q->rear];
}
// 전단 확인
element get_front(DequeType* q) {
	if (is_empty(q))
		error("큐가 공백 상태");
	return q->data[(q->front + 1) % MAX_QUEUE_SIZE];
}

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