큐의 정의
스택과 함께 큐도 프로그래밍에서 굉장히 자주 사용되는 자료구조입니다. 스택이 후입선출(LIFO) 형태를 따르는 자료구조라면, 큐는 반대로 선입선출(FIFO, First In First Out) 형태를 따르는 자료구조입니다. 선입선출의 예시로는 은행 업무를 보기 위해 기다리는 사람들의 대기열을 예시로 들 수 있습니다. 가장 먼저 대기표를 뽑은 사람이 가장 먼저 은행 업무를 보게 될 것입니다.
이처럼 큐는 "뒤에서 새로운 데이터가 추가되고 앞에서 데이터가 하나씩 삭제되는 구조"를 가지고 있습니다. 즉, 삽입과 삭제가 서로 다른 곳에서 일어납니다. 큐에서 삽입이 일어나는 곳(가장 뒤 부분)을 후단(Rear)이라고 하고, 큐에서 삭제가 일어나는 곳(가장 앞 부분)을 전단(Front)이라고 합니다.
Enqueue 연산과 Dequeue 연산
큐의 Enqueue 연산과 Dequeue 연산은 스택의 push 연산과 pop 연산과 매우 유사합니다. 그러나 다른 것이 있다면 스택과 달리 큐는 삽입과 삭제가 서로 다른 곳에서 일어나기에 큐는 "양쪽 끝 부분을 다 살펴보아야 한다는 것입니다."
Enqueue 연산
Enqueue 연산은 큐에 요소를 추가하는 연산으로, 큐의 "가장 끝 부분"에 새로운 요소를 "추가"합니다. 당연히 Enqueue 연산을 진행하는 중, 큐의 데이터가 완전히 찬다면 Enqueue 연산은 더 이상 실행되지 않으며 오류가 발생하게 됩니다.
Dequeue 연산
Dequeue 연산은 큐의 요소를 삭제하는 연산으로, 큐의 "가장 앞 부분"에 있는 요소를 "삭제"합니다. 당연히 Dequeue 연산을 진행하는 중, 큐의 데이터가 남아있지 않다면 Dequeue 연산은 더 이상 실행되지 않으며 오류가 발생하게 됩니다.
선형 큐 (Linear Queue)
지금부터 큐를 구현해보도록 하겠습니다. 스택을 구현하는 것과 아주 유사합니다. 삽입을 위한 변수 "rear"와 삭제를 위한 "front"를 선언해주고(이때, 각각 rear와 front의 초기값은 -1이 되어야 합니다.) 삽입이 진행되면 rear를 1 증가시킨 후 데이터를 저장하면 되고, 삭제가 진행되면 front를 1 증가시킨 후 front가 지정하는 위치에 있는 데이터를 삭제하면 됩니다. 이렇게 구현하는 큐를 "선형 큐(Linear Queue)"라고 합니다.
#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() {
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;
}원형 큐 (Circle Queue)
선형 큐에는 치명적인 단점이 있는데, 그것은 바로 "전단(front)과 후단(rear)의 값이 증가만 하기에 메모리 활용이 비효율적이다"라는 것입니다. 즉, 큐의 크기는 결국 정해져있는데 전단과 후단이 계속 증가만 하면 앞 부분의 메모리는 비어있고, 계속 뒷 공간에 데이터를 추가하니 메모리가 낭비가 되는 것입니다. 결국은 큐의 크기가 정해져 있기에 데이터도 무한정으로 추가할 수 없기도 합니다. 그래서 이러한 문제점을 해결하고자 "원형 큐"가 등장하였습니다.
원형 큐는 큐 배열을 선형(직선)이 아니라 원형으로 바꾸고, front와 rear를 연결시키는 것입니다. 또한 front와 rear의 초기값을 -1이 아닌 0으로 선언하여 구현합니다. 말로 설명하면 이해하기가 쉽지 않으니 아래의 사진을 통해 이해해봅시다.
원형 큐의 개념에 대해서 알아보았으니, 이제부터 원형 큐를 실제로 구현해보겠습니다. 원형 큐를 구현함에 있어서 가장 중요한 것은 front와 rear를 원형으로 회전시키는 것입니다. front와 rear를 원형으로 회전시키는 알고리즘은 다음과 같습니다.
front = (front + 1) % MAX_QUEUE_SIZE;
rear = (rear + 1 ) % MAX_QUEUE_SIZE;
그리고 원형 큐를 구현할 때 중요한 것은 "front는 첫 번째 요소 앞을 가리키고, rear는 마지막 요소를 가리킨다" 입니다. 그렇기에 삽입을 할 때는 반드시 rear를 먼저 증가시킨 후 데이터를 삽입하고, 삭제를 할 때는 반드시 front를 먼저 증가시킨 후 데이터를 삭제해야 합니다.
이제 정말로 원형 큐를 실제로 구현해보겠습니다. 원형 큐를 C언어 코드로 나타내면 다음과 같습니다.
#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];
}
// 전단(front) 호출 함수
element get_front(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);
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;
}덱 (Deque)
덱은 Double-Ended Queue의 줄임말로, 큐의 전단과 후단 모두에서 삽입과 삭제가 가능한 큐를 말합니다. 그렇기에 덱은 스택과 큐의 연산을 모두 가지고 있습니다. 다만, 스택과 큐와 같이 데이터 중간에 삽입하거나 삭제하는 연산은 불가능합니다.
덱은 원형 큐와 같이 전단과 후단을 모두 사용하기에 구현하는 방법도 원형 큐와 매우 유사합니다. 그러나 덱에는 조금 더 추가해줘야 하는 연산들이 있습니다. 바로 "후단을 삭제하는 연산(delete_rear)", "전단에 삽입하는 연산(add_front)", "후단을 가져오는 연산(get_rear)" 이것들을 추가해주면 덱 구현이 끝이 납니다.
이때, delete_rear()와 add_front()에서는 원형 큐와 달리 반대 방향의 회전이 필요합니다. 반대 방향의 회전을 구하는 알고리즘은 다음과 같습니다.
front = (front - 1 + MAX_DEQUE_SIZE) % MAX_DEQUE_SIZE;
rear = (rear - 1 + MAX_DEQUE_SIZE) % MAX_DEQUE_SIZE;
이제 덱에 대해서 알아야 할 것은 끝났습니다. 이제 C언어로 덱을 구현해보도록 하겠습니다.
#include <stdio.h>
#include <stdlib.h>
#define MAX_DEQUE_SIZE 5
typedef int element;
typedef struct { // 덱 타입
element data[MAX_DEQUE_SIZE];
int front, rear;
} DequeType;
// 오류 함수
void error(char *message) {
fprintf(stderr, "%s\n", message);
exit(1);
}
// 초기화
void init_deque(DequeType *d) {
d->front = d->rear = 0;
}
// 공백 상태 검출 함수
int is_empty(DequeType *d) {
return (d->front == d->rear);
}
// 포화 상태 검출 함수
int is_full(DequeType *d) {
return ((d->rear + 1) % MAX_DEQUE_SIZE == d->front);
}
// 덱 출력 함수
void deque_print(DequeType *d) {
printf("DEQUE(front=%d rear=%d) = ", d->front, d->rear);
if(!is_empty(d)) {
int i = d->front;
do {
i = (i + 1) % (MAX_DEQUE_SIZE);
printf("%d | ", d->data[i]);
if(i == d->rear)
break;
} while (i != d->front);
}
printf("\n");
}
// 삽입 함수
void add_rear(DequeType *d, element item) {
if(is_full(d))
error("덱이 포화상태입니다.");
d->rear = (d->rear + 1) % MAX_DEQUE_SIZE;
d->data[d->rear] = item;
}
// 삭제 함수
element delete_front(DequeType *d) {
if (is_empty(d))
error("덱이 공백상태입니다.");
d->front = (d->front + 1) % MAX_DEQUE_SIZE;
return d->data[d->front];
}
// 전단 호출 함수
element get_front(DequeType *d) {
if (is_empty(d))
error("덱이 공백상태입니다.");
return d->data[(d->front + 1) % MAX_DEQUE_SIZE];
}
// 전단 삽입 함수
void add_front(DequeType *d, element val) {
if (is_full(d))
error("덱이 포화상태입니다.");
d->data[d->front] = val;
d->front = (d->front - 1 + MAX_DEQUE_SIZE) % MAX_DEQUE_SIZE;
}
// 후단 삭제 함수
element delete_rear(DequeType *d) {
int prev = d->rear;
if (is_empty(d))
error("덱이 공백상태입니다.");
d->rear = (d->rear - 1 + MAX_DEQUE_SIZE) % MAX_DEQUE_SIZE;
return d->data[prev];
}
// 후단 호출 함수
element get_rear(DequeType *d) {
if (is_empty(d))
error("덱이 공백상태입니다.");
return d->data[d->rear];
}
int main() {
DequeType deque;
init_deque(&deque);
for (int i = 0; i < 3; i++) {
add_front(&deque, i);
deque_print(&deque);
}
for (int i = 0; i < 3; i++) {
delete_rear(&deque);
deque_print(&deque);
}
return 0;
}