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

덱(Deque) - 동적 - 특징과 정의

Deque이란 Double Ended Queue의 준말로 기존의 큐와는 다르게 앞뒤 어디로든 자료를 넣을 수 있고 어디로든 자료를 뺄수 있는 자료구조 형태를 의미합니다. 전반적인 기능들은 큐와 같기 때문에 배열로는 구현을 안하고 동적으로만 구현을 하겠습니다.

덱은 다음과 같은 구조체를 사용하여 만들게 됩니다.

#include<stdio.h>
#include<malloc.h>
 
struct Node
{
    int Item;
    Node *Prev;
    Node *Next;
};
struct Deque
{
    Node *header;
    Node *tailer;
};

그냥 느낌상으로는 이중 연결 리스트정도의 느낌입니다.

덱(Deque) - 동적 - ADT

• void init_Deque()
  
  
  

  void init_Deque(Deque *Target_Deque)
  {
      Target_Deque->header = NULL;
      Target_Deque->tailer = NULL;
  }

  덱을 만든 후 초기화 하는 함수입니다. 덱 내부의 포인터들을 초기화 해줍니다. 
  
  
  

• void Input_Head()
  
  
  

  void Input_Head(Deque *Target_Deque, int Item)
  {
      Node *New = (Node *)malloc(sizeof(Node));
      if (Target_Deque->header == NULL)
      {
          Target_Deque->header = New;
          Target_Deque->tailer = New;
          New->Item = Item;
          New->Next = NULL;
          New->Prev = NULL;
          return;
      }
      Target_Deque->header->Prev = New;
      New->Next = Target_Deque->header;
      Target_Deque->header = New;
      New->Item = Item;
      New->Prev = NULL;
  }

  앞에서 추가 하는 함수 입니다. 처음 추가할 때와 그 이후를 구분하였습니다. 이중연결이기 때문에 앞 뒤에 대한 포인터를 지정해 주어야 합니다.
  
  

• void Input_Tail()
  
  
  

  void Input_Tail(Deque *Target_Deque, int Item)
  {
      Node *New = (Node *)malloc(sizeof(Node));
      if (Target_Deque->tailer == NULL)
      {
          Target_Deque->header = New;
          Target_Deque->tailer = New;
          New->Item = Item;
          New->Next = NULL;
          New->Prev = NULL;
          return;
      }
      New->Item = Item;
      Target_Deque->tailer->Next = New;
      New->Prev = Target_Deque->tailer;
      Target_Deque->tailer = New;
      New->Next = NULL;
  }

  Input_Head와 같습니다. 다른 것은 뒤에 넣을 때는 기존의 값들의 제일 마지막에 넣는것이기 때문에 tailer 포인터를 기준으로 삽입하게 됩니다.
  
  

• int Output_Head()
  
  

  int Output_Head(Deque *Target_Deque)
  {
      if (Target_Deque->header == NULL)
      {
          printf("The Deque is empty\n");
          return 0;
      }
      int return_value;
      Node *Cur = NULL;
      return_value = Target_Deque->header->Item;
      Target_Deque->header->Next->Prev = NULL;
      Cur = Target_Deque->header;
      Target_Deque->header = Target_Deque->header->Next;
      free(Cur);
      return return_value;
  }

  덱의 제일 앞에서 데이터를 빼내는 함수입니다. header 포인터를 옮겨 주어야합니다.
  
  

• int Output_Tail()
  
  

  int Output_tail(Deque *Target_Deque)
  {
      if (Target_Deque->tailer == NULL)
      {
          printf("The Deque is empty\n");
          return 0;
      }
      int return_value = 0;
      Node *Cur = NULL;
      return_value = Target_Deque->tailer->Item;
      Target_Deque->tailer->Prev->Next = NULL;
      Cur = Target_Deque->tailer;
      Target_Deque->tailer = Target_Deque->tailer->Prev;
      free(Cur);
      return return_value;
  }

  덱의 제일 뒤에서 데이터를 빼내는 함수입니다. tailer 포인터를 옮겨주어야합니다.
  
  

• void printing()
  
  

  void printing(Deque *Target_Deque)
  {
      Node *Cur = Target_Deque->header;
      while (Cur != NULL)
      {
          printf("%d ", Cur->Item);
          Cur = Cur->Next;
      }
      printf("\n");
  }

  출력하는 함수입니다. header 포인터부터 시작해서 NULL을 만날 때까지 출력을 합니다.
  
  
  

전반적으로는 단순 이중 연결 리스트와 비슷한 모습니다. 덱(deque)은 스텍(Stack)이나 큐(queue)로도 쓸 수도 있는데요

ADT를 출력으로 Input_Head()함수를 입력으로 Output_Head()함수를 출력으로 쓰거나

ADT를 출력으로 Input_Tail()함수를 입력으로 Output_Tail()를 출력으로 쓰게되면 스텍처럼 동작하게 되며

ADT를 출력으로 Input_Head()함수를 입력으로 Output_Tail()함수를 출력으로 쓰거나

ADT를 출력으로 Input_Tail()함수를 입력으로 Output_Headl()를 쓰게되면 스텍처럼 동작하게 됩니다.

다음 포스팅에서는 트리(Tree)에 대해서 포스팅하겠습니다.