[백준 10866] 덱 [C]

백준 - 10866

---

풀이

Deque(Double Ended Queue)는 Stack와 Queue의 특징을 모두 갖는 이중 연결 리스트(Doubly Linked List)의 구조이다.

쉽게말해 방향이 반대인 Stack 두개를 붙인 것과 같다.

 

 

역방향 Stack

0	1	"	"	"	4998	4999
						front

 

정방향 Stcak

5000	5001	"	"	"	10000	10001
rear

 

역방향 Stack과 정방향 Stcak를 합치고, 

중간 index(4999~5000)에서 front를 감소, rear를 증가시키는 방식으로 구현했다.

0	1	"	"	"	4998	4999	5000	5001	"	"	"	10000	10001
						front	rear

단, front와 rear이 일치하는 경우는 없다는 점에 유의하자.

front + 1이 rear과 같을 때 Deque가 비어있는 것이다.

---

소스코드

#include <stdio.h>
#include <string.h>
#define MAX 10001
int front = MAX/2 - 1, rear = MAX/2;
int empty(){
    return front + 1 == rear;
}
int main(){
    int deque[MAX], N, n;
    char instruction[11];
    scanf("%d", &N);
    while (N--){
        scanf("%s", instruction);
		
        if (!(strcmp(instruction, "push_front"))){
            scanf("%d", &n);
            deque[front--] = n;
        }else if (!strcmp(instruction, "push_back")){
            scanf("%d", &n);
            deque[rear++] = n;
        }else if (!strcmp(instruction, "pop_front")){
            printf("%d\n", empty() ? -1 : deque[++front]);
        }else if (!strcmp(instruction, "pop_back")){
            printf("%d\n", empty() ? -1 : deque[--rear]);
        }else if (!strcmp(instruction, "size"))
            printf("%d\n", rear - front - 1);
        else if (!strcmp(instruction, "empty"))
            printf("%d\n", empty());
        else if (!(strcmp(instruction, "front")))
            printf("%d\n", empty() ? -1 : deque[front+1]);
        else if (!(strcmp(instruction, "back")))
            printf("%d\n", empty() ? -1 : deque[rear-1]);
    }
}

---

출처 및 참고자료

10866번: 덱

큐(자료구조) - 나무위키 (namu.wiki)