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

이번에는 큐를 동적으로 만들어 보겠습니다.

큐(Queue) - 동적 - 구조

큐를 동적으로 만들 때는 다음과 같은 구조체를 이용하게 됩니다.

#include<stdio.h>
#include<malloc.h>
struct QueueNode
{
    QueueNode *Link;
    int VALUE;
};
struct Queue
{
    QueueNode *header;//제일 앞 포인터
    QueueNode *tailer;//제일 뒤 포인터
    QueueNode *Temp_Tail;//제일 뒤 바로 앞 포인터
};

이번엔 포인터를 3개를 사용했습니다. 큐를 만들때 이번엔 단순연결 리스트를 이용하여 만들었습니다. 단순 연결리스트는 다시 뒤로 돌아가기 힘들기 때문에 포인터를 하나더 썼습니다.

큐(Queue) - 동적 - ADT

• void init()
  
  
  

  void init(Queue *Target_Queue)
  {
      Target_Queue->header = NULL;
      Target_Queue->tailer = NULL;
      Target_Queue->Temp_Tail = NULL;
  }

  초기화 함수입니다. 포인터들을 초기화 해 줍니다.
  
  
• bool is_empty()
  
  
  

  bool is_empty(Queue *Target_Queue)
  {
      if (Target_Queue->header == NULL)
      {
          printf("비었습니다.\n");
          return true;
      }
      else
      {
          printf("아직 값이 있습니다.\n");
          return false;
      }
  }

  포인터 상태를 확인하여 비었는지 찼는지 확인을 합니다. 동적 할당을 하여 만드는 큐는 메모리 사이즈가 되는 만큼 만들 수 있기 때문에 가득 찬 경우는 제외했습니다. 가득찬경우 true 그렇지 않은 경우 false를 반환합니다
  
  

• void enqueue()
  
  
  

  void enqueue(Queue *Target_Queue, int Item)
  {
      QueueNode *New = (QueueNode *)malloc(sizeof(QueueNode));
      if (is_empty(Target_Queue))//첫 번째 노드 추가
      {
          Target_Queue->header = New;
          Target_Queue->tailer = New;
          New->VALUE = Item;
          New->Link = NULL;
          return;
      }
      else
          if (Target_Queue->Temp_Tail == NULL)// 두 번째 노드 추가
          {
              New->Link = Target_Queue->header;
              New->VALUE = Item;
              Target_Queue->Temp_Tail = New;
              Target_Queue->header = New;
          }
          else// 이후 노드 추가
          {
          New->Link = Target_Queue->header;
          New->VALUE = Item;
          Target_Queue->header = New;
          }
  }

  큐에 데이터를 추가하는 함수입니다. 포인터 3개를 할당해야하기 때문에 3부분으로 나눠서 단계별로 포인터들을 할당하게 됩니다.
  
  
  

• int dequeue()
  
  
  

  int dequeue(Queue *Target_Queue)
  {
      int Value = 0;
      QueueNode *Temp= NULL;
      QueueNode *Delete = NULL;
      QueueNode *Cur = Target_Queue->header;
      while (Cur!=Target_Queue->Temp_Tail)
      {
          Temp = Cur;//temp Tail 이전의 노드를 가리키는 포인터 저장
          Cur = Cur->Link;
      }
      Delete = Target_Queue->tailer;
      Value = Delete->VALUE;
      Target_Queue->Temp_Tail = Temp;
      Target_Queue->tailer = Temp->Link;
      Target_Queue->tailer->Link = NULL;
      free(Delete);
      return Value;
  }

  큐에서 Temp_Tail 포인터가 가르키는 노드 이전의 노드를 카리키는 노드를 이용하여 가장 마지막 노드를 삭제하기 전 tailer 노드와 Temp_Tail 노드를 할당할 위치를 저장하게 됩니다. 위에서 Temp 포인터는 기존의 Temp_Tail이 가리키던 노드의 바로 이전 노드를 가리키는 포인터 이며 Delete 노드는 동적해제할 노드를 저장하는 포인터입니다.
  
  

• void printing()
  
  
  

  void printing(Queue *Target_Queue)
  {
      QueueNode *Cur = Target_Queue->header;
      while (Cur!=NULL)
      {
          printf("%d ", Cur->VALUE);
          Cur = Cur->Link;
      }
      printf("\n");
  }

  출력하는 함수입니다. 제일 끝으로 갈때까지 출력하게 됩니다.
  
  

사실 큐는 이중연결로 짜도 상관은 없지만 뒤에서 포스팅할 덱(deque)에서 이중연결으로 구현하며 또 덱으로도 큐를 표현할 수 있기 때문에 단순연결로 한번 짜봤습니다. 다음 포스팅에서는 덱(deque)을 포스팅 하겠습니다.