원형 큐

원형 큐

 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 가 끝지점에 도달해도 앞칸이 비어있는 경우 앞 칸에 데이터를 집어넣을 수 있음을 알 수 있다.