5. 덱 (Deque)

위의 STL 자료는 유명한 자료구조이므로 잘 학습해 두어야 한다.

Deque

이 알고리즘을 활용하기 위해서는 상단에 반드시 #include <deqye>을 선언해야 한다.
이 자료구조의 특징은 stack의 특징과 queue의 특징을 섞었다는 것이다. 즉,  LIFO(Last In First Out)이다. 즉, 나중에 들어온 것이 먼저 나가는 자료구조이다.

Deque는 기본적으로 vector container와 매우 유사하나, vector보다는 앞과 뒤의 원소로 삽입이나 삭제가 빈번한 경우에 사용하는 것이 일반적이다. vector의 경우에는 뒤의 자료만 추가하고 삭제가 가능하다. 선언 방법은 "deque<자료형> 변수이름"이다. 만약 선언하면서 초기화를 시키고 싶은 경우에는 

사용방법은 다음과 같다.
dq.push_front(value) : 덱의 앞 부분에 원소를 추가
dq.push_back(value) : 덱의 뒷 부분에 원소를 추가
dq.pop_front() : 덱의 첫번째 원소를 제거
dq.pop_back() : 덱의 마지막 원소를 제거
dq.front() : 덱의 첫번째 원소를 return한다.
dq.back() : 덱의 마지막 원소를 return한다. (단, queue에서는 마지막 원소를 return하는 것이 q.end()였다는 측면에서 차이가 있다.)
dq.size() : 덱안에 있는 원소의 개수를 반환
dq.empty() : 덱이 비어있으면 true, 아니면 false를 반환한다.

덱에 해당하는 쉬운 문제를 간단하게 살펴보면 다음과 같다.

 

#include <iostream>
#include <deque>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

int main(void){
    int n;
    cin >> n;
    deque<int> data_store;
    
    for(int i = 0; i < n; i++){
        string checker;
        cin >> checker;

        if(checker == "push_front"){
            int temp;
            cin >> temp;
            data_store.push_front(temp);


        }
        else if(checker == "push_back"){
            int temp;
            cin >> temp;
            data_store.push_back(temp);

        }
        else if(checker == "pop_front"){
            if(data_store.empty() == 1){
                cout << "-1\n";
            }
            else{
                cout << data_store.front() << "\n";
                data_store.pop_front();
            }
        }
        else if(checker == "pop_back"){
            if(data_store.empty() == 1){
                cout << "-1\n";
            }
            else{
                cout << data_store.back() << "\n";
                data_store.pop_back();
            }

        }
        else if(checker == "size"){
            cout << data_store.size() << "\n";

        }
        else if(checker == "empty"){
            cout << data_store.empty() << "\n";

        }
        else if(checker == "front"){
            if(data_store.empty() == 1){
                cout << "-1\n";
            }
            else{
                cout << data_store.front() << "\n";
            }
        }
        else if(checker == "back"){
            if(data_store.empty() == 1){
                cout << "-1\n";
            }
            else{
                cout << data_store.back() << "\n";
            }
        }
    }

    return 0;

}