[자료구조] 덱 (Deque)

덱(Deque; Double-Ended Queue)이란?

앞서 설명한 큐는 데이터가 삽입되는 곳과 삭제되는 곳이 달랐지만 덱은 그렇지 않습니다. 큐의 앞과 뒤에서 모두 삽입과 삭제가 가능한 큐를 의미합니다.

 

덱 ADT

덱의 특징에 맞게 양쪽에서 원소를 추가할 수 있게 짜여져 있습니다.

create() ::= 덱 생성
init(dq) ::= 덱 초기화
is_empty(dq) ::= 덱이 비었는지 검사
is_full(dq) ::= 덱이 꽉 차있는지 검사
add_front(dq, e) ::= 덱의 앞 원소 추가
add_rear(dq, e) ::= 덱의 뒤 원소 추가
delete_front(dq) ::= 덱의 앞 원소 제거 및 반환
delete_rear(dq) ::= 덱의 뒤 원소 제거 및 반환
pop_front(q) ::= 덱의 앞 원소 반환
pop_rear(q) ::= 덱의 뒤 원소 반환

 

덱 (Deque)

추상 자료형을 바탕으로 덱을 구현해봅시다.

 

덱 구조체

구조체를 이용해 덱의 구조를 구현해봅시다.

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

일반적인 큐와 동일하게 구조체 안에 front와 rear 변수가 선언되어 있습니다. front는 첫 번째 원소를 가리키고 rear는 마지막 원소를 가리킵니다. 구조체는 별 다른 차이점은 없습니다.

하지만 앞으로 나올 함수에서 앞과 뒤에서 동작할 여러 가지 함수들을 만들 것입니다. 삽입, 삭제, 반환이 모두 2번씩 이루어져야 합니다.

 

add_front(dq, item)

큐 앞에서 원소를 삽입하는 함수입니다. 앞에서 삽입하기 때문에 front가 가리키고 있는 인덱스에 삽입해주면 됩니다.

