Deque = Vector + List

deque는 vector의 특성과 list의 특성이 섞여 있다.

vector의 특성:

• push_front(), pop_front(), push_back(), pop_back() 동작이 O(1) 복잡도로 동작한다
• dynamic size
• 모든 원소에 대해 임의 접근 동작이 O(1) 시간 복잡도로 동작한다

 

list 특성

• insertion
• deletion
• 덱 중간에서 원소 삽입 또는 삭제는 O(n) 시간 복잡도로 동작하며, 실제로는 최대 n/2 단계로 동작 (n은 덱의 크기)

 

vector의 메모리 형식을 따르면서 리스트처럼 삽입과 삭제가 vector보다 자유로운 deque의 특성을 자세히 알아보기 위해 deque의 wrapper을 알아보았다.

//Daque wrapper
#include <iostream>
#include <list>

template<typename T>
class DequeWrapper {
private:
    std::list<T> deque;

public:
    // Constructor
    DequeWrapper() {}

    // deque 앞 삽입
    void push_front(const T& value) {
        deque.push_front(value);
    }

    // deque 뒤 삽입
    void push_back(const T& value) {
        deque.push_back(value);
    }

    // 주어진 위치 다음에 삽입
    void insert_after(typename std::list<T>::iterator pos, const T& value) {
        deque.insert(std::next(pos), value);
    }

    // 주어진 위치 이전에 삽입
    void insert_before(typename std::list<T>::iterator pos, const T& value) {
        deque.insert(pos, value);
    }

    // 앞의 원소 제거 후 반환
    T pop_front() {
        T frontElement = deque.front();
        deque.pop_front();
        return frontElement;
    }

    // 마지막 원소 제거 후 반환
    T pop_back() {
        T backElement = deque.back();
        deque.pop_back();
        return backElement;
    }

    // 빈 deque인지 확인
    bool empty() const {
        return deque.empty();
    }

    // deque의 size 확인
    size_t size() const {
        return deque.size();
    }

    // deque 원소들 출력
    void print() const {
        for (const T& element : deque) {
            std::cout << element << " ";
        }
        std::cout << std::endl;
    }
};

 

 

int main() {
    // dequeWrapper 생성
    DequeWrapper<int> dequeWrapper;

    //deque 원소 삽입
    dequeWrapper.push_back(1);
    dequeWrapper.push_back(3);

    // deque 값 출력
    dequeWrapper.print();

    // insert_after 사용
    auto it = dequeWrapper.begin();
    dequeWrapper.insert_after(it, 2);

    // deque 값 출력
    dequeWrapper.print();

    return 0;
}

 

---

deque (Double-ended queue):

덱(deque)은 양쪽 끝에서 요소의 삽입과 삭제를 효율적으로 지원하는 순차 컨테이너입니다. 요소에 대한 임의 접근을 제공하며 양쪽 끝에서의 삽입 및 삭제는 상수 시간에 수행됩니다. 내부적으로는 주로 요소를 저장하기 위해 동적 배열이나 고정 크기 블록의 연결 리스트를 사용합니다.

//cppCopy code
#include <iostream>#include <deque>void printDeque(const std::deque<int>& dq) {
    for (auto it = dq.begin(); it != dq.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
}

int main() {
    std::deque<int> dq = {1, 2, 3};
    dq.push_front(0);
    dq.push_back(4);
    printDeque(dq);
    return 0;
}

stack:

스택(stack)은 LIFO (Last In, First Out) 데이터 구조를 제공하는 컨테이너 어댑터입니다. 가장 최근에 추가된 요소에만 접근할 수 있으며 반복자를 제공하지 않습니다. 내부적으로는 주로 덱(deque)이나 리스트(list)를 사용하여 구현됩니다. 

cppCopy code
#include <iostream>#include <stack>int main() {
    std::stack<int> stk;
    stk.push(1);
    stk.push(2);
    stk.push(3);

    while (!stk.empty()) {
        std::cout << stk.top() << " ";
        stk.pop();
    }
    std::cout << std::endl;

    return 0;
}

vector:

벡터(vector)는 동적 배열을 지원하는 순차 컨테이너입니다. 요소에 대한 임의 접근을 제공하며 컨테이너 끝에서의 효율적인 삽입 및 삭제를 지원합니다. 자동으로 크기를 조절하는 동적 배열로 주로 구현됩니다. 

cppCopy code
#include <iostream>#include <vector>void printVector(const std::vector<int>& vec) {
    for (auto it = vec.begin(); it != vec.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
}

int main() {
    std::vector<int> vec = {1, 2, 3};
    vec.push_back(4);
    printVector(vec);
    return 0;
}

list:

리스트(list)는 어느 위치에서든 요소의 효율적인 삽입 및 삭제를 지원하는 이중 연결 리스트 컨테이너입니다. 요소에 대한 임의 접근을 제공하지 않으며 첨자(subscripting)를 통한 직접적인 요소 접근을 지원하지 않습니다. 양방향 반복자를 제공합니다.

cppCopy code
#include <iostream>#include <list>void printList(const std::list<int>& lst) {
    for (auto it = lst.begin(); it != lst.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
}

int main() {
    std::list<int> lst = {1, 2, 3};
    lst.push_front(0);
    lst.push_back(4);
    printList(lst);
    return 0;
}

• 덱은 원소 삽입 시 나머지 원소를 항상 오른쪽으로 이동해야만 하는 것은 아니다. 원소 삽입 위치에서 가장 가운 끝 가까운 쪽으로 나머지 원소를 이동 하면 n/2단계의 시간 복잡도로 움직이게 된다.
• 단일 메모리 청크를 사용하지 않고 크기가 같은 여러 개의 메모리 청크를 사용하여 데이터를 저장한다. (벡터와 유사한 자료 구조)
• 메모리 재할당을 최소화하려면 첫 번째 청크부터 원소를 추가하지 않고 중간 위치의 청크부터 원소를 저장할 수 있다.