큐큐큐큐큐큐큨큐!
큐는 스택과 비슷한 모양새를 하고있지만 조작하는 방식은 조금 다르다.
큐는 앞뒤가 모두 뚫린 긴 통이라고 생각하면 되는데, 뒤에서 무언가를 집어넣고 앞에서 부터 내용물을 빼내는 구조이다.
즉, 입구와 출구가 서로 다르고 먼저 들어간 데이터가 먼저 나오는 구조를 지니고 잉를 FIFO(First In First Out) 구조라고 한다.
큐의 개념
큐는 입구와 출구가 따로 있는 긴 통이라고 했고 큐를 조작한느 방법은 두가지로 제한되어 있다.
큐를 조작하는 방법은 크게 put 동작과 get 동작이 있다.
(Enqueue, Dequeue 라고 불르기도 하는데, put과 get이 더 짧고 부르기도 편해서 나는 이렇게 할 생각이다.)
일단 큐에 어떤 데이터를 집어넣을때는 뒷쪽(Rear)에서 부터 집어넣고, 이 집어넣는 동작을 Put(혹은 Enqueue) 동작 이라고 한다.
그리고 큐에서 자료를 얻어오는 동작(빼내오는 동작)을 할때는 큐의 앞쪽(Front)에서 부터 얻어오고, 이를 Get(혹은 Dequeue) 동작 이라고 한다.
배열을 이용한 큐의 구현
큐는 스택과 매우 유사하게 생긴 자료구조인걸 위의 그림만 봐도 알 수 있다.
그래서 스택에서 그러했듯이 큐 역시 마찬가지로 배열을 이용해서 큰 문제 없이 쉽게 구현할 수 있다고 생각하는데 반대로 문제가 많다.
일단! 한번 짧게 생각을 해보면, 위의 그림처럼 배열로 큐를 만들때 front와 rear를 표시할 두개의 변수만 있으면 될것같다.
그리고 put과 get을 일단 한번 짜보면 아래처럼 될 것 같다.
int put(int k) {
// rear가 한계를 넘었으면 오버플로우 에러 발생
queue[++rear] = k;
}
int get(void) {
// 큐가 비어있으면 언더플로우 에러 발생
return queue[front++];
}rear와 front는 queue 배열의 앞과 뒤를 나타내는 인덱스다.
근데 위 코드와 같아 put, get 함수를 정의하면 큐에 자료를 집어넣고 빼는 동작을 반복하다 보면 rear와 front는 계속 증가하기만 한다.
그렇다면 결과적으로 큐는 전체적으로 배열을 이동하면서 실제로 저장하고 있는 자료는 몇개 되지 않지만 rear가 배열의 최대 길이를 넘어가면서 오버플로우 에러를 발생할거다!!!! 😱
그렇다면 오버플로우를 방지하기 위해서는 rear가 배열의 끝에 이르렀는지를 검사해서 배열에 끝에 닿았을 경우 큐의 내용을 복사해서 배열의 앞부분으로 옮기는 동작이 필요하다.
으악 keynote로 그리기 힘들다...
여튼 이 부분이 바로 배열로 구현하는 큐의 문제점이다!
저 작업을 하기 싫어서 배열을 무지막지하게 크게 생성해두면 메모리 낭비가 일어날거고, 혹여나 크게 만들어둔 배열의 끝부분에 도달한다면 결국 다시 복사하고 인덱스를 다시 조정하는 일이 일어나야만 한다...!!
그래서 이 문제를 해결하기 위해서는 어찌하면 좋을까~~?
바로 원형 큐(Circular Queue)를 이용하면 해결할 수 있다.
원형 큐
원형 큐는 배열의 첫 요소와 마지막 요소가 붙어서 마리 뱀의 머리가 꼬리를 물고있는 듯한 모양이다.
(그냥 배열의 처음과 마지막이 서로 연결되었다 라고 상상해보자!)
따라서 간단하게 제일 처음 요소의 앞 요소는 제일 마지막 요소가 되고, 제일 마지막 요소의 뒷 요소는 제일 앞 요소라는 조작에 의해서 가능해진다.
그리고 이 조작은 나머지(%) 연산을 이용해서 간단하게 구현할 수 있다.
참고로 원형의 자료구조는 끝이라는 개념이 없이 계속 빙빙빙 돌기만 한다.
그래서 배열을 이용할때의 큐가 이동하여서 한계가 넘는 경우는 없다.
따라서 원형 큐 에서는 큐가 이동을 하지만 한계를 넘지않고 계속 회전을 하게된다.
여기서 중요하게 눈여겨 봐야할 부분은 바로 Rear가 가리키는 위치이다.
위 그림을 보면 Front는 실제로 자료가 저장되어 있는 선두 부분을 가리키고 있지만 Rear는 자료가 저장되어있는 끝 부분을 가리키는게 아니라 그 다음의 빈 공간을 가리키고 있다!!
만약 Rear가 큐의 끝을 가리키고 있다고 가정해보자.
이 경유 큐가 비어있음을 나타내려면 어떻게 해야할까?? front와 rear가 같은 경우겠지~ 라고 생각했다면 놉!
front와 rear가 서로 같다라는 의미는(rear가 큐의 끝을 가리키는 경우에) 하나의 자료가 있음을 의미한다.
따라서 rear가 큐의 끝을 가리키면, 큐가 비어있는 상태를 표현하지 못한다. OMG😨
그렇다면!!!
rear가 큐의 끝 다음의 빈 공간을 가리키게 한다면, front = rear가 되면 이 경우는 정말로 큐가 비었다는 표현이 된다.
여기서 중요한 부분은 바로 원형 큐 에서는 배열로 선언한 크기를 모두 사용할 수 없다, 바로 딱 1개 요소를 사용하지 못하는데 이 부분을 버퍼로 사용해야하기 때문이다.
원형 큐에서 자료가 하나도 없음을 나타내는 것은 front와 rear가 같은 경우이다. 이 경우는 front와 rear사이에 하나도 자료가 없다는 의미가 된다.
만약 원형 큐에 자료가 꽉찬 경우는 어떤식으로 표현할까? 이 경우도 역시 front와 rear는 같게 된다.
원형 큐가 비어있음과 꽉 차있음을 구분하기 위해서 원형큐는 배열의 요소 중 1개를 사용하지 않는다.
즉 front와 rear 사이에 완충작용을 하는 하나의 공간이 배치가 된다.
큐 초기화
#define MAX 10
int queue[MAX];
int front, rear;
void init_queue(void) {
rear = 0;
front = 0;
}
void clear_queue(void) {
front = rear;
}배열로 구현하는 큐의 초기화는 매우 간단한데, front와 rear를 같은 값으로 만들면 큐는 비게된다.
특히 초기화에서는 이 두개의 값을 모두 0으로 만들어 둬야하고, 큐를 비우는 경우는 단순히 front와 rear가 같게만 해주면 된다.
Put
put 동작은 rear가 가리키는 곳에 새로운 값을 큐에 집어 넣는 동작을 말한다.
먼저 put 동작을 하려면 큐가 꽉차있는 상태인지 확인하는 작업이 필요하다.
큐가 꽉차있는지 확인을 하려면 rear의 다음이 front와 같아지는지를 알아보면 되는데, 큐가 꽉차더라도 앞에서 설명한것 처럼 완충지대라는 빈공간이 하나 존재한다.
따라서 큐가 꽉차있다면 rear의 다음이 front가 되게된다.
여기서 rear의 다음이라고 표현한것은, 원형큐의 인덱스로써 만약에 배열의 경계에 도달했을 경우 나머지(%) 연산을 통해서 다시 제일 앞이나 뒤로 돌아가야 하기 때문이다.
또 중요한 부분인데, 원형큐의 인덱스를 1 증가시키려면, 1을 증가시킨 후 반드시 배열의 크기로 나머지(%) 연산을 수행해야만, 인덱스가 배열의 크기를 벗어나지 않는다!!!
int put(int k) {
if((rear + 1) % MAX == front) {
printf("\nQueue Overflow\n");
return -1;
}
queue[rear++] = k;
rear %= MAX;
return k;
}Get
다음은 front가 가리키는 곳의 값을 가지고 오는 get 함수다.
먼저 get 동작을 위해서는 큐가 비어있는 상태인지 아닌지를 확인해야 한다. 당연하지만 비어있는 큐에서는 어떠한 값도 얻어낼수 없기 때문이다.
그리고 큐가 비어있는지를 확인하려면 front와 rear가 같은 값인지를 확인하면 된다.
다음으로 front값이 현재의 큐에서 가장 앞(선두)을 가리키는 값이기 때문에, 반환해줘야할 값은 바로 queue[front] 값이다.
값을 얻은 다음으로는 front를 다음 요소로 이동 시켜야 하는데, 다음 요소로의 이동은 front에 1을 더한 다음 배열의 크기로 나머지(%) 연산을 하면 된다.
int get(void) {
int value;
if(rear == front) {
printf("\nQueue Underflow\n");
return -1;
}
value = queue[front++];
front %= MAX;
return value;
}전체 코드
확실히 리스트를 구현하기 위해서 구조체를 만들고 포인터를 이용해서 링크를 조작해주는 부분이 번거롭기는 하지만, 배열의 단점을 보완하기 때문에 더 편한것 같다...
다음은 리스트로 큐를 구현하는걸 해볼 차례~
//
// main.c
// Queue_Array
//
// Created by 박재현 on 2024/05/10.
//
#include <stdio.h>
#define MAX 10
int queue[MAX];
int front, rear;
void init_queue(void) {
rear = 0;
front = 0;
}
void clear_queue(void) {
front = rear;
}
int put(int k) {
if((rear + 1) % MAX == front) {
printf("\nQueue Overflow\n");
return -1;
}
queue[rear++] = k;
rear %= MAX;
return k;
}
int get(void) {
int value;
if(rear == front) {
printf("\nQueue Underflow\n");
return -1;
}
value = queue[front++];
front %= MAX;
return value;
}
void print_queue(void) {
for(int i = front; i != rear; i = (i + 1) % MAX) {
printf("%-6d", queue[i]);
}
printf("\n");
}
int main(int argc, const char * argv[]) {
int i;
init_queue();
printf("\nPut 5, 4, 7, 8, 2, 1\n");
put(5);
put(4);
put(7);
put(8);
put(2);
put(1);
print_queue();
printf("\nGet\n");
i = get();
print_queue();
printf("\nGetting value is %d\n", i);
printf("\nPut 3, 2, 5, 7\n");
put(3);
put(2);
put(5);
put(7);
print_queue();
printf("\nCurrently queue is full, try to put 3");
put(3);
print_queue();
printf("\nInitialize queue\n");
clear_queue();
print_queue();
printf("\nCurrently queue is empty, try to get");
i = get();
print_queue();
printf("\nGetting value is %d\n", i);
return 0;
}실행 결과
