[BOJ알고리즘, C++]#10866_덱, 선형 자료구조

 

[BOJ알고리즘, C++]#10866_덱

 

BOJ 알고리즘 문제 풀이, 10866 문제 덱

deque 컨테이너를 활용하는 방법에 대해 알아보겠습니다.

 

---

 

Overview

 

1. 문제
2. 풀이
3. 코드

 

#0. 문제

 

 

#1. 풀이

1. 양방향 큐

• 양방향 큐는 데이터 목록의 양쪽 끝에서 데이터의 삽입과 삭제가 모두 가능한 큐 자료구조의 한 종류입니다.
• 양방향 큐는 양쪽 끝에서 데이터의 삽입과 삭제가 모두 가능해 크기가 유연하며, 슬라이딩 윈도우 알고리즘 혹은 양쪽에서 접근해야 하는 큐 기반의 문제 등에 활용됩니다. 

 

2. deque 컨테이너

[Basic C++] #68_deque

 

#2. 코드

1. 코드

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

int N;
deque<int> dq;

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    cin >> N;

    while(N--)
    {
        string str;
        int num;

        cin >> str;

        if(str == "push_front")
        {
            cin >> num;
            dq.push_front(num);
        }
        else if(str == "push_back")
        {
            cin >> num;
            dq.push_back(num);
        }
        else if(str == "pop_front")
        {
            if(!dq.empty())
            {
                cout << dq.front() << '\n';
                dq.pop_front();
            }
            else
            {
                cout << -1 << '\n';
            }
        }
        else if(str == "pop_back")
        {
            if(!dq.empty())
            {
                cout << dq.back() << '\n';
                dq.pop_back();
            }
            else
            {
                cout << -1 << '\n';
            }
        }
        else if(str == "size")
        {
            cout << dq.size() << '\n';
        }
        else if(str == "empty")
        {
            if(dq.empty())
                cout << 1 << '\n';
            else
                cout << 0 << '\n';
        }
        else if(str == "front")
        {
            if(!dq.empty())
                cout << dq.front() << '\n';
            else
                cout << -1 << '\n';
        }
        else if(str == "back")
        {
            if(!dq.empty())
                cout << dq.back() << '\n';
            else
                cout << -1 << '\n';
        }
    }

}