원형 큐
- 큐를 실제로 구현하기 위한 방법론
- rear가 끝지점에 있을 때 enqueue를 하는 경우 한칸 앞으로 가는 것이 아니라 맨 앞칸이 비어있는 경우 맨 앞에 채워넣는 구조. 맨 앞과 맨 끝이 연결되어 있어 원형 큐라고 한다.(꼬리에 꼬리를 무는 구조)
rear = (rear + 1) % QUEUE_SIZE;
front = (front + 1) % QUEUE_:SIZE;
=> 맨 끝에 있을 때 +1 하면 인덱스 0을 가리켜야 하므로 큐의 칸의 수만큼 나눠줘야 한다.(모듈러 연산 i mod j)
=> 따라서 원형 큐를 구현하면 맨 앞칸들이 비워있는 경우에도 앞칸으로 돌아가 enqueue()할 수 있게 된다.따라서 rear가 맨 끝지점에 있는 경우에도 enqueue()을 할 수 있게 되었다.(단, 맨 앞칸이 비어있는 경우)
원형 큐가 꽉 차면 안되고 한 칸 비어야 하는 이유
= 원형 큐가 한 칸 비어있는 것이 꽉 찬 경우라고 간주하는 이유
=> 일반적으로 rear 의 값과 front의 값이 같은 경우, 큐는 비어있다.하지만 큐를 다 채울 경우에도 rear와 front의 값이 같기 때문에 프로그램은 이 때 큐가 가득찼는지 아니면 비어있는지 구분을 할 수 없게되고 enqueue와 dequeue 하는 데 지장이 생긴다. 큐에 값이 들어갔는지 일일히 검색해도 되지만 이는 rear와 front의 값을 비교하는 것보다 시간이 낭비되기 때문에 좋지않다.
근데 한 칸 비어있는 경우를 꽉 찬 경우라고 생각하면 문제는 해결된다.
한 칸 비어있는 경우는 front가 rear보다 한 칸 앞서 있는 경우로 (rear+1)%QUEUE_SIZE == front로 확인 가능하고 이는 비어있는 경우(rear == front)를 체킹하는 코드와 같지 않으므로 프로그램이 이제는 큐가 가득찬 경우와 큐가 비어있는 경우를 분별가능해져 enqueue와 dequeue를 수월하게 할 수 있다.
원형 큐 구현
#include <stdio.h>
## define QUEUE_SIZE 5
## define TRUE 1
## define FALSE 0
int queue[QUEUE_SIZE]={-1,};
int front = 0;
int rear = 0;
int isQueueEmpty(){
return front == rear ? TRUE : FALSE;
}
int isQueueFull(){
return (rear+1)%(QUEUE_SIZE) == front ? TRUE : FALSE;
}
void enqueue(int data){
if(isQueueFull() == TRUE){
printf("------queue is full------\n");
return;
}
rear = (rear+1)%QUEUE_SIZE;
queue[rear] = data;
}
int dequeue(){
if(isQueueEmpty() == TRUE){
printf("------queue is empty------\n");
return -1;
}
front = (front+1)%QUEUE_SIZE;
int data = queue[front];
queue[front] = -1;
}
void printQueue(){
int i;
for(i= 0; i<QUEUE_SIZE; i++){
int data = queue[i];
if(data != -1){
printf("%d ", queue[i]);
}
}
printf("\n");
}
int main(){
int i;
for(i=0;i<QUEUE_SIZE;i++){
enqueue(i);
}
printQueue();
for(i=0;i<QUEUE_SIZE-1;i++){
dequeue(i);
}
printQueue();
printf("rear : %d \n", rear);
enqueue(10);
printQueue();
return 0;
}
// ------queue is full------
// Order : first - in
// 0 1 2 3
// Order : first - in
//
// rear : 4
// Order : first - in
// 10
=> 큐에 큐의 사이즈만큼(5) enqueue하면 사이즈 - 1(4)만큼만 채울 수 있음을 알 수 있다.(꽉찬 경우 == 한 칸 비어있는 경우)
=> 큐.md 에서 구현했던 큐와 다르게 원형 큐는 rear 가 끝지점에 도달해도 앞칸이 비어있는 경우 앞 칸에 데이터를 집어넣을 수 있음을 알 수 있다.