덱 (Deque)

덱 (Deque)

덱은 Double-Ended Queue의 줄임말로 큐의 전단과 후단에서 모두 삽입과 삭제가 가능한 큐를 의미합니다.

덱은 스택과 큐의 연산들을 모두 가지고 있습니다.

예를 들면 add_front, delete_front 연산은 스택의 push, pop

add_rear, delete_front 연산은 큐의 enqueue, dequeue 연산과 같습니다.

추가로 덱은 get_front, get_rear, delete_rear를 가지고 있습니다.

(대소문자의 큰 의미는 없습니다)

덱은 보통 이중 연결 리스트로 구현됩니다.

- 그 이유는 전단과 후단에서 모두 삽입, 삭제가 가능해야 하기 때문에 양쪽으로 링크를 가지고 있어야 편리하기 때문입니다.

- 이중 연결 리스트의 첫 번째 노드와 마지막 노드를 가리키는 포인터를 동시에 가지고 있어야 합니다. 그래서 덱과 관련된 변수는 첫 번째 노드를 가리키는 변수인 head와 마지막 노드를 가리키고 있는 tail이 됩니다.

덱의 구현 (이중 연결 리스트 이용)

#include <stdio.h>

#include <stdlib.h>

#define TRUE 1

#define FALSE 0

typedef int element;           // 요소의 타입

typedef struct DlistNode {  // 노드의 타입

  element data;

  struct DlistNode *llink;     //  왼쪽 링크

  struct DlistNode *rlink;     //  오른쪽 링크

} DlistNode;

typedef sturct DequeType{  // 덱의 타입

  DlistNode *head;             // 덱의 처음

  DlistNode *tail;                // 덱의 끝

} DequeType;

void error(char *message)

{

  fprintf(stderr, "%s\n", message);

  exit(1);

}

// 덱의 초기화

void init(DequeType *dq) 

{

  dq->head = dq->tail = NULL;  // 덱의 처음과 끝을 NULL로 세팅

}

// 노드 생성

DlistNode *create_node(DlistNode *llink, element item, DlistNode *rlink)

{

  DlistNode *node = (DlistNode *)malloc(sizeof(DlistNode));  // 노드 생성하면서 동적 메모리 할당

  if( node == NULL ) error("메모리 할당 오류");

  node->llink = llink;            // 왼쪽 링크, 오른쪽 링크와 데이터를 직접 생성

  node->data = item;

  node->rlink = rlink;

  return node;

}

int is_empty(DequeType *dq)

{

  if(dq->head == NULL ) return TRUE;

  else return FALSE;

}

// rear에 아이템 추가 연산

void add_rear(DequeType *dq, element item)

{

  DlistNode *new_node = create_node(dq->tail, item, NULL);  // 맨 끝에 아이템을 추가하기 때문에 오른쪽 링크는 NULL

  if( is_empty(dq))                 // 덱이 비었으면 맨 앞에 노드 추가

     dq->head = new_node;

  else {

     dq->tail->rlink = new_node;   // 그게 아니라면 맨 끝 노드의 오른쪽 링크에 노드 추가

     dq->tail = new_node;            //  그리고 새롭게 추가된 노드가 맨 끝 노드가 됨

  }

}

// front에 아이템 추가 연산

void add_front(DequeType *dq, element item)

{

  DlistNode *new_node = create_node(NULL, item, dq->head);  //  맨 앞에 노드를 추가하기 때문에 왼쪽 링크는 NULL

  if( is_empty(dq))                   // 덱이 비었으면

     dq->tail = new_node;         // 맨 끝에 새로운 노드 추가

  else {

     dq->head->llink = new_node;   // 그게 아니라면 맨 앞 노드의 왼쪽 링크에 새로운 노드를 추가

     dq->head = new_node;            //  맨 앞에 새로운 노드 추가

  }

}

// front의 아이템 삭제 연산

element delete_front(DequeType *dq)

{

  element item;                      // 지울 아이템의 빈공간 생성

  DlistNode *removed_node;    // 지울 노드의 빈공간 생성

  if(is_empty(dq)) error("공백 덱에서 삭제");

  else {

    removed_node = dq->head;       // 빈 노드 공간에 덱의 맨 앞 노드 넣기 (front의 삭제라서)

    item = removed_node->data;     // 빈 아이템 공간에 덱의 맨 앞 노드(복사본) 삭제할 데이터 넣기

    dq->head = dq->head->rlink;    // 덱의 첫 부분은 오른쪽 링크(두 번째)에 있었던 데이터로 변경

    free(removed_node);                 // 메모리 공간 반납

    if(dq->head == NULL)               

       dq->tail = NULL;                   // 공백일 경우 덱의 맨 끝은 NULL

    else

       dq->head->llink = NULL;        // 그게 아니라면 덱의 맨 처음의 왼쪽 링크는 NULL

  }

  return item;                                //  추출한 데이터 리턴

}

element delete_rear(DequeType *dq)

{

  element item;                            // 지울 아이템의 빈공간 생성

  DlistNode *removed_node;         // 지울 노드의 빈공간 생성

  if(is_empty(dq)) error("공백 덱에서의 삭제");

  else {

    removed_node = dq->tail;        // 빈 노드 공간에 덱의 맨 끝 노드 넣기 (rear의 삭제)

    item = removed_node->data;   // 빈 아이템 공간에 덱의 맨 끝 노드(복사본) 삭제할 데이터 넣기

    dq->tail = dq->tail->llink;        // 덱의 맨 끝은 왼쪽 링크(맨 마지막 -1)에 있었던 데이터로 변경

    free(removed_node);               // 메모리 공간 반납

    if(dq->tail == NULL)

      dq->head = NULL;                // 공백일 경우 덱의 맨 처음은 NULL

    else

      dq->tail->rlink = NULL;          // 그게 아니라면 덱의 맨 끝의 오른쪽 링크는 NULL

  }

  return item;                               // 추출한 데이터 리턴

}

void display(DequeType *dq)

{

  DlistNode *p;

  printf("(");

  for(p = dq->head; p != NULL; p = p->link)    // 덱의 첫 노드부터 맨 끝까지 데이터 출력

     printf("%d ", p->data);

  printf(")\n");

}

void main()

{

  DequeType deque;

  init(&deque);

  add_front(&deque, 10);    // deque( 10 )

  add_front(&deque, 20);    // deque ( 20 10 )

  add_rear(&deque, 30);     // deque ( 20 10 30 )

  display(&deque);

  delete_front(&deque);      // deque ( 10 30 )

  delete_rear(&deque);       // deque ( 10 )

  display(&deque);

}

결과 : 

(20 10 30)

(10 )