덱(Deque)의 이해와 구현

큐를 설명하였으니, 이와 관련 있는 덱을 소개하고자 한다. 스택과 큐의 구조를 이해한 사오항에서 덱의 구조는 한줄로 설명이 가능하며, 양방향 리스트 까지 구현해본 경험이 있으면 덱의 구현을 일일히 설명할 필요는 없다.

 

덱의 이해와 ADT의 정의

"큐는 뒤로 넣고 앞으로 빼는 자료구조" 

이러한 느낌으로 덱을 한 문장으로 설명하면 다음과 같다.

"덱은 앞으로도 뒤로도 넣을 수 있고, 앞으로도 뒤로도 뺄수 있는 자료구조"

 

이것으로 덱의 구조는 충분히 설명되었다고 생각한다. dequeue은 double -ended queue 를 줄여서 표현한 것으로, 양방향으로 넣고 뺄수 있다는 사실에 초점이 맞춰져서 지어진 이름이다. 어쨋든 덱은 한방향으로 넣고, 양방향으로 뺄 수 있는 자료구조이기에 스택과 큐의 특성을 모두 갖는 , 혹은 스택과 큐를 조합한  형태의 자료구조로 이해되고 있다. 따라서 덱의 ADT를 구성하는 핵심 함수 네 가지의 기능은 다음과 같다.

 

앞으로 넣기

뒤로 넣기

앞에서 빼기

뒤에서 빼기

 

그럼 이어서 위의 기능을 중심으로 한 덱의 ADT를 정의하겠다. 

 

void Deque(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 DQGetLast(Deque *pdeq);

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

 

참고로 Deque '디큐'로 읽기 쉽다. 그럼에도 불구하고 '덱'으로 발음하는 이유는 '디큐'로 발음할 경우 큐의 dequeue연산과 그 발음이 같아져서 이 둘을 구분하기 어렵기 때문이다. 물론 '디큐'로 읽는 사람도 있다. 그러나 혼란을 줄 수 있으므로 가급적 '덱'으로 읽기 바란다.

 

덱의 구현

덱의 구현을 위해서 우선적으로 해야 할 일은 헤더파일의 정의이다. 그런데 헤더파일을 정의하기 위해서는 구현할 덱의 구조를 결정해야 한다. 물론 덱도 배열을 기반으로, 그리고 연결리스트를 기반으로도 구현이 가능하다. 하지만 우리는 덱의 구현에 가장 어울린다고 알려진 '양방향 연결 리스트'를 기반으로 덱을 구현할 것이다. 양방향 연결 리스트가 , 단방향 연결리스트보다 덱의 구현에 더 잘 어울리는 이유는 다음 함수의 구현과 관련이 있다.

 

Data DQRemoveLast(Deque *pdeq);  //꼬리에 위치한 데이터(노드) 삭제

 

위의 함수는 꼬리에 위치한 노드를 삭제하는 함수인데, 노드가 양방향으로 연결되어 있지 않으면 꼬리에 위치한 노드의 삭제는 간단하지 않다. 때문에 덱의 구현에 있어서 양방향 연결 리스트는 매우 좋은 선택이라 할 수 있다.

그럼 양방향 연결 리스트 기반의 덱을 위한 헤더파일을 정의하겠다.

 

//Deque.h
#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

 

위의 헤더파일에 정의된 구조체 Node를 보면 양방향 연결 리스트를 기반으로 덱이 구현됨을 알 수 있고, 구조체 DLDeque을 보면 head와 tail이 각각 리스트의 머리와 꼬리를 가리키게 됨을 알 수 있다. 즉 다음 구조의 양방향 연결리스트를 구현할 생각이다.

 

head->2-><-4-><-6-><-8-><-10<-tail

2의 prev와 10의 next 에는 NULL이 저장되어 있음

 

그런데 앞서 우리는 다음과 같이, 꼬리를 가리키는 포인터 변수 tail이 없는 구조로 양방향 연결 리스트를 구현한바가 있다.

head->2-><-4-><-6-><-8-><-10->NULL

2의 prev에는 NULL

 

이 둘의 유일한 차이점은 포인터 변수 tail을 둬서 리스트의 꼬리를 가리키게 하느냐 마느냐에 있다. 

물론 tail의 유무를 제외하고 구조적으로는 그 형태가 동일하지만 ADT에 정의된 함수가 다르기 때문에 코드까지 완전히 동일하지는 않다. 하지만 이전에 구현한 내용을 참조하여 쉽게 덱을 구현할 수 있다.

 

//Deque.c
#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 == NULL0   	//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;
    
    if(DQIsEmpty(pdeq))
    	pdeq->tail= newNode;
   	else
    	pdeq->head->prev= newNode;
        
    newNode->prev=NULL;
    pdeq->head = newNode;
}

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

Data DQRemoveFirst(Deque *pdeq)
{
	Node *rnode= pdeq->head;
    Data rdata;
    if(DQIsEmpty(pdeq))
    {
		printf("Deque Memory Error!");
        exit(-1);
   	}
    rdata= pdeq->head->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)
{
	Node *rnode = pdeq->tail;
    Data rdata;
    if(DQIsEmpty(pdeq))
    {
		printf("Deque Memory Error!");
        exit(-1);
   	}
    rdata= pdeq->tail->data;
    
    pdeq->tail = pdeq->tail->prev;
    free(rnode);
    
    if(pdeq->tail == NULL)
    	pdeq->head = NULL;
   	else
    	pdeq->tail->next= NULL;
      
   	return rdata;
}

Data DQGetFirst(pdeq)
{
	  if(DQIsEmpty(pdeq))
    {
		printf("Deque Memory Error!");
        exit(-1);
   	}
    return pdeq->head->data;
}

Data DQGetLast(pdeq)
{
	  if(DQIsEmpty(pdeq))
    {
		printf("Deque Memory Error!");
        exit(-1);
   	}
    return pdeq->tail->data;
}

//DequeMain.c
#include <stdio.h>
#include "Deque.h"

int main()
{
	//Deque의 생성 및 초기화
    Deque deq;
    DequeInit(&deq);
    
    //데이터 넣기 1차
    DQAddFirst(&deq, 3);
    DQAddFirst(&deq, 2);
    DQAddFirst(&deq, 1);
   	
    DQAddLast(&deq, 4);
    DQAddLast(&deq, 5);
    DQAddLast(&deq, 6);
    
    //데이터 꺼내기 1차
    while(!DQIsEmpty(&deq))
    	printf("%d ", DQRemoveFirst(&deq));
        
   	printf("\n");
    
    //데이터 넣기 2차
    DQAddFirst(&deq, 3);
    DQAddFirst(&deq, 2);
    DQAddFirst(&deq, 1);
    
    DQAddLast(&deq, 4);
    DQAddLast(&deq, 5);
    DQAddLast(&deq, 6);
    
    //데이터 꺼내기 2차
    while(!DQIsEmpty(&deq))
    	printf("%d ", DQRemoveLast(&deq));
        
   	return 0;
}
==========================실행결과=======================
1 2 3 4 5 6
6 5 4 3 2 1 

위의 main함수에서는 덱을 대표하는 4개의 함수를 확인하기 위해서, 데이터를 덱의 머리와 꼬리에 넣어보고, 또 이를 머리에서 그리고 꼬리에서 꺼내어 그 결과를 출력하였다.