[Data Structure] 덱(deque)

---

덱

 

 

덱(deque)은 double-ended queue의 줄임말, 즉 양쪽 방향에서 삽입과 삭제가 가능한 큐이다.

데이터 추가와 삭제가 전열(front)와 후열(rear) 모두에서 가능하기 때문에 스택이나 단순 큐보다 유연하게 사용 가능하다는 장점이 있다.

 

---

ADT

 

객체 (Object)

• 0 개 이상의 요소들로 구성된 선형 리스트

연산 (Operation)

• create(size) ::= 최대 크기가 size 인 공백 덱을 생성한다.
• init() ::= 덱를 초기화한다.
• is_full() ::= 덱의 원소 개수가 size 와 같다면 true 를, 아니라면 false 를 반환한다.
• is_empty() ::= 덱이 비어있다면 true 를, 아니라면 false 를 반환한다.
• add_front(item) := 덱이 가득 차 있지 않다면 덱의 맨 앞에 item 을 추가한다.
• add_rear(item) ::= 덱이 가득 차 있지 않다면 덱의 맨 뒤에 item 을 추가한다.
• delete_front() ::= 덱이 비어있지 않다면 덱의 가장 앞에 있는 원소를 제거해서 반환한다.
• delete_rear() ::= 덱이 비어있지 않다면 덱의 가장 뒤에 있는 원소를 제거해서 반환한다.
• front() 혹은 peek() ::= 덱이 비어있지 않다면 덱의 가장 앞에 있는 원소를 제거하지 않고 반환한다.
• rear() ::= 덱이 비어있지 않다면 덱의 가장 뒤에 있는 원소를 제거하지 않고 반환한다.
• size() ::= 덱의 원소 개수를 반환한다.

 

---

구현 | C

 

간단하게 C 를 통해 덱을 구현하였다. 덱은 양방향 삽입, 삭제가 가능해야 하기 때문에 선형 배열로 구현하면 삽입에 필요한 연산이 너무 많아지고, 따라서 기본적으로 연결 리스트를 사용하지 않더라도 원형 큐와 같이 원형으로 구현한다.

아래 코드는 main 함수를 제외한 덱 선언과 덱을 관리하는 코드이다. element 는 임의로 int 로 설정하였다. 에러는 임의로 -1 을 반환하도록 하였다.

#include <stdio.h>
#define MAX_QUEUE_SIZE 10

typedef int element;
typedef struct {
    element data[MAX_QUEUE_SIZE];
    int front;
    int rear;
} Deque;

void init_deque(Deque* d) {
    d->front = d->rear = 0;
}

int is_empty(Deque* d) {
    return (d->front == d->rear);
}

int is_full(Deque* d) {
    return ((d->rear + 1) % MAX_QUEUE_SIZE == d->front);
}

void add_front(Deque* d, element item) {
    if (is_full(d)) {
        printf("Deque is full\n");
        return;
    } else {
        d->data[d->front] = item;
        d->front = (d->front - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
    }
}

void add_rear(Deque* d, element item) {
    if (is_full(d)) {
        printf("Deque is full\n");
        return;
    } else {
        d->rear = (d->rear + 1) % MAX_QUEUE_SIZE;
        d->data[d->rear] = item;
    }
}

element delete_front(Deque* d) {
    if (is_empty(d)) {
        printf("Deque is empty\n");
        return -1;
    } else {
        d->front = (d->front + 1) % MAX_QUEUE_SIZE;
        return d->data[d->front];
    }
}

element delete_rear(Deque* d) {
    if (is_empty(d)) {
        printf("Deque is empty\n");
        return -1;
    } else {
        d->rear = (d->rear - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
        return d->data[d->rear];
    }
}

element front(Deque* d) {
    if (is_empty(d)) {
        printf("Deque is empty\n");
        return -1;
    } else {
        return d->data[(d->front + 1) % MAX_QUEUE_SIZE];
    }
}

element rear(Deque* d) {
    if (is_empty(d)) {
        printf("Deque is empty\n");
        return -1;
    } else {
        return d->data[(d->rear - 1) % MAX_QUEUE_SIZE];
    }
}

int size(Deque* d) {
    return (d->rear - d->front + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
}

void display(Deque* d) {
    for (int i = 0; i < MAX_QUEUE_SIZE; i++) {
        if (i > d->front && i <= d->rear) {
            printf("%d\t|", d->data[i]);
        } else if (d->front > d->rear) {
            if (i > d->front || i <= d->rear) {
                printf("%d\t|", d->data[i]);
            } else {
                printf("\t|");
            }
        } else {
            printf("\t|");
        }
    }
    printf("\n");
}

기존 원형 큐와 비교해서 두 가지 연산만 추가되었다. 기본적인 큐는 선입선출이라 후입후출을 담당하는 add_front() 와 delete_rear() 이 없었기 때문에 덱은 이 두 함수를 추가해준 것과 같다.

main 함수를 아래와 같이 구현하고 실행해보자.

int main()
{
    Deque d;
    init_deque(&d);
    add_front(&d, 1); display(&d);
    add_front(&d, 2); display(&d);
    add_front(&d, 3); display(&d);
    add_rear(&d, 4); display(&d);
    add_rear(&d, 5); display(&d);
    add_rear(&d, 6); display(&d);
    add_rear(&d, 7); display(&d);
    add_rear(&d, 8); display(&d);
    add_rear(&d, 9); display(&d);
    add_rear(&d, 10); display(&d);
    delete_rear(&d); display(&d);
    delete_front(&d); display(&d);
    delete_rear(&d); display(&d);
    delete_front(&d); display(&d);
    delete_front(&d); display(&d);
    return 0;
}

결과는 아래와 같다.

1	|	|	|	|	|	|	|	|	|	|
1	|	|	|	|	|	|	|	|	|2	|
1	|	|	|	|	|	|	|	|3	|2	|
1	|4	|	|	|	|	|	|	|3	|2	|
1	|4	|5	|	|	|	|	|	|3	|2	|
1	|4	|5	|6	|	|	|	|	|3	|2	|
1	|4	|5	|6	|7	|	|	|	|3	|2	|
1	|4	|5	|6	|7	|8	|	|	|3	|2	|
1	|4	|5	|6	|7	|8	|9	|	|3	|2	|
Deque is full
1	|4	|5	|6	|7	|8	|9	|	|3	|2	|
1	|4	|5	|6	|7	|8	|	|	|3	|2	|
1	|4	|5	|6	|7	|8	|	|	|	|2	|
1	|4	|5	|6	|7	|	|	|	|	|2	|
1	|4	|5	|6	|7	|	|	|	|	|	|
	|4	|5	|6	|7	|	|	|	|	|	|

덱이 원형이라 생각하고 봐야 한다. 처음에 1 을 가장 앞에 추가했는데, 다시 앞에 2 를 추가하려 하니 뒤로 가서 추가되었다. 원형이니 가장 앞에 추가된 것과 같다.

 

C 에서는 따로 deque 라이브러리가 존재하지 않지만, C++, Java 등에서는 별도의 라이브러리가 존재한다.

백준의 덱(링크)을 활용하여 덱을 구현하고 연습해볼 수 있다.