큐 배열 기반으로 구현하기
앞서 큐에 대해서 이야기할때 큐는 선입선출의 방식을 사용한다고 했다.
그럼 필요한 것은 머리와 꼬리이다. 머리를 Front, 꼬리를 Rear이라고 하기로 한다.
enqueue 연산
우선적으로 데이터를 입력할 때는 제일 먼저 들어오는 데이터를 머리와 꼬리가 동시에 가르키고, 이후 두 번째 데이터부터는 들어오는 데이터가 꼬리가 되도록 설정한다.
위 사진을 보면 길이가 4인 배열에 enqueue 연산이 이루어지는 모습을 볼 수 있다.
dequeue 연산
dequeue 연산은 두 가지를 생각해 볼 수 있다.
첫 번째
첫 번째는 보편적으로 데이터를 추출하면 다음 데이터들을 앞으로 이동시키는 방식
이 방법은 두 가지 문제가 있다.
- 첫 번째는 Front가 굳이 필요가 없다는 점이다
- 두 번째는 매번 dequeue 연산을 진행할 때마다 데이터들을 앞으로 한 칸씩 이동시켜야하는 단점이다.
위 두 가지 문제점으로 인해 배열 기반의 큐에서는 이 방식을 사용하지 않는다.
두 번째
두 번째 방식은 데이터는 그대로 두고 Front를 이동하는 방식이다.
이 방법은 앞의 문제점은 해결되어 있지만 다른 문제가 있다.
배열이 그림의 맨 마지막 상태일 때 D를 enqueue하면 다음 그림과 같이 된다.
문자 D가 배열의 끝에 저장되고 따라서 Rear을 더 이상 이동시킬 수 없다.
그리고 배열의 앞부분은 비어있는 상태에서 enqueue연산을 진행하기도 어렵다.
이 문제를 해결하기 위해서는 Rear을 맨 앞으로 이동시키면 된다.
Rear이 배열의 끝에 도달하면 맨 앞으로 이동하고, Front 또한 Rear을 따라서 배열의 앞으로 이동하면 된다.
이런 형태로 동작하는 배열 기반의 큐를 원형 큐(Circular queue)라고 한다.
Circular Queue
원형 큐는 다음과 같은 모습으로 생각할 수 있다.
그럼 다시 처음부터 빈 원형 큐에 데이터를 넣는 과정을 살펴보자
처음에 enqueue를 통해 데이터 A가 들어오면 Front와 Rear이 둘 다 첫 번째 데이터를 가르킨다
이후 추가되는 데이터를 Rear이 가르키게 되는 과정이다.
그리고 다시 dequeue를 하는 과정을 살펴보면
Front가 이동을 하면서 데이터를 꺼낸다.
하지만 여기서 또 문제가 있다 데이터가 가득찼을 때와 모두 비웠을 때의 모습이다.
그림을 보면 문제를 알 수 있다. 그림을 보면 데이터가 가득 찼을때나 비었을 때나 Front가 Rear을 앞서고 있는 것을 볼 수 있다.
여기서 문제는 Front와 Rear을 통해 큐가 가득차있는지 비어있는지 알 수가 없는 점이다.
이런 문제를 해결하기 위해서는 다른 방식을 사용해야 한다.
여러가지 해결책이 있을 수 있지만, 배열을 꽉 채우지 않는 방법을 사용한다.
이는 배열의 길이가 N일 때, 데이터가 N-1개 채워졌을 때, 이를 꽉 찬것으로 간주하는 것이다.
이는 저장공간 하나를 낭비하는 부분이 있지만, 저장 공간 한개로 문제점을 해결할 수 있기 때문에 좋은 방법이라고 볼 수 있다.
그럼 이제 Front와 Rear의 상대적 위치를 통해 비어있는지 꽉 차 있는지를 구분한다.
우선 다시 처음부터 데이터가 비어있는 모습을 보자
이는 아까 처음 모습과 같다.
그리고 이제 다시 데이터를 채우는 과정을 진행한다면
이제 새롭게 정의한 원형 큐는 다음과 같이 동작한다
- enqueue 연산을 하면 Rear이 가르키는 위치를 한 칸 이동시킨 후, Rear이 가르키는 위치에 데이터를 저장한다.
- dequeue 연산을 하면 Front가 가르키는 위치를 한 칸 이동시킨 후, Front가 가르키는 위치에 저장된 데이터를 반환하고 꺼낸다.
그럼 이제 큐가 비어있는 상태와 꽉 찬 상태를 서로 비교할 수 있다.
- 원형 큐가 비어있는 상태 : Front와 Rear이 같은 위치를 가르킨다
- 원형 큐가 차있는 상태 : Front가 Rear이 가르키는 위치 앞을 가르킨다
보통 일반적으로 배열 기반의 큐라고 하면 원형 큐를 의미한다고 볼 수 있다.
원형 큐의 구현
그럼 이제 원형 큐를 코드로 옮기는 구현을 해볼 차례이다.
헤더파일
#ifndef __C_QUEUE_H__
#define __C_QUEUE_H__
#define TRUE 1
#define FALSE 0
#define QUE_LEN 100
typedef int Data;
typedef struct _cQueue
{
int front;
int rear;
Data queArr[QUE_LEN];
} CQueue;
typedef CQueue Queue;
void QueueInit(Queue *pq);
int QIsEmpty(Queue *pq);
void EnQueue(Queue *pq, Data data);
Data DeQueue(Queue *pq);
Data QPeek(Queue *pq);
#endif소스파일
#include <stdio.h>
#include <stdlib.h>
#include "CircularQueue.h"
void QueueInit(Queue *pq)
{
pq->front = 0;
pq->rear = 0;
}
int QIsEmpty(Queue *pq)
{
if (pq->front == pq->rear)
{
return TRUE;
}
else
{
return FALSE;
}
}
int NextPosIdx(int pos)
{
if (pos == QUE_LEN - 1)
{
return 0;
}
else
{
return pos + 1;
}
}
void EnQueue(Queue *pq, Data data)
{
if (NextPosIdx(pq->rear) == pq->front)
{
printf("Queue Memory Error!");
exit(-1);
}
pq->rear = NextPosIdx(pq->rear);
pq->queArr[pq->rear] = data;
}
Data DeQueue(Queue *pq)
{
if (QIsEmpty(pq))
{
printf("Queue Memory Error!");
exit(-1);
}
pq->front = NextPosIdx(pq->front);
return pq->queArr[pq->front];
}
Data QPeek(Queue *pq)
{
if (QIsEmpty(pq))
{
printf("Queue Memory Error!");
exit(-1);
}
return pq->queArr[NextPosIdx(pq->front)];
}메인파일
#include <stdio.h>
#include "CircularQueue.h"
int main()
{
Queue q;
QueueInit(&q);
EnQueue(&q, 1);
EnQueue(&q, 2);
EnQueue(&q, 3);
EnQueue(&q, 4);
EnQueue(&q, 5);
printf("QPeek 먼저 사용해보기 : %d \n", QPeek(&q));
while (!QIsEmpty(&q))
{
printf("%d ", DeQueue(&q));
}
return 0;
}