[C로 만드는 자료구조]큐(Queue) - 배열

큐(Queue) - 구조

우선 큐란 스텍과는 다르게 나가는 출구와 들어가는 입구가 따로 있는 자료구조입니다. 그리고 먼저 들어온것이 먼져 나가기 때문에 FIFO(First-In-First-Out) 자료구조라고도 부릅니다. 큐를 배열로 표현할 때는 2가지 경우가 있으며 다음과 같은 특징을 가집니다..

• 선형 큐 : 배열을 선형으로 사용하여 큐를 구현
  
  
  

• 삽입을 계속하기 위해서는 요소들을 이동시켜야한다.
  
  
• 문제점이 많기 때문에 사용되지 않는다.
  
  
  
• 원형 큐 : 배열을 원형으로 사용(생각)하여 큐를 구현(이것을 사용)
  
  

큐(Queue) - 원형 큐를 이용

원형큐를 이용하게 되면 다음과 같은 원형 형식의 배열을 사용하게 됩니다. 하지만 배열에서는 앞과 뒤를 구분할 것이 필요하기 떄문에 두 가지 포인터를 사용하여 인덱스를 구분합니다.

• front : 첫 번째 요소 하나 앞의 인덱스
• rear : 마지막 요소의 인덱스

큐(Queue) - 공백상태 그리고 포화상태

배열로 만든 원형큐이기 때문에 공백상태와 포화상태를 구별하는 것이 중요합니다. 우선 공백상태의 경우엔 두 포인터가 같을 때 입니다. 그리고 포화상태는 앞 포인터가 뒷 포인터와 1칸을 두고 있을 때 포화상태로 봅니다. 왜냐하면 공백상태가 두 포인터 위치가 같을 때 이기 때문에 배열을 다 채워버리면 포인터가 같은 위치에 있어버리게 되고 포화상태인지 공백상태인지 구분이 되지 않기 때문입니다. 그렇기 떄문에 배열로 구현한 원형큐에서는 한 칸을 비워둬야 합니다.

큐(Queue) - 구현

#include<stdio.h>
#define Max_Size 5
struct element
{
    int data;
};
struct Queue
{
    element queue[Max_Size];
    element *Output;
    element *Input;
};

큐는 다음과 같은 구조체들로 구현하게 됩니다. 각 배열 요소요소를 담당하는 element 구조체와 규의 집단을 구성하고 앞, 뒤 포인터 하나씩을 가지고 있는 Queue 구조체로 구현합니다.

큐(Queue) - ADT(배열)

• init()
  
  

  void init(Queue *Target_Queue)
  {
      Target_Queue->Output = Target_Queue->queue;
      Target_Queue->Input = Target_Queue->queue;
  }

  초기화 함수입니다. 앞 뒤를 나타내는 포인터 두개를 같은 자리에 둠으로써 비어있는 큐를 하나 만듭니다.
  
  

• is empty()
  
  
  

  bool is_empty(Queue *Target_Queue)
  {
      if (Target_Queue->Input == Target_Queue->Output)
      {
          printf("queue is empty\n");
          return true;
      }
      else
      {
          printf("queue is not empty\n");
          return false;
      }
  }

  비었는지 판단하는 함수입니다. 비었을땐 true를 아닐때는 false를 리턴합니다.
  
  

• is_full()
  
  

  bool is_full(Queue *Target_Queue)
  {
      if (Target_Queue->Output - Target_Queue->Input == 1)
      {
          printf("queue is full\n");
          return true;
      }
      else 
      if (Target_Queue->Input == Target_Queue->queue + 4 && Target_Queue->Output == Target_Queue->queue)
      {
          printf("queue is full\n");
          return true;
      }
      else
      {
          printf("queue is not full\n");
          return false;
      }
  }

  꽉 찼는지 확인하는 함수입니다. 원래는 다음과 같은 형태를 가져야 하는데 VS상에서 먹히질 않아서 이렇게 만들어 봤습니다. 원래는 이렇게 만들곤 합니다.
  
  
  

  bool is_full(Queue *Target_Queue)
  {
      if ((Target_Queue->Output + 1) % Max_Size == Target_Queue->Input)
      {
          printf("queue is full\n");
          return true;
      }
      else
      {
          printf("queue is not full\n");
          return false;
      }
  }

  밑에 소스는 정상적으로 컴파일 되지 않습니다.
  
  

• void enqueue()
  
  

  void enqueue(Queue *Target_Queue,int item)
  {
      if (is_full(Target_Queue))
      {
          return;
      }
      Target_Queue->Input->data = item;
      if (Target_Queue->queue + 5 == Target_Queue->Input)
      {
          Target_Queue->Input = Target_Queue->queue;
      }
      else
      {
          Target_Queue->Input++;
      }
  }

  
  위 소스는 큐에 데이터를 삽입하는 소스입니다. 삽입은 Input 포인터를 이용하여 삽입하게 됩니다. 또한 삽입이 끝나면 포인터를 증가시켜 다음 배열 칸에 들어갈 준비를 하며 제일 끝에 있는 경우 제일 앞으로 다시 옮겨주게 됩니다.
  
  

• void dequeue()
  
  
  

  int dequeue(Queue *Target_Queue)
  {
      int return_value = 0;
      if (is_empty(Target_Queue))
      {
          return 0;
      }
      return_value = Target_Queue->Output->data;
      if (Target_Queue->queue + 5 == Target_Queue->Output)
      {
          Target_Queue->Output = Target_Queue->queue;
      }
      else
      {
          Target_Queue->Output++;
      }
      return return_value;
  }

  
  데이터를 삭제하는 소스입니다. 삭제를 Output 포인터를 이용하여 삭제하게 됩니다. 삭제하기전에 값을 저장해둔다음 포인터를 감소시켜 줄었음을 나타내게 되며 삭제한 데이터 값을 리턴하면 됩니다.
  
  

• void printing()
  
  
  

  void printing(Queue *Target_Queue)
  {
      for (element *i = Target_Queue->Output; i < Target_Queue->Input; i++)
      {
          printf("%d -> ", i->data);
          if (i == Target_Queue->queue + 4)
              i = Target_Queue->queue;
      }
      printf("\n");
  }

  데이터들을 출력해주는 함수입니다. 포인터를 하나씩 증가시켜서 출력하며 끝에 도달했을 때 다시 앞으로 옮겨서 계속 진행하게 됩니다.
  
  
  
  

이상으로 배열로 만드는 원형 큐를 알아보았습니다. 다음 포스팅에서는 동적으로 만드는 큐에 대해서 포스팅 해보겠습니다.