C언어 자료구조 큐 개념과 구현(2) queue

1.이번시간은 배열로 큐를 구현해보도록 합니다.

1)큐에서의 배열 realloacte()  

//참고 front가 항상 rear보다 오른쪽에 있는 것은 아니다. 





헤더파일은 동일. 

 

 #include <stdbool.h> 

 

 typedef int Item;

 typedef struct queue_type *Queue;

 

 Queue create();

 void destroy(Queue q);

 void make_empty(Queue q);

 bool is_empty(Queue q);

 void enqueue(Queue q, Item i);

 Item dequeue(Queue q);

 Item peek(Queue q);

 int get_Size(Queue q);

 

 

 

 struct queue_type {

  Item *contents;

  int front;

  int rear;

  int size;

  int capacity;

 };

 

 void terminate(const char *message)

 {

  printf("%\n", message);

  exit(1); 

 }

 

 int get_size(Queue q)

 {

  return q->size;

 }

 

 Queue create()

 { 

  Queue q = (Queue)malloc(sizeof(struct queue_type));

  if(q == NULL)

   terminate("Error in create: queue could not be created");

  q->contents = (Item *)malloc(INIT_CAPACITY * sizeof(Item));

  if(q->contents == NULL) {

   free(q);

   terminate("Error in create: queue could not be created");

  }

  q->front = 0;

  q->rear = -1;

  q->size = 0;

  q->capacity = INIT_CAPACITY; //100으로 설정 

  return q;

  

 }

 

 void destroy(queue q)

 {

  free(q->contents);

  free(q);

 }

 

 void make_empty(Queue q)

 {

  q->front =0;  //free 할 필요없이 사이즈가 0으로 만든다. 

  q->rear = -1;

  q->size = 0;

 }

 

 bool is_empty(Queue q)

 {

  return q->size == 0;

 }

 

 bool is_full(Queue q)

 {

  return q->size == q->capacity;

 }

 

 void enqueue(Queue q, Item i)

 {

  if (is_full(q))

   reallocate(q);                   //인덱스 0을 가리키도록 하면 맨처음으로 삽입이 된다.  

  q->rear = (q->rear +1)%q->capacity; //1만 증가시키면 배열인덱스 범위가 초과하기 때문에 capacity 를 나눈나머지를 연산한다.  

  q->contents[q->rear] = i;        //ex) rear가 -1일때 +1하면 0이 된다   

  q->size++;

 }

 

 Item dequeue(Queue q)

 {

  if(is_empty(q))

   terminate("Error in dequeue: queue is empty");

   Item result = q->contents[q->front]; 

   q->front = (q->front +1)%q->capacity;

   q->size--;

   return result;

 }

 

 Item peek(Queue q)

 {

  if(is_empty(q))

   terminate("Error in peek: queue is empty");

  return q->contens[q->front];

 }