[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. 사용 용도에 따른 효율성 : 덱은 스택 또는 큐처럼 사용될 때 각각의 용도에 비해 효율성이 떨어질 수 있다.

덱이 특정 용도에 특화된 자료구조보다는 다목적으로 사용되는 특성이 있어서 그렇다.