Baekjoon 10866 덱(Deque)

자료구조 세번째, 덱 !

[문제]

[풀이]

덱(Deque)은 큐(Queue)와 유사한 성격을 가지고 있기때문에, Queue를 베이스로 코드를 구현할 수 있다.

Queue와의 다른 점은,
1. FIFO인 Queue와는 달리, front와 back 모든 곳에서 push, pop이 가능하다.
2. front와 back 모두 고려해야한다.

덱은 Circular Queue의 형태로 디자인하면 쉽게 구현할 수 있다.
front는 실제 저장정보의 시작점 하나 앞이며, rear은 말 그대로 저장된 정보의 마지막 위치이다.
앞선 queue의 구현에서는 front와 rear가 같으면 empty를 의미했다.
하지만 여기서는 조금 다르다.

front와 rear일 때, 두가지 경우를 생각할 수 있다.
1. empty
2. full

하지만 위의 문제에서는 고려할 필요가 없다.
이미 충분한 입력가능수만큼 배열을 만들어주었기 때문이다. (10,000)

이 문제를 풀며 실제로 고려해야할 점은,
1. front와 rear의 이동
2. circular의 형태로 구현
3. front가 0일때의 push, pop / rear가 배열의 마지막 위치일때의 push, pop
=>이는 mod(%)를 이용해 해결할 수 있다.

[최종코드]

#include <iostream>
using namespace std;

class Deque {
public:
    int deque[10000]={0};
    int size;
    int f;
    int rear;

    Deque(){ // constructor
        size=0;
        f=0;
        rear=0;
    }
    
    
    int empty() {
        if(f==rear){
            return 1;
        }
        else return 0;
    }


    void push_front(int data) {
        size+=1;
        if(f==0){
            f=(10000-1);
            deque[(f+1)%10000]=data;
            return;
        }
        else{
            f=f-1;
            deque[(f+1)%10000]=data;
            return;
        }
    }

    void push_back(int data){
        size+=1;
        if(rear==9999){
            rear=(9999+1)%10000;
            deque[rear]=data;
            return;
        }
        else{
            rear=rear+1;
            deque[rear]=data;
            return;
        }
    }

    int pop_front(void){

        if(empty()){
            return -1;
        }
        else{
            size-=1;
            
            if(f==9999){
                f=(9999+1)%10000;
                return deque[f];
            }
            else{
                f=f+1;
                return deque[f];
            }
        }
    }

    int pop_back(void){
        if(empty()){
            return -1;
        }
        else{
            size-=1;

            if(rear==0){
                rear=9999;
                return deque[(9999+1)%10000];
            }
            else{
                rear=rear-1;
                return deque[rear+1];
            }
        }
    }

    int front(void){
        if(empty()){
            return -1;
        }
        else{
            if(f==9999) return deque[0];
            else return deque[f+1];
        }
    }

    int back(void){
        if(empty()){
            return -1;
        }
        else{
            return deque[rear];
        }
    }


    
}; //class의 끝에 semi colon 필수 !!


int main (void){
    int N; //test case
    cin>>N;
    Deque d;
    for(int i=0; i<N; i++){
        string msg;
        cin>>msg;
        if(msg=="push_back"){
            int num;
            cin>>num;
            d.push_back(num);
        }

        else if(msg=="push_front"){
            int num;
            cin>>num;
            d.push_front(num);
        }
        
        else if(msg=="pop_front"){
            cout<<d.pop_front()<<endl;
        }

        else if(msg=="pop_back"){
            cout<<d.pop_back()<<endl;
        }

        else if(msg=="size"){
            cout<<d.size<<endl;
        }

        else if(msg=="front"){
            cout<<d.front()<<endl;
        }

        else if(msg=="back"){
            cout<<d.back()<<endl;
        }
        else if(msg=="empty"){
            cout<<d.empty()<<endl;
        }
    }

    return 0;
    
      return 0;
}

[돌아보며]

circular의 형태로 구조화한 부분이 신선했다.
앞으로는 늘릴 수 없는 배열의 한계를 극복할 수 있는 적절한 방법으로 보인다.