[C++, 자료구조] 덱(Deque)

■ 덱(Deque)

스택은 같은 한쪽(Top)에서 데이터를 넣고 빼는 구조였고, 큐는 뒤에서 데이터를 넣고 앞에서 데이터를 꺼내는 자료구조였다.

[Deque]

덱은 앞으로도 뒤로도 넣을 수 있고, 앞으로도 뒤로도 뺄 수 있는, 스택과 큐의 특성을 모두 갖추고 있는 자료구조이다.

• Deque는 ‘디큐’로 읽기 쉬운데, 이러면 큐의 Dequeue연산과 발음이 같아져 “덱”으로 발음한다
  • Double-Ended Queue의 줄임말이다.

▶ 덱의 추상 자료형

덱의 특성을 살펴봤으니, 이번엔 덱의 추상 자료형에 대해 살펴보자.

정의	설명
void InitDeque(Deque* dq)	덱의 초기화를 진행한다. 덱 생성 후 가장 먼저 호출한다.
bool IsEmpty(Deque* dq)	덱이 빈 경우 ture, 그렇지 않은 경우는 false를 반환한다.
void PushFront(Deque* dq, Data data)	덱의 머리에 데이터를 저장한다.
void PushBack(Deque* dq, Data data)	덱의 꼬리에 데이터를 저장한다.
Data PopFront(Deque* dq)	덱의 머리에 위치한 데이터를 반환 및 소멸한다.
Data PopBack(Deque* dq)	덱의 꼬리에 위치한 데이터를 반환 및 소멸한다.
Data GetFirst(Deque* dq)	덱의 머리에 위치한 데이터를 소멸하지 않고 반환한다.
Data GetLast(Deque* dq)	덱의 꼬리에 위치한 데이터를 소멸하지 않고 반환한다.

 

덱도 마찬가지로 배열, 혹은 리스트를 기반으로 작성할 수 있지만 데이터의 삽입 특징에 따라 가장 어울리는 “양방향 연결 리스트”를 사용하여 구현할 것이다.

 

■ 덱의 구현

1. Deque.h

#pragma once
typedef int Data;

struct DequeNode
{
	DequeNode* prev = nullptr;
	DequeNode* next = nullptr;
	Data data;
}; typedef DequeNode Node;

struct Deque
{
	Node* head = nullptr;
	Node* tail = nullptr;
};

void InitDeque(Deque* dq);

void push_front(Deque* dq, Data value);
void push_back(Deque* dq, Data value);
Data pop_front(Deque* dq);
Data pop_back(Deque* dq);

Data get_front(Deque* dq);
Data get_back(Deque* dq);

bool IsEmpty(Deque* dq);

 

앞서 정리한 추상 자료형을 기반으로 헤더 파일을 작성하였다.

[꼬리가 있는 양방향 연결 리스트]

머리를 가리키는 Head 포인터를 덱의 앞으로, 꼬리를 가리키는 Tail 포인터를 덱의 끝으로 설정하여 데이터를 추가하거나 반환한다.

• 기존 양방향 리스트와 크게 차이는 없지만, 추상 자료형이 다르기 때문에 코드까지 완전히 동일하진 않다.

 

2. Deque.cpp

1. InitDeque() / IsEmpty()

void InitDeque(Deque* dq)
{
	if(dq->head != nullptr)
	{
		while (IsEmpty(dq) == false)
		{
			pop_front(dq);
		}
	}

	dq->head = nullptr;
	dq->tail = nullptr;
}

bool IsEmpty(Deque* dq)
{
	return dq->head == nullptr;   // 헤드 노드가 nullptr이라면, 덱은 비어있다.
}

 

덱을 초기화하고 나서 가장 먼저 호출하는 함수이다.

• 이전과 동일하게 덱에 데이터가 있는 상태에서 head와 tail을 nullptr로 만들어버리면, 기존 데이터에는 접근이 불가능하니 pop_front() 함수를 사용하여 할당된 메모리를 해제한다.

 

2. push_front()

void push_front(Deque* dq, Data value)
{
	auto newNode = new Node;

	newNode->data = value;
	newNode->next = dq->head;

	if(IsEmpty(dq))
	{
		dq->tail = newNode;
	}
	else
	{
		dq->head->prev = newNode;
	}

	dq->head = newNode;
}

 

노드를 생성하고, 인자로 전달된 데이터를 초기화한다. 새롭게 생성된 노드의 next 포인터는 기존 head가 가리키는 노드를 가리키도록 만든다.

[데이터가 추가되는 경우]

• 처음으로 데이터가 추가되는 경우라면(dq→head == null), tail도 newNode를 가리켜야 한다.
• 기존 데이터가 존재하는 경우라면, head가 가리키는 노드의 prev 포인터를 newNode를 가리키게 한 뒤, head노드를 옮긴다.

 

3. push_back()

void push_back(Deque* dq, Data value)
{
	auto newNode = new Node;

	newNode->data = value;
	newNode->prev = dq->tail;

	if(IsEmpty(dq))
	{
		dq->head = newNode;
	}
	else
	{
		dq->tail->next = newNode;
	}

	dq->tail = newNode;
}

 