void add_front(Deque *dq, element item) {
    if(is_full(dq)) {
        fprintf(stderr, "덱이 꽉 차있습니다.");
    }
    dq->data[dq->front] = item;
    dq->front = (dq->front - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
}

근데 큐에서 했던 연산이랑 비교해보면 살짝 복잡합니다. 사실 지금 덱은 선형 덱이 아닌 원형 덱입니다. 선형 덱은 선형 큐와 마찬가지로 rear가 배열 크기에 도달하게 되면 더 이상 삽입 연산을 수행할 수 없기 때문에 덱도 마찬가지로 원형으로 만드는 것이 효율적입니다. 하지만 원형 덱이라도 연산이 뭔가 이상하네요. 삽입 연산이어서 인덱스가 증가되어야 할 것 같은데 왜 숫자를 뺄까요? 아래에서 자세하게 설명하기로 하고 일단 넘어갑시다.

 

add_rear(dq, item)

큐 뒤에서 원소를 삽입하는 함수입니다. 뒤에서 삽입하기 때문에 rear가 가리키고 있는 인덱스에 삽입해주면 됩니다.

void add_rear(Deque *dq, element item) {
    if(is_full(dq)) {
        fprintf(stderr, "덱이 꽉 차있습니다.");
    }
    dq->rear = (dq->rear + 1) % MAX_QUEUE_SIZE;
    dq->data[dq->rear] = item;
}

 

delete_front(dq)

큐 앞에서 원소를 삭제하는 함수입니다. 앞에서 삭제하기 때문에 front가 가리키고 있는 인덱스를 삭제해주면 됩니다.

element delete_front(Deque *dq) {
    if(is_empty(dq)) {
        fprintf(stderr, "덱이 비어있습니다.");
    }
    dq->front = (dq->front + 1) % MAX_QUEUE_SIZE;
    return dq->data[dq->front];
}

 

delete_rear(dq)

큐 뒤에서 원소를 삭제하는 함수입니다. 뒤에서 삭제하기 때문에 rear가 가리키고 있는 인덱스를 삭제해주면 됩니다.

element delete_rear(Deque *dq) {
    int prev = dq->rear;
    if(is_empty(dq)) {
        fprintf(stderr, "덱이 비어있습니다.");
    }
    dq->rear = (dq->rear - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
    return dq->data[prev];
}

 

get_front(dq)

큐 앞에서 원소를 반환하는 함수입니다. front가 가리키고 있는 원소를 반환하면 됩니다.

element get_front(Deque *dq) {
    if(is_empty(dq)) {
        fprintf(stderr, "덱이 비어있습니다.");
    }
    return dq->data[(dq->front + 1) % MAX_QUEUE_SIZE];
}

 

get_rear(dq)

큐 뒤에서 원소를 반환하는 함수입니다. rear가 가리키고 있는 원소를 반환하면 됩니다.

element get_rear(Deque *dq) {
    if(is_empty(dq)) {
        fprintf(stderr, "덱이 비어있습니다.");
    }
    return dq->data[dq->rear];
}

 

전체 코드는 아래와 같습니다.

#include <stdio.h>

#define MAX_DEQUE_SIZE 5

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

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

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

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

// 원소를 삽입하는 함수
void add_front(Deque *dq, element item) {
    if(is_full(dq)) {
        fprintf(stderr, "덱이 꽉 차있습니다.");
    }
    dq->data[dq->front] = item;
    dq->front = (dq->front - 1 + MAX_DEQUE_SIZE) % MAX_DEQUE_SIZE;
}

void add_rear(Deque *dq, element item) {
    if(is_full(dq)) {
        fprintf(stderr, "덱이 꽉 차있습니다.");
    }
    dq->rear = (dq->rear + 1) % MAX_DEQUE_SIZE;
    dq->data[dq->rear] = item;
}

// 원소를 삭제하는 함수
element delete_front(Deque *dq) {
    if(is_empty(dq)) {
        fprintf(stderr, "덱이 비어있습니다.");
    }
    dq->front = (dq->front + 1) % MAX_DEQUE_SIZE;
    return dq->data[dq->front];
}

element delete_rear(Deque *dq) {
    int prev = dq->rear;
    if(is_empty(dq)) {
        fprintf(stderr, "덱이 비어있습니다.");
    }
    dq->rear = (dq->rear - 1 + MAX_DEQUE_SIZE) % MAX_DEQUE_SIZE;
    return dq->data[prev];
}

// 원소를 반환하는 함수
element get_front(Deque *dq) {
    if(is_empty(dq)) {
        fprintf(stderr, "덱이 비어있습니다.");
    }
    return dq->data[(dq->front + 1) % MAX_DEQUE_SIZE];
}

element get_rear(Deque *dq) {
    if(is_empty(dq)) {
        fprintf(stderr, "덱이 비어있습니다.");
    }
    return dq->data[dq->rear];
}

void print_dq(Deque *dq) {
    printf("DEQUE(front=%d rear=%d) = ", dq->front, dq->rear);
    if(!is_empty(dq)) {
        int i = dq->front;
        do {
            i = (i + 1) % (MAX_DEQUE_SIZE);
            printf("%d | ", dq->data[i]);
            if(i == dq->rear) {
                break;
            }
        } while (i != dq->front);
    }
    printf("\\n");
}

int main() {
    Deque dq;
    init_deque(&dq);
    for(int i = 0; i < 3; i++) {
        add_front(&dq, i);
        print_dq(&dq);
    }
    for(int i = 0; i < 3; i++) {
        delete_rear(&dq);
        print_dq(&dq);
    }
}

 

덱에서 추가된 연산

큐애는 없는 덱에만 존재하는 연산이 있습니다.

1. 앞에서 원소를 삽입하는 add_front(dq, item)
2. 뒤에서 원소를 삭제하는 delete_rear(dq)

 

하나씩 살펴봅시다.

 

먼저, 앞에서 삽입할 때는 제일 앞의 원소의 위치가 어딘지 필요합니다. 하지만 앞에서 삽입을 하게 되면 인덱스가 0인 배열에 값이 들어있으면 더 이상 삽입하지 못 하게 됩니다. 하지만 덱을 원형으로 생각해보면 삽입을 할 수 있게 됩니다. 왜냐하면 0 이전에는 배열의 끝 인덱스가 나오기 때문이죠.

(대충 원형 덱으로 이전 인덱스에 공백이 나오지 않는 그림)

 

여기서 1을 빼주는 연산이 이해가 되기 시작합니다. 덱에 있는 데이터를 하나씩 밀 수 없으니 인덱스를 하나 빼는 겁니다. 그리고 덱 크기의 숫자를 더해주는 이유도 인덱스는 음수가 될 수 없기 때문에 (엄밀히 말해서 C언어에서는 인덱스를 음수로 넣을 수 있지만 선언하지 않은 데이터에 접근하는 것이기 때문에 우리가 얻고 싶은 데이터를 얻을 수는 없습니다.) 덱의 크기를 더해줍니다.

 

두 번째로 delete_rear(dq)도 마찬가지입니다. 삭제할 때에 인덱스가 0인 원소를 지우면 1을 빼면 음수가 되기 때문에 그러한 경우를 대비해 덱의 크기를 더하고 나머지를 구합니다.