큐의 ADT(Abstract Data Type)

큐의 배열 기반 구현

다음을 염두하며 큐를 배열로 구현하자.

#include <stdio.h>

# define SIZE 5

int queue[SIZE]={-1,};

int front = -1;
int rear = -1;

void enqueue(int data){

   if(rear == SIZE -1){
     printf("------queue is full------\n");
     return;
	 }
   queue[++rear] = data;

}

int dequeue(){
  
  if(front == rear){
    printf("------queue is empty------\n");
	  return -1;
	}
	int data = queue[++front];
  queue[front] = -1;
}

void printQueue(){

  int i;
  printf("Order : first - in\n");
  for(i= front+1; i<=rear; i++){
	   printf("%d ", queue[i]);
	}
	printf("\n");
}

int main(){
  int i;
  for(i=0;i<5;i++){
    enqueue(i);
	}
  printQueue();

  for(i=0;i<5;i++){
    dequeue(i);
	}
  printQueue();

  printf("rear : %d \n", rear);
  enqueue(10);

  return 0;
}

// 실행 결과
// Order : first - in
// 0 1 2 3 4 
// Order : first - in
// 
// rear : 4 
// ------queue is full------

=> 큐를 배열로 구현하면 이정도 일 것이다. 하지만 여기에는 치명적인 단점이 있다.
=> 처음에 enqueue를 다섯번 호출하여 큐의 상태가 모두 가득차게 하였다. 이후 dequeue를 다섯번 호출하여 큐가 모두 비워지게 하였다. 따라서 큐는 비었으므로 다시 데이터를 넣을 수 있지만 그럼에도 큐에 데이터를 넣을 수 없다. 왜냐하면 enqueue를 호출했을 때 rear의 값이 4로 큐의 끝지점을 가리키고 있어 가득찼다고 인식하여 넣을 수 없고 rear를 1 증가시켜 넣는다 해도 그 위치는 큐의 바깥이라 그럴 수 없기 때문이다.
그러면 이러한 상황에 큐의 사이즈를 늘려서 enqueue를 호출할까? 가능한 얘기이고 스택의 경우 사이즈를 2배 늘려서 사용하므로 나쁘지 않은 생각인것 같다. 하지만 이렇게 사이즈를 늘리는 경우는 dequeue해서 앞의 index의 칸들이 비어있는 경우, 이 칸들은 낭비할 수 밖에 없다. 큐의 사이즈는 점차 커지지만 정작 모든 칸들을 사용할 수없는 문제가 발생한다. 이를 해결하기 위해 원형 큐가 등장했다.

원형 큐는 원형큐.md 에서 두둥!