Nagie's DevStory
[DATA STRUCTURE] 08. 덱(Deque) 본문
아래의 코드는 C++로 구현된 덱(Deque)이다.
std::deque가 동작하는 결과를 보고 std::vector를 사용해 흉내만 내봤다.
#pragma once
#include <vector>
template <typename T>
class MyDeque {
private:
std::vector<T> data;
public:
void pushFront(const T& item) {
data.insert(data.begin(), item);
}
void pushBack(const T& item) {
data.push_back(item);
}
void popFront() {
if (!isEmpty()) {
data.erase(data.begin());
}
}
void popBack() {
if (!isEmpty()) {
data.pop_back();
}
}
const T& front() const {
if (!isEmpty()) {
return data.front();
}
}
const T& back() const {
if (!isEmpty()) {
return data.back();
}
}
bool isEmpty() const {
return data.empty();
}
int size() const {
return data.size();
}
};
주요 특징
1. 이중 끝 큐(Double-Ended Queue) : 덱은 양쪽 끝에서 삽입과 삭제 연산을 지원하는 자료 구조다.
2. 빠른 삽입과 삭제 : 덱은 양쪽 끝에서의 삽입과 삭제 연산이 모두 O(1)의 시간 복잡도를 갖는다.
3. 양방향 접근 : 덱은 양쪽 끝에서의 삽입, 삭제, 검색 등 모든 작업에 대한 빠른 양방향 접근을 제공한다.
4. 다양한 용도 : 덱은 큐와 스택의 모든 기능을 수행할 수 있기 때문에 다양한 응용 분야에서 활용할 수 있다.
5. 큐와 스택 구현 : 덱은 큐와 스택을 구현하는 데 사용할 수 있다.
6. 언어 차원에서의 지원 : 덱은 많은 프로그래밍 언어에서 표준 라이브러리나 서드파티 라이브러리로 제공된다.
(예를 들면 C++의 STL에서는 std::deque 클래스를 제공한다.)
장점
1. 양방향 데이터 접근 : 덱은 양쪽 끝에서 데이터를 추가하거나 제거할 수 있어,
데이터를 양방향으로 효과적으로 처리할 수 있다.
2. 다양한 용도 : 덱은 스택과 큐의 기능을 모두 제공하기 때문에 다양한 용도로 활용할 수 있다.
LIFO(Last-In-First-Out) 동작이 필요한 경우나 FIFO(First-In-First-Out) 동작이 필요한 경우 사용할 수 있다.
3. 중간 요소 삽입 : 덱은 양쪽에서 데이터를 추가하거나 제거할 수 있으므로
중간에 요소를 삽입하거나 제거하기에도 효과적이다.
4. 데이터 회전 : 덱을 사용해 데이터를 회전시킬 수 있으며, 환형 큐와 유사한 용도로 사용될 수 있다.
단점
1. 구현 복잡성 : 덱은 스택과 큐의 두 가지 동작을 모두 제공해야 하므로 구현이 복잡할 수 있다.
2. 메모리 사용 : 덱은 동적 배열을 사용하는 경우 메모리 할당과 해제가 복잡할 수 있으며,
또한 양쪽 끝에서 데이터를 추가하거나 제거하는 작업은 중간 요소에 비해 오버헤드가 있을 수 있다.
3. 사용 용도에 따른 효율성 : 덱은 스택 또는 큐처럼 사용될 때 각각의 용도에 비해 효율성이 떨어질 수 있다.
덱이 특정 용도에 특화된 자료구조보다는 다목적으로 사용되는 특성이 있어서 그렇다.