[C++][STL] 덱(Deque) 개념과 사용 방법

 

【 덱(Deque) 이란? 】

 

C++ STL에서 제공하는 덱(Deque)은 Double Ended Queue의 줄임말로, 양쪽 끝에서 삽입과 삭제가 가능한 선형 자료구조이다.

즉 큐와 스택의 기능을 모두 갖추었는데, 특히 큐와 스택이 데이터의 접근이 제한적이라는 한계점을 극복하고자 만들어진 자료구조이다.

예를 들어, 덱을 이용하면 양쪽에서 접근할 수 있는 양방향 탐색이 가능해진다.

또한 큐에서는 구현할 수 없는 중간 요소의 삽입 및 삭제도 가능하다.

 

 

 

 

【 덱(Deque)의 특징 】

 

• 임의 접근: 인덱스가 존재하기에, 벡터(vector)와 같이 인덱스를 사용하여 임의의 위치에 접근할 수 있다.
• 동적 배열: 덱은 동적 배열로, 크기를 동적으로 조절할 수 있다.
• 양방향 접근: 양쪽 끝에서 삽입 및 삭제가 가능하다.
• 메모리 관리: 메모리 할당을 세그먼트 단위로 수행한다.

 

 

 

【 덱(Deque)의 주요 멤버 함수 】

 

멤버함수
dq.assign(n)	요소 n개를 0으로 초기화
dq.assign(n,i)	요소 n개를 i로 초기화
dq.at(n)	dq의 n번째 요소 참조 반환
dq.begin()	dq의 첫 번째 요소 주소값 참조 반환
dq.front()	dq의 첫 번째 요소 참조 반환
dq.back()	dq의 마지막 요소 참조 반환
dq.end()	dq의 마지막 요소 다음을 참조 반환
dq.clear()	dq의 모든 요소 삭제
dq.empty()	dq가 비어 있는 경우 1 반환 아닐 경우 0 반환
dq.size()	dq의 원소 수를 반환
dq.insert(iterator, i)	iterator가 가리키는 위치에 요소 i 삽입 기존 원소들은 한 칸씩 밀려남
dq.erase(iterator)	iterator가 가리키는 위치의 요소 삭제
dq.resize(m)	dq의 메모리 크기를 m으로 늘리고 늘어난 부분은 0으로 초기화

 

 

【 예제 】

 

다음은 덱을 이용한 간단한 예시이다.

#include <iostream>
#include <deque>

using namespace std;

int main()
{
    deque<int> dq;

    dq.push_back(10); // 뒤에 10 삽입
    dq.push_front(20); // 앞에 20 삽입

    cout << dq.front() << '\n'; // 20 출력
    cout << dq.back() << '\n'; // 10 출력

    dq.pop_front(); // 앞에 있는 20 제거
    dq.pop_back(); // 뒤에 있는 10 제거

    dq.push_back(30);
    dq.push_back(40);

    for (int i = 0; i < dq.size(); i++) {
        cout << dq[i] << ' ';
    }
    cout << '\n'; // 30 40 출력

    return 0;
}