큐는 앞서 설명한 스택과 함께 언급되고 또 비교되는 자료구조이다. 스택은 먼저 들어간 데이터가 나중에 나오는 구조인 반면, 큐는 먼저 들어간 데이터가 먼저 나오는 구조이다. 이것이 스택과 큐의 유일한 차이점이다.
큐(Queue)에 대한 이해
큐의 이해를 위해서 별도의 예는 필요하지 않다. 큐는 우리에게 매우 익숙한 자료구조 이기 때문이다.
예를들어 대중교통이나 패스트푸드점에서 주문을 할 때 줄을 섰던걸 생각해보면 된다.
즉 줄을 섰던게 큐의 구성이랑 같기 때문이다.
이렇듯 큐는 선입선출 구조의 자료구조이다. 때문에 'FIFO(First-in, First-out) 구조의 자료구조'라고 불린다.
큐의 ADT정의
스택과 마찬가지로 큐의 ADT도 정형화된 편이다. 그럼 큐의 핵심이라 할 수 있는 두가지 연산을 소개하겠다.
enqueue : 큐에 데이터를 넣는 연산
dequeue : 큐에서 데이터를 꺼내는 연산
스택에서 데이터를 넣고 빼는 연산을 가리켜 각각 push, pop이라 하는 것처럼, 큐에서 데이터를 빼는 연산에 대해서도 각각 enque, dequeue 라는 별도의 이름을 붙여주고 있다. 그럼 이어서 큐의 ADT를 확인하자. 물론 이것이 큐의 보편적인 ADT이다.
큐 자료구조의 ADT
void QueueInit(Queue *pq);
-큐의 초기화를 진행한다.
-큐 생성 후 제일 먼저 호출되어야 하는 함수이다.
int QIsEmpty(Queue *pq);
-큐가 빈 경우 TRUE(1)을, 그렇지 않은 경우 FALSE(0)을 반환한다.
void Enqueue(Queue *pq, Data data);
-큐에 데이터를 저장한다. 매개 변수 data로 전달된 값을 저장한다.
Data Dequeue(Queue *pq);
-저장순서가 가장 앞선 데이터를 삭제한다.
-삭제된 데이터는 반환된다.
-본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 한다.
Data QPeek(Queue *pq);
-저장순서가 가장 앞선 데이터를 반환하되 삭제하지 않는다.
-본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 한다.
위의 ADT에서는 이름 충돌을 막기 위해 두 함수 이름 앞에 Q를 붙였다.
QIsEmpty, QPeek
이제 큐를 구현해볼텐데, 큐 역시 스택과 마찬가지로 배열을 기반으로, 그리고 연결 리스트를 기반으로 구현이 가능하다. 따라서 이번에도 배열 기반의 큐와 연결 리스트 기반의 큐를 각각 구현해볼 것이다.
큐의 배열 기반 구현
배열 기반의 큐를 구현하기에 앞서 먼저 그 구조를 고민해야 한다. 큐는 스택과 큰차이를 보이지 않지만 , 스택과 달리 고민할 것이 몇가지 더 있기 때문이다.
큐의 구현에 대한 논리
처음 큐를 접하면 다음과 같이 생각하는 것이 보통이다.
"스택과 큐의 차이점이 앞에서 꺼내느냐 뒤에서 꺼내냐에 있으니, 이전에 구현에 놓은 스택을 대상으로 꺼내는 방법만 조금 변경하면 큐가 될것 같다"
하지만 큐의 구현모델을 알게되면 이보다는 큰 차이가 있다고 느낄 것이다. 그럼 다음 과정을 보면서 현 모델을 설명하겠다. 다음 그림에서는 길이가 4인 배열 대상의 enqueue 연산을 보이는데, 그림에서 F는 front의 약자로 큐의 머리를 , R은 Rear의 약자로 큐의 꼬리를 가리키는 일종의 변수를 의미한다.
enqueue A
| A |
F , R ->A를 가리킴
enqueue B
| A | B |
F는 A를 R은 B를 가리킴
enqueue C
| A | B | C |
F는 A를 R은 C를 가리킴
위의 과정에서 F가 가리키는 것이 큐의 머리이고, R이 가리키는 것이 큐의 꼬리이다. 따라서 enqueue 연산 시 R이 그 다음칸을 가리키게 되고, 그 자리에 새 데이터가 저장된다.
그렇다면 dequeue 연산 시에는 어떠한 데이터를 반환하고 소멸해야 할까? F가 가리키는 데이터가 저장순서가 가장 앞선 데이터 이므로 F가 가리키는 대상으로 dequeue 연산을 진행해야한다.
즉 F를 참조하여 dequeue 연산을 하고, R을 참조하여 enqueue 연산을 한다. 따라서 큐는 '뒤로 넣고 앞으로 빼는 자료구조'라고도 한다.
이제 위 과정의 마지막 상태에서 dequeue연산을 진행하겠다.
| A | B | C |
F는 A를 R은 C를 가리킴
dequeue
| B | C |
F는 B를 R은 C를 가리킴
dequeue
| C |
F와 R은 C를 가리킴
위 과정에서 보이는 방식은, dequeue 연산 시 반환할 데이터를 배열의 맨 앞부분에 위치 시키는 방식으로 가장 보편적으로 인식하는 배열의 삭제방법을 적용한 것이다. 사실 이 방법을 적용하면 dequeue 연산의 대상이 맨 앞부분에 위치하므로, 그림에서 보인 것과 달리 F가 불필요하다. 하지만 이 방식은 dequeue연산 시마다 저장된 데이터를 한 칸씩 이동시켜야 하는 단점이 있다. 때문에 배열 기반의 큐에서는 위의 방식으로 dequeue 연산을 진행하지 않는다. 그럼 실제로 적용하는 dequeue연산의 방법을 소개하겠다.
| A | B | C |
F는 A를 R은 C를 가리킴
dequeue
| B | C |
F는 B를 R은 C를 가리킴
dequeue
| C |
F와 R은 C를 가리킴
위 과정에서는 dequeue연산 시 F를 이동시키고 있다. 이 방식을 취하게 되면 dequeue의 과정에서 데이터의 이동이 필요치 않다. 그저 F가 가리키는 위치만 한 칸 오른쪽으로 옮기면 그뿐이다. 하지만 이 방법도 완전하지는 않다. 다음과 같은 경우가 발생하기 때문이다.
enqueue D
| C | D |
F는 C를 R은 D를 가리킴
위에 그림은 문자 D가 배열의 끝에 저장된 상황이다. 때문에 더 이상 R을 오른쪽으로 이동시킬 수 없다. 그런데 dequeue 연산도 몇 차례 진행이 되어 배열의 앞 부분은 비어있다. 이 상황에서 우리는 어떻게 추가로 enqueue연산을 진행해야 하는가?
"R을 배열의 앞부분으로 이동시키면된다"
쉽게 말해서 R을 회전시키는 것이다. R이 배열의 끝에 도달하면, 다시 맨 앞으로 이동시켜서 R이 회전하게 만드는 것이다. 물론 R을 뒤쫒아 가는 F도 배열의 끝에 도달하면 회전해야 한다. 그리고 이러한 방식으로 동작하는 배열 기반 큐를 가리켜 '원형 큐 (circular queue)'라 한다. 논리적으로 배열이 원형의 형태를 갖춘다고 해서 붙여진 이름이다.
원형 큐(Circular Queue)의 소개
앞서 우리는 R과 F를 회전시켜서, 큐를 구성하는 배열을 효율적으로 사용하자는 결론에 도달했다. 그런데 R과 F를 회전시킨다는 것은 배열을 다음의 형태로 바라본다는 뜻이 된다.
때문에 우리는 실제로 원형 큐를 구현하기 까지, 원형 큐를 논리적으로 위 그림의 형태로 바라보기로 하겠다. 원형 큐도 앞서 보인 큐와 마찬가지로 첫 번째 데이터가 추가되는 순간 F와 R이 동시에 그 데이터를 가리킨다. 그 녀석이 큐의 머리이자 꼬리이기 때문이다. 따라서 위 그림은 다음의 과정을 거쳐서 완성된 것이다.
enqueue B
enqueue C
그리고 위의 그림을 대상으로 총 2회에 걸쳐서 dequeue 연산을 진행하면 , 다음의 상태에 이른다.
그럼 이제 구현만 하면 될까? 아니다, 위의 모델에서도 생각해 볼 문제가 있다. 이의 확인을 위해서 맨 처음의 과정인 A, B, C 데이터가 있을 경우에 enqueue 연산을 진행하고, C데이터만있는 경우에 dequeue 연산을 진행해보자. 즉 큐를 완전히 채워보고 또 완전히 비워보자는 것이다. 그럼 다음 그림을 통해서 그 결과를 확인하자.
위 그림을 보면 , 큐가 꽉찬 경우나 텅빈 경우나 F가 R보다 한 칸 앞선 위치를 가리킴을 알 수 있다. 그리고 이것이 의미하는 바는 다음과 같다.
"F와 R의 위치만 가지고는 꽉찬 경우와 텅빈 경우를 구분할 수 없다."
그럼 이에 대한 해결책은 무엇일까? 다양한 해결책이 있겠지만, 우리는 다음의 해결책을 사용할 것이다.
"배열을 꽉 채우지 않는다. 꽉 채우면 구분이 안되니 꽉 채우지 않는 것이다"
이것이 의미하는 바는 다음과 같다.
"배열의 길이가 N이라면 데이터 N-1개 채워졌을때, 이를 꽉 찬것으로 간주한다"
이렇게하면 저장 공간을 하나 낭비하게 되지만 , 문제 해결로 인해 얻는 것이 더 많다. 그리고 혹시나 해서 말하지만 F와 R의 위치는 계속 회전이 된다. 따라서 F와 R의 상대적 위치 차를 통해서 , 텅빈 경우와 꽉 찬 경우를 구분해야 한다. 그럼 이러한 결론을 반영해서 큐가 채워지는 과정을 다시 한번 정리해보자.
다음 그림에서는 큐가 처음으로 생성되어 텅 빈경우를 보고 있다.
위 그림에서는 F와 R이 같은 위치를 가리키고 있다. 이전에는 첫 번째 데이터가 저장된 경우, 이 데이터가 머리이자 꼬리이기 때문에 F와 R이 같은 위치를 가리키게 하였다. 하지만 지금은 공간 하나를 비우기로 하였으니, F와 R이 같은 위치를 가리키는 이 상태가 텅 빈 상황을 표현한 것이 된다. 그럼 이상태에서 데이터를 채워나가보겠다.
위 그림을 통해서 다음 두 가지 사실을 정리할 수 있다. 이는 실제 큐의 구현을 위해서 인지하고 있어야 하는 내용들이다.
"enqueue 연산 시, R이 가리키는 위치를 한칸 이동시킨 다음에, R이 가리키는 위치에 데이터를 저장한다."
"dequeue 연산 시 F가 가리키는 위치를 한칸 이동시킨 다음에, F가 가리키는 위치에 저장된 데이터를 반환 및 소멸한다."
이 중에서 특히 dequeue 연산 시에도 F가 가리키는 위치를 우선 한 칸 이동한다는 사실을 잊지 말자.
그리고 비록 dequeue 연산의 결과를 그림으로 보이지는 않았지만, 위 그림을 통해서 충분히 예상할 수 있을 것이다. 그럼 마지막으로 한번 더 dequeue연산을 진행해서 큐를 꽉 채워 보겠다.
이로서 우리가 구현할 큐의 특성 두 가지를 다음과 같이 추가로 정리할 수 있다.
원형 큐가 텅 빈 상태 : F와 R이 동일한 위치를 가리킨다.
원형 큐가 꽉 찬 상태 : R이 가리키는 위치의 앞을 F가 가리킨다.
이러한 특성은 실제 큐의 구현에서 그대로 코드로 옮겨진다. 따라서 별도로 정리하고 이해해 둘 필요가 있다.
원형 큐 (Circular Queue)의 구현
배열 기반의 큐라 하면 대부분의 경우 원형 큐를 의미한다고 봐도 무리가 아니다. 따라서 우리도 배열 기반의 큐를 대표하는 원형 큐를 구현하고자 한다. 그런데 우리는 앞서 그림을 통해서 원형 큐의 논리를 완전히 이해하였다. 때문의 원형 큐의 구현은 부담스럽지 않다. 배열을 힘껏 휘어서 두 개의 끝을 붙이는 것도 아니고, 그저 F와 R이 배열의 끝에 도달했을 때 앞으로 이동시키는 것이 전부이다.
//CircularQueue.h
#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; //그림을 통해서 F라 표현했던 멤버
int rear; //그림을 통해서 R이라 표현했던 멤버
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
앞서 정의한 큐의 ADT를 기반으로 위의 헤더파일을 정의하였다. 그런데 그림에서 F와 R로 표현했던 변수를 위의 구조체 CQueue 에서는 각각 front와 rear로 이름을 지었다. 이후에 종종 front는 F로 rear은 R로 표현할 것이다.
이어서 헤더파일에 선언된 함수의 구현을 보일 차례인데 ,그에 앞서 다음 함수를 먼저 소개한다.
이 함수는 간단하지만 원형 큐의 핵심이라 할 수 있다.
int NextPostIdx(int pos) //큐의 다음 위치에 해당하는 인덱스 값 반환
{
if(pos ==QUE_LEN-1)
return 0;
else
return pos+1;
}
이는 큐의 다음 위치에 해당하는 배열의 인덱스 값을 반환하는 함수이다. 따라서 1을 전달하면 2를 반환하고, pos를 전달하면 pos+1을 반환한다. 그러나 큐의 길이보다 하나 작은 값이 인자로 전달되면 0을 반환한다. 이것이 무엇을 의미하는가? 바로 F와 R이 배열의 끝에 도달했으므로, 앞으로 이동해야 함을 의미한다. 즉 F와 R의 회전을 돕는 함수이다.
이제 원형 큐의 구현을 보일 텐데, 위의 NextPosIdx 함수를 이해했다면 이미 반은 이해한 것이다. 실제 구현의 내용은 어렵지 않다.
//CircularQueue.c
#include <stdio.h>
#include <stdlib.h>
#include "CircularQueue.h"
void QueueInit(Queue *pq) //텅 빈 경우 front와 rear은 동일 위치를 가리킴
{
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(NextPostIdx(pq->rear) == pq->front) //큐가 꽉 찼다면,
{
printf("Queue Memory Error!");
exit(-1);
}
pq->rear = NextPostIdx(pq->rear); //rear을 한 칸 이동
pq->queArr[pq->rear] = data; //rear이 가리키는 곳에 데이터 저장
}
Data Dequeue(Queue *pq)
{
if(QIsEmpty(pq))
{
printf("Queue Memory Error!");
exit(-1);
}
pq->fornt = NextPostIdx(pq->front); //front를 한 칸 이동
return pq->queArr[pq->front]; //front가 가리키는 데이터 반환
}
Data QPeek(Queue *pq)
{
if(QIsEmpty(pq))
{
printf("Queue Memory Error!");
exit(-1);
}
return pq->queArr[NextPosIdx(pq->front)];
}이번에는 우리가 구현할 원형 큐의 동작을 확인하기 위핸 main 함수를 소개하겠다.
//CircularQueueMain.c
#include <stdio.h>
#include "CircularQueue.h"
int main()
{
//QUeue 의 생성 및 초기화
Queue q;
QueueInit(&q);
//데이터 넣기
Enqueue(&q, 1); Enqueue(&q, 2);
Enqueue(&q, 3); Enqueue(&q, 4);
Enqueue(&q, 5);
//데이터 꺼내기
while(!QIsEmpty(&q))
printf("%d ", Dequeue(&q));
return 0;
}
===================실행 결과======================
1 2 3 4 5이로써 원형 큐에 대한 설명이 마무리 되었다.
'휴지통 > 자료구조-C' 카테고리의 다른 글
| 덱(Deque)의 이해와 구현 (0) | 2021.03.01 |
|---|---|
| 큐(Queue)의 연결리스트 기반 구현 (0) | 2021.02.28 |
| 스택을 활용한 계산기 구현 (0) | 2021.02.24 |
| 스택 (0) | 2021.02.23 |
| 양방향 연결 리스트 (0) | 2021.02.16 |