Chapter 07. 덱(Deque)의 이해와 구현

주의 사항!

• 이 글은 제가 직접 공부하는 중에 작성되고 있습니다.
• 따라서 제가 이해하는 그대로의 내용이 포함됩니다.
• 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다.

양방향 연결 리스트, 스택, 큐를 제대로 이해하고 있다면 덱을 이해하는 것은 껌입니다. 덱에 대해 한 줄로 설명하자면 다음과 같습니다.

 

"덱은 데이터를 앞으로도 뒤로도 입력 가능하며, 앞으로도 뒤로도 출력이 가능한 큐 혹은 스택 혹은 두 개 모두와 같다" 

 

스택은 데이터를 앞으로 넣었으면 앞으로 빼야 하는 것이 특징입니다. 반면 큐는 데이터를 앞으로 넣었으면 뒤로 빼야 하는 것이 특징입니다. 그런데 덱은 데이터를 앞으로 넣었으면 앞으로도 뒤로도 뺄 수 있고, 이는 데이터를 뒤에서 넣었을 때도 마찬가지라는 특징을 가지고 있습니다.

 

덱의 이름이 Deque인 것이 마치 큐의 Dequeue 함수와 유사합니다. 하지만 Deque라는 이름은 'Double-Ended Queue'를 줄여서 표현한 것으로, 데이터를 양방향으로 넣고 뺄 수 있다는 사실에 초점이 맞춰져서 지어진 이름입니다.

 

덱에 대한 설명은 위 설명만으로 충분하다고 생각합니다. 이제 덱의 ADT를 정의해 보겠습니다. 다음은 덱의 일반적인 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를 바탕으로 덱의 헤더 파일을 정의할 차례입니다. 헤더 파일의 정의에 앞서 배열 기반으로 구현할 것인지 연결 리스트를 기반으로 구현할 것인지를 결정해야 합니다. 두 가지 방법 다 덱을 구현할 수는 있으나, 덱의 구현에 가장 적합하다고 알려진 양방향 연결 리스트를 기반으로 구현해 보겠습니다.

//DLLBDeque.h 헤더 파일로 저장
#ifndef DLLBDEQUE_H
#define DLLBDEQUE_H

#define TRUE 1
#define FALSE 0

typedef int Data;

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

typedef struct DLLBDeque
{
	Node* head;
	Node* tail;
}DLLBDeque;

typedef DLLBDeque 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

이제 위 헤더 파일을 바탕으로 각 함수들을 정의해 보겠습니다.

//DLLBDeque.c 소스 파일로 저장 
#include "DLLBDeque.h"
#include <stdio.h>
#include <stdlib.h>

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

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

void DQAddFirst(Deque* pdeq, Data data)
{
	Node* newNode = (Node*)malloc(sizeof(Node));
	if (newNode == NULL)
	{
		printf("메모리 공간이 부족합니다. \n");
		exit(1);
	}

	newNode->data = data;

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

	pdeq->head = newNode;
}

void DQAddLast(Deque* pdeq, Data data)
{
	Node* newNode = (Node*)malloc(sizeof(Node));
	if (newNode == NULL)
	{
		printf("메모리 공간이 부족합니다. \n");
		exit(1);
	}

	newNode->data = data;

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

Data DQRemoveFirst(Deque* pdeq)
{
	Node* delNode = pdeq->head;
	Data delData = delNode->data;

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

	free(delNode);
	return delData;
}

Data DQRemoveLast(Deque* pdeq)
{
	Node* delNode = pdeq->tail;
	Data delData = delNode->data;

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

	free(delNode);
	return delData;

}

Data DQGetFirst(Deque* pdeq)
{
	return pdeq->head->data;
}

Data DQGetLast(Deque* pdeq)
{
	return pdeq->tail->data;
}

위 코드에 대해서는 따로 설명이 필요 없을 것 같습니다. 코드의 이해가 어렵지 않고, 또 위 코드대로 작성하지 않아도 직접 구현해볼 수도 있기 때문입니다.

 

이제 양방향 연결 리스트 기반 덱의 구현이 끝났습니다. 이를 테스트해 볼 main 함수를 정의하고 실행결과를 보겠습니다.

//main.c 소스 파일로 저장
#include "DLLBDeque.h"
#include <stdio.h>

int main(void)
{
	//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));
	}
	printf("\n");

	return 0;
}

/*
실행결과

1 2 3 4 5 6
6 5 4 3 2 1

*/