[Data Structure] #3-3 덱 (Deque)

덱(Deque)

 덱(Deque)은 Double ended queue를 줄인 말이다. 말 그대로 끝이 2개라는 의미다. 이게 무슨 말일까?

 보통의 Queue는 뒤 쪽(rear)으로 들어가서 앞 쪽(front)로 나온다. 앞과 뒤가 구분이 되어있는 것이 보통의 Queue다. 끝이 2개라는 의미는 바로 양 쪽이 앞이자 뒤가 된다는 의미이다.

 즉, 앞과 뒤 모두에 front와 rear 포인터가 존재한다. 이렇게 되면 앞쪽에서도 insert가 가능하고 뒤쪽에서도 remove가 가능해진다. 이러한 형태를 구현하기 위해서 Deque은 이중 연결 리스트(Doubly Linked List)를 사용한다.

 코드를 보자. 

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

typedef int element;

// Double linked list 로 Deque를 구현
typedef struct {
    element data;
    struct DlistNode* llink;
    struct DlistNode* rlink;
} DlistNode;

// 양방향이기 때문에 양쪽 pointer를 가진다
typedef struct {
    DlistNode* head;
    DlistNode* tail;
} DequeType;

void error(char *message){
    fprintf(stderr,"%s\n",message);
    exit(1);
}

void init(DequeType *d){
    d->head = NULL;
    d->tail = NULL;
}

DlistNode *create_node(DlistNode *llink, element item, DlistNode *rlink){
    DlistNode *new_node = (DlistNode*) malloc(sizeof(DlistNode));
    new_node->data = item;
    new_node->llink = (struct DlistNode*) llink;
    new_node->rlink = (struct DlistNode*) rlink;
    return new_node;
}

int is_empty(DequeType *d){
    return d->head == NULL && d->tail == NULL;
}

void add_rear(DequeType *d, element item){
    DlistNode *new_node = create_node(d->tail, item, NULL);
    if (is_empty(d))
        d->head = new_node;
    else
        d->tail->rlink = (struct DlistNode*) new_node;
    d->tail = new_node;
}

void add_front(DequeType *d, element item){
    DlistNode *new_node = create_node(NULL, item, d->head);
    if (is_empty(d))
        d->tail = new_node;
    else
        d->head->llink = (struct DlistNode*) new_node;
    d->head = new_node;
}

element delete_front(DequeType *d){
    if (is_empty(d)) error("deque is empty");
    
    DlistNode *removed = d->head;
    element item = removed->data;
    
    d->head = (DlistNode*) d->head->rlink;
    
    if (d->head == NULL)
        d->tail = NULL;
    else
        d->head->llink = NULL;
    free(removed);
    return item;
}

element delete_rear(DequeType *d){
    if (is_empty(d)) error("deque is empty");
    DlistNode *removed = d->tail;
    element item = removed->data;
    d->tail = (DlistNode*) d->tail->llink;
    
    if (d->tail == NULL)
        d->head = NULL;
    else
        d->tail->rlink = NULL;
        
    free(removed);
    return item;
} 

void display(DequeType *d){
    DlistNode *p;
    if (is_empty(d)) error("deque is empty");

    printf("( ");
    for (p=d->head; p!=NULL; p=(DlistNode*)p->rlink)
        printf("%d ",p->data);
    printf(")\n");
}

int main(){
    DequeType d;
    init(&d);
    
    add_front(&d, 10);
    add_front(&d, 20);
    add_rear(&d, 30);
    display(&d);
    
    delete_front(&d);
    delete_rear(&d);
    display(&d);
    
    return 0;
}