2024 모각코 5회차

일정

2024.01.16

목표

백준 10866 덱구현 c++fh wkrtjd

[BOJ] 10866번 덱(deque) C++ 구현

문제

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

풀이

STL을 사용하는 것보다 덱을 직접 구현하는 게 문제에서 원하는 것 같아서 직접 구현해 봤습니다.

직접 구현하면서 pop_front(), pop_back() 부분에서 NULL포인터에 접근하지 않게 주의하며 구현했습니다.

소스코드

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

class Node{
    public:
        int data;
        Node *next;
        Node *prev;

    Node(int input){
        data = input;
        next = NULL;
        prev = NULL;
    }
};

class Deque{
    public:
        int size;
        Node *head;
        Node *tail;

        Deque(){
            size = 0;
            head = NULL;
            tail = NULL;
        }

        void push_front(int input){
            Node *node = new Node(input);
            if(head==NULL){
                tail = node;
            }else{
                head -> prev = node;
                node -> next = head;
            }
            head = node;
            size++;
        }

        void push_back(int input){
            Node *node = new Node(input);
            if(head==NULL){
                head = node;
            }else{
                node->prev = tail;
                tail->next = node;
            }
            tail = node;
            size++;
        }

        int pop_front(){
            if(head==NULL) return -1;
            
            int value = head->data;
            Node *node = head->next;
            delete head;
            head = node;
            if(head==NULL){
                tail=NULL;
            }else head->prev = NULL;
            size--;
            return value;
        }

        int pop_back(){
            if(tail==NULL) return -1;

            int value = tail -> data;
            Node *node = tail->prev;
            delete tail;
            tail = node;
            if(tail==NULL){
                head=NULL;
            }else tail->next=NULL;
            size--;
            return value;
        }

        int empty(){
            if(head==NULL) return 1;
            else return 0;
        }

        int front(){
            if(head==NULL) return -1;
            return head->data;
        }

        int back(){
            if(head==NULL) return -1;
            return tail->data;
        }
};


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n;
    string s;

    Deque dq;
    
    cin >> n;

    for(int i=0;i<n;i++){
        cin >> s;
        if(s=="push_front"){
            int element;
            cin >> element;
            dq.push_front(element);
        }else if(s=="push_back"){
            int element;
            cin >> element;
            dq.push_back(element);
        }else if(s=="pop_front"){
            cout << dq.pop_front() << "\n";
        }else if(s=="pop_back"){
            cout << dq.pop_back() << "\n";
        }else if(s=="size"){
            cout << dq.size << "\n";
        }else if(s=="empty"){
            cout << dq.empty() << "\n";
        }else if(s=="front"){
            cout << dq.front() << "\n";
        }else if(s=="back"){
            cout << dq.back() << "\n";
        }
    }
}