덱(Deque)의 이해와 구현

덱은 큐와 관련이 있다
스텍과 큐를 이해한 이후 덱을 보면 이해하기 쉽다

큐는 빨대같은 모양으로 뒤로 넣고 앞으로 빼는 구조라고 한다면, 덱은 앞, 뒤 구분없이 넣고 뺄 수 있는 구조이다.

Deque는 double-ended queue의 줄임말로 이름 그대로 양방향으로 넣고 빼고 할 수 있다.
양방향으로 데이터를 넣고 뺄 수 있기 때문에 스택과 큐의 특성을 모두 가진, 스택과 큐가 조합된 자료구조로 볼 수 있다.

덱 자료구조의 ADT

• void DequeInit(Deque * pdeq);

  • 덱의 초기화
  • 덱 생성 후 가장 먼저 호출

• int DQIsEmpty(Deque * pdeq);

  • 덱이 비어있는 경우 TRUE(1), 아니면 FALSE(0)을 반환

• void DQAddFirst(Deque * pdeq, Data data);

  • 덱의 머리에 데이터 저장, data로 전달된 값 저장

• void DQAddLast(Deque * pdeq, Data data);

  • 덱의 꼬리에 데이터 저장, data로 전달된 값 저장

• Data DQRemoveFirst(Deque * pdeq);

  • 덱의 머리에 위치한 데이터를 반환하고 제거

• Data DQRemoveLast(Deque * pdeq);

  • 덱의 꼬리에 위치한 데이터를 반환하고 제거

• Data DQGetFirst(Deque * pdeq);

  • 덱의 머리에 위치한 데이터를 소멸하지 않고 반환

• Data DQGetLast(Deque * pdeq);

  • 덱의 꼬리에 위치한 데이터를 소멸하지 않고 반환

덱 자료구조의 ADT의 핵심은 네 가지로

• 앞으로 넣기
• 뒤로 넣기
• 앞에서 빼기
• 뒤에서 빼기

이다.

---

헤더파일

#ifndef __DEQUE_H__
#define __DEQUE_H__

#define TRUE 1
#define FALSE 0

typedef int Data;

typedef struct _node
{
   Data data;
   struct _node *next;
   struct _node *prev;
} Node;

typedef struct _dlDeque
{
   Node *head;
   Node *tail;
} DLDeque;

typedef DLDeque Deque;

void DequeInit(Deque *pdeq);
int DQIsEmpty(Deque *pdeq);

void DQAddFirst(Deque *pdeq, Data data);
void DQAddLast(Deque *pdeq, Data data);

Data DQRemoveFirst(Deque *pdeq);
Data DQRemoveLast(Deque *pdeq);
Data DQGetFirst(Deque *pdeq);
Data DQGetLast(Deque *pdeq);

#endif

소스파일

#include <stdio.h>
#include <stdlib.h>
#include "Deque.h"

void DequeInit(Deque *pdeq)
{
   pdeq->head = NULL;
   pdeq->tail = NULL;
}

int DQIsEmpty(Deque *pdeq)
{
   if (pdeq->head == NULL)
   {
      return TRUE;
   }
   else
   {
      return FALSE;
   }
}

void DQAddFirst(Deque *pdeq, Data data)
{
   Node *newNode = (Node *)malloc(sizeof(Node));
   newNode->data = data;
   newNode->next = pdeq->head;
   newNode->prev = NULL;

   if (!DQIsEmpty(pdeq))
   {
      pdeq->head->prev = newNode;
   }
   else
   {
      pdeq->tail = newNode;
   }

   pdeq->head = newNode;
}

void DQAddLast(Deque *pdeq, Data data)
{
   Node *newNode = (Node *)malloc(sizeof(Node));
   newNode->data = data;
   newNode->prev = pdeq->tail;
   newNode->next = NULL;

   if (!DQIsEmpty(pdeq))
   {
      pdeq->tail->next = newNode;
   }
   else
   {
      pdeq->head = newNode;
   }

   pdeq->tail = newNode;
}

Data DQRemoveFirst(Deque *pdeq)
{
   if (DQIsEmpty(pdeq))
   {
      printf("Deque Memory Error!");
      exit(-1);
   }

   Node *rnode = pdeq->head;
   Data rdata = rnode->data;

   pdeq->head = pdeq->head->next;
   free(rnode);

   if (pdeq->head == NULL)
   {
      pdeq->tail = NULL;
   }
   else
   {
      pdeq->head->prev = NULL;
   }

   return rdata;
}

Data DQRemoveLast(Deque *pdeq)
{
   if (DQIsEmpty(pdeq))
   {
      printf("Deque Memory Error!");
      exit(-1);
   }

   Node *rnode = pdeq->tail;
   Data rdata = rnode->data;

   pdeq->tail = pdeq->tail->prev;
   free(rnode);

   if (pdeq->tail == NULL)
   {
      pdeq->head = NULL;
   }
   else
   {
      pdeq->tail->next = NULL;
   }

   return rdata;
}

Data DQGetFirst(Deque *pdeq)
{
   if (DQIsEmpty(pdeq))
   {
      printf("Deque Memory Error!");
      exit(-1);
   }

   return pdeq->head->data;
}

Data DQGetLast(Deque *pdeq)
{
   if (DQIsEmpty(pdeq))
   {
      printf("Deque Memory Error!");
      exit(-1);
   }

   return pdeq->tail->data;
}

메인파일

#include <stdio.h>
#include "Deque.h"

int main()
{
   Deque dq;
   DequeInit(&dq);

   // 앞으로 넣기
   DQAddFirst(&dq, 1);
   DQAddFirst(&dq, 2);
   DQAddFirst(&dq, 3);

   // 뒤로 넣기
   DQAddLast(&dq, 9);
   DQAddLast(&dq, 8);
   DQAddLast(&dq, 7);

   // 데이터 앞으로 꺼내서 삭제하기
   printf("데이터 앞에서 꺼내기 \n");
   while (!DQIsEmpty(&dq))
   {
      printf("%d ", DQRemoveFirst(&dq));
   }
   printf("\n");

   // 데이터 다시 넣기
   DQAddFirst(&dq, 1);
   DQAddFirst(&dq, 2);
   DQAddFirst(&dq, 3);
   DQAddLast(&dq, 9);
   DQAddLast(&dq, 8);
   DQAddLast(&dq, 7);

   printf("데이터 뒤로 꺼내기 \n");
   while (!DQIsEmpty(&dq))
   {
      printf("%d ", DQRemoveLast(&dq));
   }
   printf("\n");

   return 0;
}

결과

데이터 앞에서 꺼내기 
3 2 1 9 8 7        

데이터 뒤로 꺼내기 
7 8 9 1 2 3