큐(Queue) 란?
스택의 경우, 나중에 들어온 데이터가 먼저 나가는 LIFO 구조인 반면, 큐(Queue) 는 먼저 들어온 데이터가 먼저 나가는 자료구조입니다. 이런 특성을 FIFO (First-In First-Out) 이라고 합니다.
스택은 아래 부분이 막히고 윗 부분이 뚫린 형태였다면 큐는 양쪽이 뚫린 통입니다. 스택이 맨 위에서만 데이터를 삽입하고 삭제했다면 큐는 삽입과 삭제가 다른 쪽에서 일어납니다. 양 끝의 이름을 일반적으로 front 와 rear 라고 부르며 데이터의 삽입이 일어나는 곳을 rear 라고 하고 데이터의 삭제가 이뤄지는 곳을 front 라고 합니다.
데이터 삽입을 스택에서는 push 라고 했지만 queue 에서는 enqueue 라고 합니다. 삭제 연산은 dequeue 라고 합니다.
선형큐 구현
큐도 스택과 마찬가지로 구현하는 방법이 여러 가지입니다. 오늘은 배열을 이용해 큐를 구현해볼 건데 배열 구현과 연결리스트 구현은 각각 장단점이 있습니다. 큐의 크기가 동적으로 변경되거나 중간에 요소의 삽입/수정이 많은 경우에는 연결리스트로 구현하는 것이 유리하고 배열 기반 큐는 큐의 크기가 고정되어 있고, 요소의 삽입/삭제가 이루어지지 않는 경우 상대적으로 간단하게 구현할 수 있습니다.
먼저 1차원 배열을 정의하고 삽입, 삭제를 위한 변수인 front 와 rear 을 만듭니다. front 는 큐의 첫 번째 요소를 가리키고 rear 는 큐의 마지막 원소를 가리킵니다.
큐 타입 정의, 큐 초기화 init()
#include <stdio.h>
#include <stdlib.h>
#define MAX_QUEUE_SIZE 5
typedef int element;
typedef struct {
int front;
int rear;
element[MAX_QUEUE_SIZE];
}QueueType;
void init(QueueType* q)
{
q->rear = -1;
q->front = -1;
}스택과 거의 유사한 형태로 정의합니다. 스택의 경우는 element 배열과 top 을 가리키기 위한 int top 이 StackType 안에 정의되었습니다. 큐의 경우는 front 와 rear 2개의 인덱스를 나타내기 위해 변수를 2개 정의합니다. init() 의 경우도 거의 동일한데요, 배열이기 때문에 처음에는 -1 인덱스로 초기화해 큐가 비어있음을 명시합니다.
isfull(), isempty() 함수
스택과 마찬가지로 큐가 가득 찼는지, 비어 있는지 검사하는 함수가 필요합니다.
int isfull(QueueType* q)
{
if (q->rear == (MAX_QUEUE_SIZE - 1))
return 1;
else
return 0;
}
int isempty(QueueType* q)
{
if (q->front == q->rear)
return 1;
else
return 0;
}먼저 isfull() 의 동작을 보면, rear 가 큐의 마지막 인덱스를 가리키는 경우 가득 찼다고 정의합니다. 이 때 큐 안에 몇 개의 데이터가 들어있는지는 중요하지 않습니다. 더 이상 rear 가 증가할 수 없는 경우 선형큐에서는 가득 찼다고 정의합니다.
isempty() 의 조건을 보면 front == rear 인 경우 데이터가 없다고 정의합니다. 이는 아래에서 enqueue 와 dequeue 의 내용을 확인하면 더 쉽게 이해할 수 있지만 쉽게 생각해보면 데이터의 삽입이 일어나는 경우 rear 가 1 증가하고, 데이터의 삭제가 이루어지면 front 가 1 증가한다고 생각하시면 됩니다.
enqueue() : 데이터 삽입 , ++rear 에 데이터 저장
큐의 구현에서는 enqueue 와 dequeue 를 이해하는 것이 가장 중요합니다. rear 가 먼저 증가한 이후 데이터를 삽입해야만 합니다. 이는 마치 스택에서 push 연산을 구현하는 것과 비슷합니다.
void enqueue(QueueType* q, element item)
{
if (isfull(q)) {
fprintf(stderr, "큐 포화 상태 에러\n");
return;
}
q->data[++(q->rear)] = item; // rear 가 먼저 1 증가하고 삽입
}
dequeue() : 데이터 삭제 , ++front 에 있는 데이터 추출
dequeue() 는 마찬가지로 front 를 먼저 증가 시키고 그 인덱스에 있는 데이터를 추출하는 함수입니다.
element dequeue(QueueType* q)
{
if (isempty(q)) {
fprintf(stderr, "큐 공백 상태 에러");
return -1;
}
return q->data[++(q->front)];
}
선형큐 ( linear queue )
이로써 선형큐의 구현이 끝났습니다. main 함수까지 포함한 전체 코드 및 실행 예시를 확인해봅시다.
#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 init(QueueType* q)
{
q->rear = -1;
q->front = -1;
}
int isfull(QueueType* q)
{
if (q->rear == (MAX_QUEUE_SIZE - 1))
return 1;
else
return 0;
}
int isempty(QueueType* q)
{
if (q->front == q->rear)
return 1;
else
return 0;
}
void enqueue(QueueType* q, element item)
{
if (isfull(q)) {
fprintf(stderr, "큐 포화 상태 에러\n");
return;
}
q->data[++(q->rear)] = item; // rear 가 먼저 1 증가하고 삽입
}
element dequeue(QueueType* q)
{
if (isempty(q)) {
fprintf(stderr, "큐 공백 상태 에러");
return -1;
}
return q->data[++(q->front)];
}
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 main(void) {
int item = 0;
QueueType q;
init(&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);
enqueue(&q, 40); queue_print(&q);
enqueue(&q, 50); queue_print(&q);
item = dequeue(&q); queue_print(&q);
enqueue(&q, 60);
return 0;
}
간단한 예제 코드만 봐도 선형큐는 이해하기 쉽지만 치명적인 단점을 확인할 수 있습니다. 바로 데이터가 큐에 없더라도 MAX_QUEUE_SIZE 수를 넘어서는 enqueue 연산을 할 수 없다는 점입니다. 분명 지금 큐에는 데이터가 하나밖에 없고, 빈 자리가 무려 3개나 되는데, 즉 배열의 앞부분이 비어있는데도 큐를 재사용하지 못하는 건 딱 봐도 비효율적이죠. 그래서 끝과 처음을 이어서 재사용할 수 있도록 원형으로 큐를 구성한 것을 원형큐(Circular Queue) 라고 합니다.
원형큐(Circular Queue)
큐의 개념을 그대로 사용하면서 배열을 원형으로 생각한 것을 원형큐 라고 합니다. 즉 front 와 rear의 값이 배열의 끝인 (MAX_QUEUE_SIZE -1) 에 도달하면 다음에 증가하는 값이 0이 되도록 만든 것입니다. 실제 배열이 원형으로 변화되는 건 아니지만 개념상으로 원형으로 배열의 인덱스를 변화시켜 주는 것이죠.
원형큐에서는 front 와 rear 의 개념이 선형큐와 살짝 달라집니다. 먼저 초기값이 -1 이 아니라 0 입니다. front 는 항상 큐의 첫번째 요소의 하나 앞을, rear 는 마지막 요소를 가리킵니다.
처음에 front와 rear 는 모두 0 입니다. 위 gif 에서는 head = front , tail = rear 라고 생각하시면 됩니다.
삽입 시 rear(tail) 이 먼저 증가되고, 증가된 위치에 새로운 데이터가 삽입됩니다. 삭제 시에도 front(head) 가 먼저 증가된 다음, 증가된 위치에서 데이터를 삭제합니다.
원형큐에서 front와 rear 의 값이 같으면 원형큐가 비어있음을 나타냅니다. 그리고 원형큐에서는 하나의 자리는 항상 비워둡니다. 그렇지 않으면 공백 상태와 포화 상태를 구분할 수 없기 때문입니다.
위 사진처럼 front 가 rear 보다 하나 앞에 있으면 포화 상태가 됩니다. 만약 요소들의 개수를 저장하고 있는 count 변수가 있다면 굳이 한 자리를 비워놓지 않아도 공백과 포화 상태를 구분할 수 있기 때문에 이 경우에는 공백 상태와 포화 상태 모두 front == rear 인 상태이고 count 에 따라 공백과 포화 상태를 구분합니다.
원형큐 구현
큐 타입의 정의는 선형큐와 똑같기 때문에 생략합니다. 바로 초기화, 공백, 포화 상태 검출 함수를 확인해봅시다.
init, isfull, isempty
//초기화 함수
void init(QueueType* q)
{
q->rear = q->front = 0;
}
// 포화 상태 검출 함수
int isfull(QueueType* q)
{
return ((q->rear + 1) % MAX_QUEUE_SIZE == q->front);
}
// 공백 상태 검출 함수
int isempty(QueueType* q)
{
return (q->front == q->rear);
}초기화 값이 0으로 바뀌고, isfull() 이 조금 특이합니다. 해석해보면 rear + 1 을 큐 크기로 나눈 것 이 front 랑 같다면, 즉 rear 이 front 보다 한칸 뒤인가? 를 묻는 겁니다. 나머지 연산자 % 를 사용해 원형으로 회전시킨 인덱스를 나타냅니다.
뒤에서도 나오므로 원형 인덱스를 나타내는 방법을 정리해보면
front ← (front + 1) % MAX_QUEUE_SIZE;
rear ← (rear + 1) % MAX_QUEUE_SIZE;
를 사용하면 front 와 rear 값은 만약 MAX_QUEUE_SIZE 가 5라면 0 1 2 3 4 0 1 2 ... 이런 식으로 변화합니다.
enqueue() , dequeue()
void enqueue(QueueType* q, element item)
{
if (isfull(q)) {
fprintf(stderr, "큐 포화 상태 에러\n");
return;
}
// 선형큐에서는 1 증가하고 삽입, 원형큐에서는 1 증가하고 원형 인덱스 연산 후 삽입
q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
q->data[q->rear] = item;
}
element dequeue(QueueType* q)
{
if (isempty(q)) {
fprintf(stderr, "큐 공백 상태 에러");
return -1;
}
// 선형큐에서는 1 증가하고 삭제, 원형큐에서는 1 증가하고 원형 인덱스 연산 후 삭제
q->front = (q->front + 1) % MAX_QUEUE_SIZE;
return q->data[q->front];
}선형큐와 비교하여 보면 더 이해하기 쉽습니다. 선형큐에서도 front와 rear 가 먼저 증가한 이후 삽입/삭제 연산이 각각 수행되었는데 원형큐에서는 증가만 하는 것이 아니라 추가적으로 원형 인덱스 연산, 즉 6 이면 1 로 바꿔주는 연산인 % 를 통해 원형큐에 맞는 인덱스로 변환시키고 삽입/삭제를 수행합니다.
queue_print()
큐를 프린트해주는 함수입니다. 이 동작을 따라가다보면 큐의 구성을 이해하기 좋습니다. 반대로 큐의 구성을 이해하지 못한다면 이 print 함수도 꽤 어렵게 느껴질 수 있습니다.
void queue_print(QueueType* q)
{
printf("QUEUE(front=%d rear=%d) = ", q->front, q->rear);
if (!isempty(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");
}
원형큐 전체 코드 및 실행 결과
위에서 구현한 게 전부 다입니다. main 함수만 추가해서 실행 결과와 함께 확인해보겠습니다.
#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 init(QueueType* q)
{
q->rear = q->front = 0;
}
// 포화 상태 검출 함수
int isfull(QueueType* q)
{
return ((q->rear + 1) % MAX_QUEUE_SIZE == q->front);
}
// 공백 상태 검출 함수
int isempty(QueueType* q)
{
return (q->front == q->rear);
}
void enqueue(QueueType* q, element item)
{
if (isfull(q)) {
fprintf(stderr, "큐 포화 상태 에러\n");
return;
}
// 선형큐에서는 1 증가하고 삽입, 원형큐에서는 1 증가하고 원형 인덱스 연산 후 삽입
q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
q->data[q->rear] = item;
}
element dequeue(QueueType* q)
{
if (isempty(q)) {
fprintf(stderr, "큐 공백 상태 에러");
return -1;
}
// 선형큐에서는 1 증가하고 삭제, 원형큐에서는 1 증가하고 원형 인덱스 연산 후 삭제
q->front = (q->front + 1) % MAX_QUEUE_SIZE;
return q->data[q->front];
}
void queue_print(QueueType* q)
{
printf("QUEUE(front=%d rear=%d) = ", q->front, q->rear);
if (!isempty(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(void) {
element e;
QueueType q;
init(&q);
while (!isfull(&q))
{
printf("정수를 입력하세요 : ");
scanf("%d", &e);
enqueue(&q, e);
queue_print(&q);
}
printf("큐가 포화상태입니다. \n\n");
printf("--데이터 삭제 단계--\n");
while (!isempty(&q))
{
e = dequeue(&q);
printf("꺼내진 데이터 : %d \n", e);
queue_print(&q);
}
printf("큐가 공백상태입니다. \n\n");
return 0;
}
다음 포스팅에서는 연결리스트로 큐를 구현해보도록 하겠습니다. 감사합니다.
참고 문헌 : C언어로 쉽게 풀어쓴 자료구조 - 생능출판
'C 자료구조' 카테고리의 다른 글
| [C 자료구조] 그래프 ADT 구현 : 인접행렬 / 인접리스트 (2) | 2023.05.25 |
|---|---|
| [C 자료구조] 그래프(Graph)의 종류 : 인접 행렬(Adjacent matrix) vs 인접 리스트(Adjacent list) (1) | 2023.05.24 |
| [C 자료구조] 큐(Queue) - 연결리스트 구현 (0) | 2023.05.24 |
| [C 자료구조] 연결리스트(Linked List) (0) | 2023.05.22 |
| [C 자료구조] 스택(Stack) (3) | 2023.05.22 |