[백준/C++] 10866번 덱

10866번 문제 링크

문제

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

명령은 총 여덟 가지이다.

• push_front X: 정수 X를 덱의 앞에 넣는다.
• push_back X: 정수 X를 덱의 뒤에 넣는다.
• pop_front: 덱의 가장 앞에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• pop_back: 덱의 가장 뒤에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 덱에 들어있는 정수의 개수를 출력한다.
• empty: 덱이 비어있으면 1을, 아니면 0을 출력한다.
• front: 덱의 가장 앞에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• back: 덱의 가장 뒤에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

풀이

덱(데큐) 는 양쪽 끝에서 삽입과 삭제가 모두 가능한 큐 로, 양쪽에서 삽입과 삭제를 모두 처리할 수 있으며, 스택과 큐의 특징을 모두 가지고 있다.

C++ 에서는 STL 로 deque 기능을 제공하고 있으며, 배열로도 구현할 수 있다.

소스코드

① STL 로 풀기

#include <iostream>
#include <deque>

using namespace std;

int deque_stl() {

    deque<int> deque_int;

    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;
            deque_int.push_front(command_num);
        } else if (command == "push_back") {
            cin >> command_num;
            deque_int.push_back(command_num);
        } else if (command == "size") {
            cout << deque_int.size() << endl;
        } else if (command == "empty") {
            cout << deque_int.empty() << endl;
        } else if (deque_int.empty()) {
            cout << -1 << endl;
        } else if (command == "pop_front") {
            cout << deque_int.front() << endl;
            deque_int.pop_front();
        } else if (command == "pop_back") {
            cout << deque_int.back() << endl;
            deque_int.pop_back();
        } else if (command == "front") {
            cout << deque_int.front() << endl;
        } else if (command == "back") {
            cout << deque_int.back() << endl;
        }
    }
    
    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 dat[]) {
    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;
}

정답