[덱] 덱(디큐)의 개념과 구현

작성일 | In

덱(디큐)란?

이번 글에서는 덱의 개념과 기본적인 기능의 구현 방법을 다룹니다.
deque는 double ended queue 의 줄임말입니다. 큐는 한 쪽에서 넣고, 반대 쪽에서 빼는 구조였다면, 덱은 양쪽 모두 삽입/삭제가 가능한 자료 구조입니다.
덱의 구현은 큐와 매우 유사하기 때문에 간단히 설명하고, 큐와 다른 점을 자세히 설명하도록 하겠습니다.

구현 방법

먼저 덱의 사이즈를 설정해줍시다.

1
#define SIZE 50010

그 다음에 앞 쪽을 가리키는 head와 뒤 쪽을 가리키는 rear를 20000으로 초기화 해주고 덱을 선언해줍니다.
20000으로 초기화 하는 이유는 이 글에서 최종적으로 해결하려는 문제에서 데이터가 최대 10000개가 들어오는데, 잠시 후에 구현할 push_front함수를 구현할 때 편리하게 하기 위해 중간 지점을 초기 위치로 지정했습니다.

1
2
int dq[SIZE];
int head = 20000, rear = 20000;

push_front

이제 push_front함수를 구현해봅시다.
push_front함수는 앞 쪽에 삽입하는 기능을 담당합니다.
구현 방법은 가장 앞 쪽을 나타내는 변수를 한 칸 앞쪽으로 옮긴 뒤, 그 자리에 데이터를 넣습니다.

1
2
3
4
1
2
3
4
int pop_front(){
    if(head >= rear) return -1;
    return dq[head++];
}

push_back

push_back함수는 큐에서의 push함수와 매우 유사하기에 설명은 생략합니다.

1
2
3
void push_back(int data){
    dq[rear++] = data;
}

pop_front

pop_front함수는 큐에서의 pop함수와 매우 유사하기에 설명은 생략합니다.

1
2
3
4
1
2
3
4
int pop_front(){
    if(head >= rear) return -1;
    return dq[head++];
}

pop_back

pop_back함수는 가장 뒤를 나타내는 변수를 앞으로 한 칸 옮긴 뒤, 기존 위치에 있던 값을 삭제합니다.

1
2
3
4
int pop_back(){
    if(head >= rear) return -1;
    return dq[--rear];
}

size, empty

size와 empty함수는 설명 없이 코드로 대체합니다.

1
2
3
4
5
6
7
int size(){
    return rear - head;
}

int empty(){
    return head == rear;
}

front, back

front와 back함수도 큐에서 구현했으므로 설명은 생략합니다.

1
2
3
4
5
6
7
8
9
int front(){
    if(head >= rear) return -1;
    return dq[head];
}

int back(){
    if(head >= rear) return -1;
    return dq[rear-1];
}

전체 코드

이렇게 해서 덱의 기본적인 기능의 구현은 마쳤습니다.
이제 https://www.acmicpc.net/problem/10866 문제를 풀어봅시다.

위에서 구현한 기능들만 사용하면 해결 가능한 문제입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <stdio.h>
#include <string.h>
#define SIZE 50010

int dq[SIZE];
int head = 20000, rear = 20000;

void push_front(int data){
    dq[--head] = data;
}

void push_back(int data){
    dq[rear++] = data;
}

int pop_front(){
    if(head >= rear) return -1;
    return dq[head++];
}

int pop_back(){
    if(head >= rear) return -1;
    return dq[--rear];
}

int size(){
    return rear - head;
}

int empty(){
    return head == rear;
}

int front(){
    if(head >= rear) return -1;
    return dq[head];
}

int back(){
    if(head >= rear) return -1;
    return dq[rear-1];
}

int main(){
    int n; scanf("%d", &n);
    while(n--){
        char op[20]; scanf("%s", op);
        if(!strcmp(op, "push_front")){
            int data; scanf("%d", &data);
            push_front(data);
        }else if(!strcmp(op, "push_back")){
            int data; scanf("%d", &data);
            push_back(data);
        }else if(!strcmp(op, "pop_front")){
            printf("%d\n", pop_front());
        }else if(!strcmp(op, "pop_back")){
            printf("%d\n", pop_back());
        }else if(!strcmp(op, "size")){
            printf("%d\n", size());
        }else if(!strcmp(op, "empty")){
            printf("%d\n", empty());
        }else if(!strcmp(op, "front")){
            printf("%d\n", front());
        }else if(!strcmp(op, "back")){
            printf("%d\n", back());
        }
    }
}