덱(Deque) 구현하기
덱 알아보기
Deque은 double ended queue의 약자로 데이터의 양 끝에서 추가, 삭제 등이 가능한 자료 구조이다. Deque는 "deck"과 발음이 같게 덱이라고 읽는다.
덱은 양 끝에서 데이터에 접근하는 것이 가능하므로 스택과 큐를 사용할 때보다 유연하게 활용할 수 있다. 또한 연결 리스트의 데이터 추가, 삭제 시간 복잡도를 비교했을 때, 연결 리스트는 O(n)인데 비해 덱은 O(1)이다.
스택과 큐로 활용하기
덱은 스택과 큐로도 활용할 수 있다. 데이터의 입력과 출력을 서로 같은 쪽에서 수행하면 (왼쪽으로만 넣고 왼쪽으로만 빼면) 스택으로, 데이터의 입력과 출력을 서로 반대 방향에서 수행하면 큐로 사용할 수 있다.
덱을 지금까지 배운 스택과 큐로 활용하는 방법을 그림으로 소개해보고자 한다. 이 부분에 대한 설명이 글의 말미에 main 함수를 이해하는데 도움이 될 것 같아서 적게 되었다.
가령 아래 그림처럼 왼쪽에서 첫 번째 데이터를 넣었다고 가정해보자. (물론 이런 모양보단 원형 큐에 가깝게 구현했지만 편의상 선형 배열로 나타내었다. 또한 통일성을 위해 지난번 원형 큐처럼 배열의 크기 MAX_LEN의 값을 8로 정의하였다.)
front와 rear의 값은 모두 0이다. 이제 계속해서 왼쪽으로 데이터를 삽입할 것이다. 두 번째 데이터가 저장되면 아래와 같은 그림이 된다.
"김철수", "박영희"에 이어 "이진우", "홍길동"을 차례로 삽입한 후의 그림은 아래와 같다.
이제 데이터를 빼낼 차례이다. 우리가 데이터를 삽입한 순서는 "김철수", "박영희", "이진우", "홍길동"이다. 이 상태에서 만약 데이터를 삽입한 방향과 반대인 오른쪽에서만 계속해서 빼내면, 삽입한 순서와 똑같이 삭제될 것이다. 즉 큐와 같은 선입선출(FIFO)이다.
만약 반대로 삽입한 방향과 같은 방향에서 계속해서 데이터를 빼내면, 삽입한 순서와 정반대로 삭제된다. 스택과 같은 후입선출(LIFO)이다.
물론 스택과 큐가 필요하면 그냥 스택과 큐를 사용하는 것이 나을 수도 있다. 하지만 덱을 사용하면 훨씬 유연하게 사용할 수 있다는 장점이 있다.
구현 방법
원형 큐에서 구현한 방법을 활용하여 덱을 구현하였다. 한 방향에서 넣는 데이터가 다른 방향에서 넣는 데이터보다 많은 경우에 다른 방향에 공간이 있는데도 데이터를 저장하지 못하는 경우를 방지하기 위함이다. 따라서 원형 큐처럼 front와 rear 두 개의 변수로 양 끝의 인덱스를 가리키게 하였다.
원형 큐에서 사용한 함수의 이름을 따오려 했으나 생각이 바뀌어 Oracle에서 제공하는 Java의 덱 인터페이스(새 창)를 참고하여 함수의 이름을 정했다. 다수의 사람들에게 익숙한 이름이 사용하기에 편리하고, 또 나중에 필드에 나가면 내가 자료 구조를 직접 만들기보단 라이브러리를 사용할 일이 더 많이 생길 수 있기 때문에 어떤 단어를 함수의 이름으로 사용하는지 알아두면 좋을 것 같다고 판단했다.
이번에 구현한 덱 역시 4개의 파일로 구성된다. DataType.h, Deque.h, Deque.c, main.c이다.
DataType.h
덱의 배열에 저장되는 요소를 구조체로 정의한 파일이다. 수정된 내용은 없다.
#pragma once
#define TRUE 1
#define FALSE 0
typedef struct Element { // 배열 요소의 자료형 정의
int age;
char* name;
} Element;Deque.h
구조체 덱에 대한 정의와 관련된 함수의 프로토타입이 정의되어 있다.
#pragma once
#include "DataType.h"
#define MAX_LEN 8
typedef struct {
Element* arr;
int front; // 맨 처음 데이터의 인덱스
int rear; // 맨 뒤 데이터의 인덱스
} Deque;
typedef void (*PrintFunc)(Element* e);
Deque* DQueCreate();
int DQueIsEmpty(Deque* deque);
int DQueAddFirst(Deque* deque, Element e);
int DQueAddLast(Deque* deque, Element e);
int DQueRemoveFirst(Deque* deque, Element* e);
int DQueRemoveLast(Deque* deque, Element* e);
int DQueGetFirst(Deque* deque, Element* e);
int DQueGetLast(Deque* deque, Element* e);
void DQuePrint(Deque* deque, PrintFunc func);
void DQueDestroy(Deque* deque);만약 C언어가 아니라 Java였다면 위처럼 "DQue"라는 이름을 붙일 것 없이 isEmpty 이런 식으로 이름 붙이고 매개 변수도 하나씩 줄일 수 있을 텐데, 구조체에는 함수를 포함시킬 수 없으므로 함수 이름에 DQue를 죄다 붙이고 매개 변수로 구조체 Deque의 포인터형을 전달해줬다.
덱은 양 끝에서 데이터를 추가, 삭제할 수 있으므로 큐와 스택에서 함수의 개수보다 두 배 더 많다.
Remove와 Get의 차이는 Remove가 붙은 함수는 데이터를 배열에서 제거한 것으로 취급하지만, Get이 붙은 함수는 단순히 데이터를 읽어올 뿐 제거하지 않은 것으로 취급하는 것이다.
Deque.c
#include <stdlib.h>
#include <stdio.h>
#include "Deque.h"Deque.h의 내용이 구현되는 deque.c이다. 함수 별로 살펴보도록 한다.
Deque* DQueCreate()
덱을 메모리에서 동적으로 할당 받은 후 초기화하고 덱의 구조체 포인터 형을 반환하는 함수이다.
Deque* DQueCreate()
{
Deque* deque = (Deque*)malloc(sizeof(Deque));
if (deque != NULL) {
deque->arr = (Element*)malloc(sizeof(Element) * MAX_LEN);
if (deque->arr == NULL) {
free(deque);
return NULL;
}
else
deque->front = deque->rear = -1;// front = rear = -1이면 비어 있음
}
return deque;
}주목해야 할 점은 deque의 front와 rear의 값을 -1로 초기화한 것이다. 이 두 값이 -1을 가지면 덱은 비어있는 것으로 판단한다.
int DQueIsEmpty(Deque* deque)
덱에 데이터가 존재하는지 검사하는 함수이다. 데이터가 존재하면 FALSE(0), 존재하지 않으면 TRUE(1)를 반환한다.
int DQueIsEmpty(Deque* deque)
{
if (deque->front == -1 || deque->rear == -1) return TRUE;
else return FALSE;
}앞서 말한 것처럼 덱이 막 생성되어 초기화되면 front와 rear의 값이 -1을 갖는다. 이 함수가 정상적으로 동작하려면 데이터를 빼내는 연산에서 빼낸 데이터가 유일한 데이터였을 때 front와 rear의 값을 다시 -1로 설정하는 과정이 있어야 한다.
int DQueAddFirst(Deque* deque, Element e)
덱의 왼쪽 끝에 데이터를 추가하는 함수이다. 반환형은 정상 작동 여부를 의미한다.
int DQueAddFirst(Deque* deque, Element e)
{
int tmp = (deque->front - 1 + MAX_LEN) % MAX_LEN;
if (tmp == deque->rear) {
printf("데이터를 저장할 수 없습니다. 공간이 부족합니다.\n");
return FALSE;
}
else {
if (DQueIsEmpty(deque))
deque->front = deque->rear = 0;
else
deque->front = tmp;
deque->arr[deque->front] = e;
printf("{ %d, %s } 저장 완료\n", e.age, e.name);
return TRUE;
}
}변수 tmp는 데이터를 추가하게 되었을 때 front가 변화하게 될 값을 의미한다. 이러한 과정이 필요한 이유는 만약 변화한 front의 값이 rear의 값과 같아지면 rear가 가리키는 데이터와 중복되기 때문이다. 또한 front와 rear가 같은 값을 갖는 상황은 덱에 데이터가 오직 한 개 존재할 때여야 한다. 따라서 tmp로 이러한 상황을 방지하는 것이다.
덱이 비어있다면 front와 rear의 값이 0으로 바뀌면서 그 위치에 데이터를 추가한다.
int DQueAddLast(Deque* deque, Element e)
덱의 오른쪽 끝에 데이터를 저장하는 함수이다. 반환값은 동작 여부를 의미한다.
int DQueAddLast(Deque* deque, Element e)
{
int tmp = (deque->rear + 1 + MAX_LEN) % MAX_LEN;
if (tmp == deque->front) {
printf("데이터를 저장할 수 없습니다. 공간이 부족합니다.\n");
return FALSE;
}
else {
if (DQueIsEmpty(deque))
deque->front = deque->rear = 0;
else
deque->rear = tmp;
deque->arr[deque->rear] = e;
printf("{ %d, %s } 저장 완료\n", e.age, e.name);
return TRUE;
}
}DQueAddFirst 함수와 거의 유사하다. 다른 점은 오른쪽 끝에 데이터를 저장하면 변수 rear의 값이 증가한다는 것이다.
int DQueGetFirst(Deque* deque, Element* e)
덱 왼쪽 끝의 데이터를 읽어오는 함수이다. 배열에서 제거하지 않는다.
int DQueGetFirst(Deque* deque, Element* e)
{
if (DQueIsEmpty(deque)) {
printf("데이터가 존재하지 않습니다.\n");
return FALSE;
}
else {
*e = deque->arr[deque->front];
return TRUE;
}
}배열에서 제거하지 않으므로 변수 front의 값도 변하지 않는다.
int DQueGetLast(Deque* deque, Element* e)
덱 오른쪽 끝의 데이터를 읽어오는 함수이다. 배열에서 제거하지 않는다.
int DQueGetLast(Deque* deque, Element* e)
{
if (DQueIsEmpty(deque)) {
printf("데이터가 존재하지 않습니다.\n");
return FALSE;
}
else {
*e = deque->arr[deque->rear];
return TRUE;
}
}DQueGetFirst 함수와 거의 같다.
int DQueRemoveFirst(Deque* deque, Element* e)
덱 왼쪽 끝의 데이터를 전달하고 덱에서 제거하는 함수이다.
int DQueRemoveFirst(Deque* deque, Element* e)
{
if (DQueGetFirst(deque, e)) {
if (deque->rear == deque->front)
deque->rear = deque->front = -1;
else
deque->front = (deque->front + 1) % MAX_LEN;
return TRUE;
}
else return FALSE;
}DQueGetFirst 함수와 내용이 대부분 겹치고 다른 점은 변수 front를 수정하는 일 뿐이므로 DQueGetFirst를 재사용하였다.
int DQueRemoveLast(Deque* deque, Element* e)
덱 오른쪽 끝의 데이터를 전달하고 덱에서 제거하는 함수이다.
int DQueRemoveLast(Deque* deque, Element* e)
{
if (DQueGetLast(deque, e)) {
if (deque->rear == deque->front)
deque->rear = deque->front = -1;
else
deque->rear = (deque->rear - 1 + MAX_LEN) % MAX_LEN;
return TRUE;
}
else return FALSE;
}DQueRemoveFirst 함수와 유사하다.
void DQuePrint(Deque* deque, PrintFunc func)
덱에 저장된 데이터를 모두 출력하는 함수이다. 함수 포인터를 매개 변수로 전달받는다.
void DQuePrint(Deque* deque, PrintFunc func)
{
if (!(DQueIsEmpty(deque))) {
int i = deque->front;
while (i != deque->rear) {
func(&(deque->arr[i]));
i = (i + 1) % MAX_LEN;
}
func(&(deque->arr[i]));
}
}void DQueDestroy(Deque* deque)
동적으로 할당 받았던 덱에 포함된 배열과 덱을 메모리에서 해제하는 함수이다.
void DQueDestroy(Deque* deque)
{
if (deque != NULL) {
free(deque->arr);
free(deque);
}
}main.c
main.c에서 구현한 덱을 테스트해본다. 이번에도 역시 모든 함수를 실행시켜보았다.
또한 글의 머리에서 언급한 것처럼 덱의 한 쪽 방향에서만 데이터를 넣고 같은 방향에서 데이터를 빼서 마치 스택처럼 후입 선출 방식으로 동작하게 하였다. 그 후엔 다시 덱의 한 쪽 방향에서만 데이터를 넣다가 반대쪽 방향에서만 데이터를 빼서 선입선출 방식의 큐처럼 동작하게 하였다.
이렇게 하면 코드가 꽤 길어지기 때문에 실행 결과를 Part 별로 나누어서 보일 것이다.
아래는 본격적으로 테스트를 시작하기 전에 포함해야 하는 코드이다.
#include <stdio.h>
#include "Deque.h"
#include "vld.h"
void printNameAge(Element* e)
{
if (e != NULL)
printf("Name: %s\tAge: %d\n", e->name, e->age);
}
int main(void)
{
Deque* deque = DQueCreate();
if (deque == NULL || deque->arr == NULL) return;
Element e1 = { 24, "김철수" };
Element e2 = { 23, "박영희" };
Element e3 = { 21, "이진우" };
Element e4 = { 45, "홍길동" };
Element e5 = { 24, "김승규" };
Element e6 = { 24, "박성겸" };
Element e7 = { 24, "진우진" };
Element e8 = { 24, "문도언" };
Element e9 = { 24, "한윤학" };
Element e10 = { 24, "이현택" };Part ① 스택으로 사용하기
소스 코드
DQueAddFirst(deque, e1);
DQueAddFirst(deque, e2);
DQueAddFirst(deque, e3);
DQueAddFirst(deque, e4);
DQueAddFirst(deque, e5);
DQueAddFirst(deque, e6);
DQueAddFirst(deque, e7);
DQueAddFirst(deque, e8);
DQueAddFirst(deque, e9);
DQueAddFirst(deque, e10);DQueAddFirst 함수로 데이터를 추가한다. call by value 방식으로 값이 전달된다.
DQuePrint(deque, printNameAge);DQuePrint 함수로 현재 덱의 상태를 출력해준다.
printf("\n\t[DQueGetFirst()]덱의 가장 왼쪽의 데이터\n");
Element tmp;
DQueGetFirst(deque, &tmp);
printNameAge(&tmp);
printf("\n\n\t[DQueGetLast()]덱의 가장 오른쪽의 데이터\n");
DQueGetLast(deque, &tmp);
printNameAge(&tmp);DQueGetFirst 함수와 DQueGetLast 함수로 작동 여부와 데이터가 정상적으로 저장되었는지 확인한다.
printf("\n\t[DQueRemoveFirst()]배열이 빌 때까지 저장된 역순으로 출력\n\n");
while (!(DQueIsEmpty(deque))) {
DQueRemoveFirst(deque, &tmp);
printNameAge(&tmp);
}while문으로 덱의 요소가 존재하지 않을 때까지 값을 제거한다. 전달 받은 값을 출력한다.
printf("\n\t[DQueIsEmpty()]현재 덱이 비어 있는가?: %s\n", DQueIsEmpty(deque) ? "true" : "false");덱이 비어 있는지 확인하는 코드이다.
Part ① 실행 결과
========================================================
스택처럼 사용하기
--------------------------------------------------------
[DQueAddFirst()]데이터 추가
{ 24, 김철수 } 저장 완료
{ 23, 박영희 } 저장 완료
{ 21, 이진우 } 저장 완료
{ 45, 홍길동 } 저장 완료
{ 24, 김승규 } 저장 완료
{ 24, 박성겸 } 저장 완료
{ 24, 진우진 } 저장 완료
{ 24, 문도언 } 저장 완료
데이터를 저장할 수 없습니다. 공간이 부족합니다.
데이터를 저장할 수 없습니다. 공간이 부족합니다.
--------------------------------------------------------
[DQuePrint()]현재 덱 상태
Name: 문도언 Age: 24
Name: 진우진 Age: 24
Name: 박성겸 Age: 24
Name: 김승규 Age: 24
Name: 홍길동 Age: 45
Name: 이진우 Age: 21
Name: 박영희 Age: 23
Name: 김철수 Age: 24
--------------------------------------------------------
[DQueGetFirst()]덱의 가장 왼쪽의 데이터
Name: 문도언 Age: 24
[DQueGetLast()]덱의 가장 오른쪽의 데이터
Name: 김철수 Age: 24
--------------------------------------------------------
[DQueRemoveFirst()]배열이 빌 때까지 저장된 역순으로 출력
Name: 문도언 Age: 24
Name: 진우진 Age: 24
Name: 박성겸 Age: 24
Name: 김승규 Age: 24
Name: 홍길동 Age: 45
Name: 이진우 Age: 21
Name: 박영희 Age: 23
Name: 김철수 Age: 24
[DQueIsEmpty()]현재 덱이 비어 있는가?: true
--------------------------------------------------------Part ② 큐로 사용하기
소스 코드
DQueAddLast(deque, e1);
DQueAddLast(deque, e2);
DQueAddLast(deque, e3);
DQueAddLast(deque, e4);
DQueAddLast(deque, e5);
DQueAddLast(deque, e6);
DQueAddLast(deque, e7);
DQueAddLast(deque, e8);
DQueAddLast(deque, e9);
DQueAddLast(deque, e10);
printf("--------------------------------------------------------\n");
printf("\n\t[DQuePrint()]현재 덱 상태\n\n");
DQuePrint(deque, printNameAge);
printf("--------------------------------------------------------\n");
printf("\n\t[DQueGetFirst()]덱의 가장 왼쪽의 데이터\n");
DQueGetFirst(deque, &tmp);
printNameAge(&tmp);
printf("\n\n\t[DQueGetLast()]덱의 가장 오른쪽의 데이터\n");
DQueGetLast(deque, &tmp);
printNameAge(&tmp);
printf("--------------------------------------------------------\n");
printf("\n\n\t[DQueRemoveLast()덱의 오른쪽 데이터 2개 제거 후 다시 데이터 삽입\n\n");
DQueRemoveLast(deque, &tmp);
DQueRemoveLast(deque, &tmp);
DQueAddLast(deque, e9);
DQueAddLast(deque, e10);
printf("--------------------------------------------------------\n");
printf("\n\t[DQueRemoveFirst()]배열이 빌 때까지 저장된 순서대로 출력\n\n");
while (!(DQueIsEmpty(deque))) {
DQueRemoveFirst(deque, &tmp);
printNameAge(&tmp);
}
printf("\n\t[DQueIsEmpty()]현재 덱이 비어 있는가?: %s\n", DQueIsEmpty(deque) ? "true" : "false");
printf("--------------------------------------------------------\n");
printf("\n\t[DQueDestroy()]deque 메모리 반환\n\n\n");
DQueDestroy(deque);
return 0;
}Part ② 실행 결과
========================================================
큐처럼 사용하기
--------------------------------------------------------
[DQueAddLast()]데이터 추가
{ 24, 김철수 } 저장 완료
{ 23, 박영희 } 저장 완료
{ 21, 이진우 } 저장 완료
{ 45, 홍길동 } 저장 완료
{ 24, 김승규 } 저장 완료
{ 24, 박성겸 } 저장 완료
{ 24, 진우진 } 저장 완료
{ 24, 문도언 } 저장 완료
데이터를 저장할 수 없습니다. 공간이 부족합니다.
데이터를 저장할 수 없습니다. 공간이 부족합니다.
--------------------------------------------------------
[DQuePrint()]현재 덱 상태
Name: 김철수 Age: 24
Name: 박영희 Age: 23
Name: 이진우 Age: 21
Name: 홍길동 Age: 45
Name: 김승규 Age: 24
Name: 박성겸 Age: 24
Name: 진우진 Age: 24
Name: 문도언 Age: 24
--------------------------------------------------------
[DQueGetFirst()]덱의 가장 왼쪽의 데이터
Name: 김철수 Age: 24
[DQueGetLast()]덱의 가장 오른쪽의 데이터
Name: 문도언 Age: 24
--------------------------------------------------------
[DQueRemoveLast()덱의 오른쪽 데이터 2개 제거 후 다시 데이터 삽입
{ 24, 한윤학 } 저장 완료
{ 24, 이현택 } 저장 완료
--------------------------------------------------------
[DQueRemoveFirst()]배열이 빌 때까지 저장된 순서대로 출력
Name: 김철수 Age: 24
Name: 박영희 Age: 23
Name: 이진우 Age: 21
Name: 홍길동 Age: 45
Name: 김승규 Age: 24
Name: 박성겸 Age: 24
Name: 한윤학 Age: 24
Name: 이현택 Age: 24
[DQueIsEmpty()]현재 덱이 비어 있는가?: true
--------------------------------------------------------
[DQueDestroy()]deque 메모리 반환
No memory leaks detected.
Visual Leak Detector is now exiting.
C:\Users\Hotaek\Desktop\2학년 여름\DS_Review\4_Deque\Deque\Debug\Deque.exe(프로세스 27328개)이(가) 종료되었습니다(코드: 0개).
이 창을 닫으려면 아무 키나 누르세요...마치며
글을 처음 쓸 때는 이렇게까지 길어질 줄 몰랐는데... 상당히 길어졌다.
사실 자료구조 복습을 시작할 때에도 시간이 이렇게 오래 걸릴 줄 몰랐다.
하루 째에 동적 배열
이틀 째에 스택
사흘 째에 큐
나흘 째에 덱
닷새 째에 연결 리스트
이렇게 할 수 있을 줄 알았다 (...)
역시 계획대로 되는 일이 많지 않다.
