cpp) 백준 10866: 덱

Problem

https://www.acmicpc.net/problem/10866

10866번: 덱

정수를 저장하는 덱(Deque)를 구현한 다음, 입력으로 주어지는 명령을 처리하시오.
 
 

Solution

- STL로 풀기
 

#include<iostream>
#include<deque>

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int t;     // 명령 수
    string s;  // 명령어
    int n;     // 입력 숫자
    deque<int> dq;

    cin >> t;

    for(int i=0;i<t;i++){
        cin >> s;

        if (s=="push_front"){
            cin >> n;
            dq.push_front(n);
        }

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

        else if (s=="empty"){
            cout << dq.empty() << '\n';
        }

        else if (s=="front"){
            if (dq.empty())
                cout << -1 << '\n';
            else
                cout << dq.front() << '\n';
        }

        else if (s=="back"){
            if (dq.empty())
                cout << -1 << '\n';
            else
                cout << dq.back() << '\n';
        }
    }
   return 0;
}

 
 
- 배열로 풀기
 

#include <iostream>
#include <string>
 
using namespace std;
 
const int MX = 1000000;
int deque_arr[2 * MX + 1];
int head = MX, tail = MX;
 
int empty(int data[]) {
    if (head == tail) return 1; // 덱이 비어 있는 경우
    else return 0; // 덱이 비어 있지 않은 경우
}
 
void push_front(int deque_arr[], int data) {
    deque_arr[--head] = data;
}
 
void push_back(int deque_arr[], int data) {
    deque_arr[tail++] = data;
}
 
int pop_front(int deque_arr[]) {
    if (empty(deque_arr)) return -1;
    return deque_arr[head++];
}
 
int pop_back(int deque_arr[]) {
    if (empty(deque_arr)) return -1;
    return deque_arr[--tail];
}
 
int size(int deque_arr[]) {
    return tail - head;
}
 
int front(int deque_arr[]) {
    if (empty(deque_arr)) return - 1;
    return deque_arr[head];
}
 
int back(int deque_arr[]) {
    if (empty(deque_arr)) return -1;
    return deque_arr[tail - 1];
}
 
int main() {
    int n;
    cin >> n;
    
    string command;
    int command_num;
 
    for (int i = 0; i < n; i++) {
        cin >> command;
 
        if (command == "push_front") {
            cin >> command_num;
            push_front(deque_arr, command_num);
        }
        else if (command == "push_back") {
            cin >> command_num;
            push_back(deque_arr, command_num);
        }
        else if (command == "pop_front") {
            cout << pop_front(deque_arr) << endl;
        }
        else if (command == "pop_back") {
            cout << pop_back(deque_arr) << endl;
        }
        else if (command == "size") {
            cout << size(deque_arr) << endl;
        }
        else if (command == "empty") {
            cout << empty(deque_arr) << endl;
        }
        else if (command == "front") {
            cout << front(deque_arr) << endl;
        }
        else if (command == "back") {
            cout << back(deque_arr) << endl;
        }
    }
    
    return 0;
}

 
 

Reference

https://blockdmask.tistory.com/73

[C++] deque container 정리 및 사용법

https://velog.io/@soyeon207/%EB%B0%B1%EC%A4%80C-10866%EB%B2%88-%EB%8D%B1

[백준/c++] 10866번 덱