push_front()와 동일한 원리로 노드를 추가한다. 데이터가 끝(tail)에 추가된다는 점만 조심해 주면 된다.

 

4. pop_front()

Data pop_front(Deque* dq)
{
	if(IsEmpty(dq))
	{
		cout << "Deque is empty!" << endl;
		return -1;
	}

	auto delNode = dq->head;
	auto retData = delNode->data;

	dq->head = delNode->next;
	delete delNode;

	if(dq->head == nullptr)
	{
		dq->tail = nullptr;
	}
	else
	{
		dq->head->prev = nullptr;
	}

	return retData; 
}

 

head가 가리키는 노드의 포인터 정보와 데이터 정보를 저장하고, Head의 위치를 삭제될 노드의 다음 위치로 옮긴다.

[데이터를 반환하는 경우]

데이터를 추가할 때와 마찬가지로, 반환하고 소멸시킬 때도 확인해야 할 경우가 있다.

• dq->head == nullptr : 더이상 남아있는 데이터가 없으므로, tail 역시 nullptr로 변경한다.
• dq->head != nullptr : 옮겨진 head가 가리키는 prev가 소멸되었으니, nullptr로 변경한다.

 

5. pop_back()

Data pop_back(Deque* dq)
{
	if(IsEmpty(dq))
	{
		cout << "Deque is empty!" << endl;
		return -1;
	}

	auto delNode = dq->tail;
	auto retData = delNode->data;

	dq->tail = delNode->prev;
	delete delNode;

	if(dq->tail == nullptr)
	{
		dq->head = nullptr;
	}
	else
	{
		dq->tail->next = nullptr;
	}

	return retData;
}

pop_back() 함수 역시 pop_front()와 같은 구조이므로 따로 설명은 하지 않고 넘어가겠다.

 

▼ 전체 코드

#include "Deque.h"
#include <iostream>
using namespace std;

void InitDeque(Deque* dq)
{
	if(dq->head != nullptr)
	{
		while (IsEmpty(dq) == false)
		{
			pop_front(dq);
		}
	}

	dq->head = nullptr;
	dq->tail = nullptr;
}

void push_front(Deque* dq, Data value)
{
	auto newNode = new Node;

	newNode->data = value;
	newNode->next = dq->head;

	if(IsEmpty(dq))
	{
		dq->tail = newNode;
	}
	else
	{
		dq->head->prev = newNode;
	}

	dq->head = newNode;
}

void push_back(Deque* dq, Data value)
{
	auto newNode = new Node;

	newNode->data = value;
	newNode->prev = dq->tail;

	if(IsEmpty(dq))
	{
		dq->head = newNode;
	}
	else
	{
		dq->tail->next = newNode;
	}

	dq->tail = newNode;
}

Data pop_front(Deque* dq)
{
	if(IsEmpty(dq))
	{
		cout << "Deque is empty!" << endl;
		return -1;
	}

	auto delNode = dq->head;
	auto retData = delNode->data;

	dq->head = delNode->next;
	delete delNode;

	if(dq->head == nullptr)
	{
		dq->tail = nullptr;
	}
	else
	{
		dq->head->prev = nullptr;
	}

	return retData; 
}

Data pop_back(Deque* dq)
{
	if(IsEmpty(dq))
	{
		cout << "Deque is empty!" << endl;
		return -1;
	}

	auto delNode = dq->tail;
	auto retData = delNode->data;

	dq->tail = delNode->prev;
	delete delNode;

	if(dq->tail == nullptr)
	{
		dq->head = nullptr;
	}
	else
	{
		dq->tail->next = nullptr;
	}

	return retData;
}

Data get_front(Deque* dq)
{
	if(IsEmpty(dq))
	{
		cout << "Deque is empty!" << endl;
		return -1;
	}

	return dq->head->data;
}

Data get_back(Deque* dq)
{
	if (IsEmpty(dq))
	{
		cout << "Deque is empty!" << endl;
		return -1;
	}

	return dq->tail->data;
}

bool IsEmpty(Deque* dq)
{
	return dq->head == nullptr;
}

#include<iostream>
#include "Deque.h"
using namespace std;

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

	for(int i = 0; i <= 50; i++)
	{
		if(i % 2 == 0)
		{
			push_front(&dq, i);
		}
		else
		{
			push_back(&dq, i);
		}
	}

	PrintAllDataFromFront(&dq);

	for(int i = 0; i <= 25; i++)
	{
		cout << "Pop Front: " << pop_front(&dq) << endl;
		cout << "Pop Back: " << pop_back(&dq) << endl << endl;
	}

	return 0;
}

[Main.cpp]

0~50까지의 수 중 짝수는 덱의 앞에, 홀수는 뒤의 덱에 추가한 뒤 앞 뒤에서 하나씩 pop 하면 성공적으로 덱을 구현한 것을 확인할 수 있다.