[BaekJoon/백준] 10866번 덱 구현

구현.. 오래걸렸다..

 

예전에 양방향 큐(=덱)을 구현한 적이 있는데, 해당 코드에서 PeekRear 함수 구현부분이 틀려서, 다시 수정해서 업데이트했다.

 

덱이란 양방향 큐이다. 시작(front)와 끝 지점(rear)에서 양쪽으로 데이터를 인큐하거나 디큐하는 자료구조다.

 

그리고 이전 큐 구현 예제들과 동일한 링버퍼 구조 기반으로 구현했다. (구조체의 종류, 역할, 세팅값도 동일)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int max;
    int num;
    int front;
    int rear;
    int *que;
} Deck;

int InitialIize(Deck *d, int max) {
    
    d->num = d->front = d->rear = 0;
    
    if((d->que = calloc(max, sizeof(int))) == NULL) {
        d->max = 0;
        return -1;
    }
    
    d->max = max;
    return 0;
}

int EnqueFront(Deck *d, int v) {
    
    if(d->num >= d->max)
        return -1;
    
    d->num++;
    if(--d->front < 0)
        d->front = d->max - 1;
    
    d->que[d->front] = v;
    return 0;
}

int EnqueRear(Deck *d, int v) {
    
    if(d->num >= d->max)
        return -1;
    
    d->num++;
    d->que[d->rear++] = v;
    
    d->rear = d->rear % d->max;
    return 0;
}

int DequeFront(Deck *d, int *v) {
    
    if(d->num <= 0)
        return -1;
    
    d->num--;
    *v = d->que[d->front++];
    
    d->front = d->front % d->max;
    return 0;
}

int DequeRear(Deck *d, int *v) {
    
    if(d->num <= 0)
        return -1;
    
    d->num--;
    
    if(--d->rear < 0)
        d->rear = d->max - 1;
    
    *v = d->que[d->rear];
    return 0;
    
}
void Clear(Deck *d) {
    d->num = d->front = d->rear = 0;
}

int Size(Deck *d) {
    return d->num;
}

int IsEmpty(Deck *d) {
    return (d->num <= 0);
}

int PeekFront(Deck *d, int *v) {
    
    if(d->num <= 0)
        return -1;
    
    *v = d->que[d->front];
    return 0;
}

int PeekRear(Deck *d, int *v) {
    int temp;
    
    if(d->num <= 0)
        return -1;
    
    if((temp = d->rear - 1) < 0)
        temp = d->max - 1;
    
    *v = d->que[temp];
    return 0;
}

int N;
char com[12];
int temp;

int main() {
    Deck deck;
    
    scanf("%d", &N);
    InitialIize(&deck, N);
    
    while(N--) {
        
        scanf("%s", com);
        
        if(strcmp(com, "push_front") == 0) {
            scanf("%d\n", &temp);
            EnqueFront(&deck, temp);
        } else if(strcmp(com, "push_back") == 0) {
            scanf("%d\n", &temp);
            EnqueRear(&deck, temp);
        } else if(strcmp(com, "pop_front") == 0) {
            
            if(DequeFront(&deck, &temp) == 0)
                printf("%d\n", temp);
            else
                printf("-1\n");
            
        } else if(strcmp(com, "pop_back") == 0) {
            
            if(DequeRear(&deck, &temp) == 0)
                printf("%d\n", temp);
            else
                printf("-1\n");

            
        } else if(strcmp(com, "size") == 0) {
            printf("%d\n", Size(&deck));
        } else if(strcmp(com, "empty") == 0) {
            printf("%d\n", IsEmpty(&deck));
        } else if(strcmp(com, "front") == 0) {
            
            if(PeekFront(&deck, &temp) == 0)
                printf("%d\n", temp);
            else
                printf("-1\n");
            
        } else if(strcmp(com, "back") == 0) {
            
            if(PeekRear(&deck, &temp) == 0)
                printf("%d\n", temp);
            else
                printf("-1\n");

        }
    }
}