[C++] 덱 ( deque ) 사용법

STL deque

deque는 양방향 큐( double-ended queue )의 기능을 제공하는 선형 컨테이너입니다.

일반적인 queue는 뒤 쪽에 데이터를 입력하고, 앞에서 데이터를 삭제하는 FIFO ( first in, first out ) 구조를 가진 반면,

deque는 뒤쪽과 앞쪽 모든 곳에서 데이터를 입력하고, 삭제가 가능한 컨테이너입니다.

 

 

deque의 구조

 

이 deque를 사용하려면 다음의 헤더를 포함해야 합니다.

#include <deque>

 

deque의 선언

deque의 선언은 다음과 같습니다.

std::deque<T> deque_name;

여기서 T는 deque의 데이터 타입을 나타냅니다.

그리고, namespace를 선언함으로써, std를 매번 명시해야 하는 번거로움을 덜 수도 있습니다.

using namespace std;

deque<int> int_deq;	// int 타입의 덱 선언

 

deque의 초기화

deque를 초기화하는 방법은 여러 가지가 있습니다.

1. 초기화 리스트를 사용하는 방법입니다.

#include <iostream>
#include <deque>
using namespace std;

int main(){

    deque<int> int_deq = { 1, 2, 3, 4, 5 };

    for( int data : int_deq ){
        cout << data << " ";
    }

    return 0;
}

 

2. 유니폼 초기화( uniform initialization )를 사용하는 방법입니다.

deque<int> int_deq { 1, 2, 3, 4, 5 };	// uniform 초기화

 

3. 직접 크기와 값을 설정할 수도 있습니다.

deque<int> int_deq (5, 10);	// 5개의 원소를 값 10으로 초기화합니다.

deque<int> int_deq = { 10, 10, 10, 10, 10 };	// 위의 줄과 동일합니다.

 

4. 다른 deque를 복사하여 초기화할 수도 있습니다.

deque<int> int_deq = { 1, 2, 3, 4, 5 };

deque<int> copy_deq(int_deq);

 

deque의 반복자 ( Iterator )

deque 반복자는 deque 내의 원소들에 접근하고, 원소들 간의 이동을 위해서 사용됩니다.
deque의 반복자는 임의 접근 반복자( random access iterator )입니다.

반복자( iterator )의 전반적인 내용은 여기에 정리해 두었습니다.

[C++] 반복자( Iterator )에 대한 설명과 종류

 

deque 반복자는 다음과 같이 선언합니다.

deque<T>::iterator iter_name;

여기서, T는 deque의 데이터 타입을 나타냅니다.

 

deque의 반복자 초기화

deque의 초기화는 다음의 함수들로 수행할 수 있습니다.

begin

이 함수는 deque의 첫 번째 원소를 가리키는 iterator를 반환합니다.

deque<int> int_deq = { 1, 2, 3, 4, 5 };
deque<int>::iterator iter;   // int타입 deque의 반복자 선언

iter = int_deq.begin();

end

이 함수는 deque의 마지막 원소 다음을 가리키는 iterator를 반환합니다.
마지막 원소를 가리키는 iterator는 다음과 같이 구할 수 있습니다.

deque<int> int_deq = { 1, 2, 3, 4, 5 };
deque<int>::iterator iter;   // int타입 deque의 반복자 선언

iter = int_deq.end();
iter--;

int val = *iter; // 마지막 원소 5

 

만일, deque의 원소가 하나도 없다면 begin과 end가 같은 값을 반환합니다.

int main(){

    deque<int> int_deque;
    if ( int_deque.begin() == int_deque.end()){
        cout << "deque size is zero\n";
    }

    return 0;
}

▼출력

deque size is zero

 

deque의 모든 원소를 순환하고자 하면 다음과 같이 할 수 있습니다.

int main(){

    deque<int> int_deque = { 1, 2, 3, 4, 5 };
    deque<int>::iterator iter;

    for(iter = int_deque.begin(); iter != int_deque.end(); iter++){
        cout << *iter << " ";
    }

    return 0;
}

▼출력

1 2 3 4 5

 

deque의 기능들

deque는 매우 많은 기능을 가진 객체입니다.
이 중에서, 공통적으로 많이 쓰이는 기능을 정리해서 설명하겠습니다.

 

• 원소의 개수 알아내기
• 원소에 접근하기
• 원소 추가하기
• 원소 삭제하기

 

원소의 개수 알아내기

size

deque가 저장하고 있는 원소의 개수를 반환합니다.

empty

deque가 가지고 있는 원소의 개수가 0이면 true, 아니면 false를 반환합니다.

int main(){

    deque<int> int_deque = { 1, 2, 3, 4, 5 };
    
    cout << int_deque.size() << endl;

    cout << "is empty: " << int_deque.empty();

    return 0;
}

▼출력

5
is empty: 0

 

원소에 접근하기

front

reference front();
const_reference front() const;

deque의 첫 번째 원소를 반환합니다.
만약, deque가 원소를 갖고 있지 않은 경우, 위 함수는 정의되지 않으므로, 사용 시 주의해야 합니다.

back

reference back();
const_reference back() const;

deque의 마지막 원소를 반환합니다.
만약, deque가 원소를 갖고 있지 않은 경우, 위 함수는 정의되지 않으므로, 사용 시 주의해야 합니다.

at

reference at(size_type pos);
const_reference at(size_type pos) const;

at 함수는 vector의 원소를 index를 사용해 접근할 수 있도록 합니다.

at 함수 대신 연산자 [ ]를 통해서 원소에 접근하는 방법도 있습니다.
그러나, index가 잘못되는 경우 연산자 [ ]는 잘못된 값을 반환하지만, at 함수는 예외(exception)를 발생시킵니다.

 

int main(){

    deque<int> int_deque = { 1, 2, 3, 4, 5 };
    
    cout << "front: " << int_deque.front() << endl;

    cout << "back: " << int_deque.back() << endl;

    cout << "element at 2: " << int_deque.at(2) << endl;   // use index

    cout << "element [3]: " << int_deque[3] << endl;    // use operator

    return 0;
}

▼출력

front: 1
back: 5
element at 2: 3
element [3]: 4

 

원소 추가하기

push_front

새로운 원소를 deque의 처음에 추가합니다.

push_back

새로운 원소를 deque의 마지막에 추가합니다.

int main(){

    deque<int> int_deque = { 1, 2, 3, 4, 5 };
    
    int_deque.push_front(0);
    int_deque.push_back(6);
    
    for( int data : int_deque ){
        cout << data << " ";
    }
    
    return 0;
}

▼출력

0 1 2 3 4 5 6

 

원소 삭제하기

pop_front

deque의 첫 번째 원소를 삭제합니다.

deque에 데이터가 없는 경우, 예외( exception )가 발생합니다.

back_back

deque의 마지막 원소를 삭제합니다.
deque에 데이터가 없는 경우, 예외( exception )가 발생합니다.

int main(){

    deque<int> int_deque = { 1, 2, 3, 4, 5 };

    int_deque.pop_front();
    int_deque.pop_back();

    for( int data : int_deque){
        cout << data << " ";
    }

    return 0;
}

▼출력

2 3 4

clear

deque의 모든 원소를 삭제합니다.

int main(){

    deque<int> int_deque = { 1, 2, 3, 4, 5 };

    int_deque.clear();

    int size = int_deque.size(); // 0

    return 0;
}