덱의 이해와 구현

큐가 뒤로 넣고 앞으로 빼는 구조라면 덱은 앞,뒤로 넣고 앞,뒤로 뺄 수 있는 구조이다. 즉 양방향으로 넣고 뺄 수 있다.

그래서 덱이란 double-ended queue라는 의미로 스택과 큐의 특성을 모두 가지고 있다.

 

덱에서 구현되어야 할건 앞으로 넣기, 뒤로 넣기, 앞으로 빼기, 뒤로 빼기

덱은 이전의 스택, 큐와 달리 양방향 리스트로 구현한다.

앞뒤로 자유롭게 이동하기 위해 next와 prev로 방향을 정할 수 있다.

 

앞으로 넣기

스택과 비슷하게 head에 데이터를 추가한다.

head앞에 새로운 데이터를 추가한 뒤 새로운 데이터를 head로 지정한다.

 

뒤로 넣기

tail 뒤에 새로운 데이터를 추가한 뒤 새로운 데이터를 tail로 지정한다.

 

앞으로 빼기

head의 next를 head로 지정한 뒤 원래의 head를 free한다.

 

뒤로 빼기

tail의 prev(tail의 뒷 데이터)를 tail로 지정한 뒤 원래의 tail을 free한다.

 

 

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

typedef int Data;

typedef struct _node{
    Data data;
    struct _node * prev;
    struct _node * next;
}Node;

typedef struct _dlDeque{
    Node * head;
    Node * tail;
}DLDeque;

typedef DLDeque Deque;

void DequeInit(Deque * pdeq){
    pdeq->head=NULL;
    pdeq->tail=NULL;

}

int DQIsEmpty(Deque * pdeq){
    if(pdeq->head == NULL){
        return 1;
    }
    else
        return 0;
}

void DQAddFirst(Deque * pdeq,Data data){
    Node * newNode=(Node*)malloc(sizeof(Node));
    newNode->data = data;

    newNode->next = pdeq->head;

    if(DQIsEmpty(pdeq))
        pdeq->tail=newNode;
    else
        pdeq->head->prev=newNode;

    newNode->prev=NULL;
    pdeq->head=newNode;
}

void DQAddLast(Deque * pdeq,Data data){
    Node * newNode=(Node*)malloc(sizeof(Node));
    newNode->data=data;

    newNode->prev = pdeq->tail;

    if(DQIsEmpty(pdeq))
        pdeq->head = newNode;
    else
        pdeq->tail->next = newNode;

    newNode->next = NULL;
    pdeq->tail=newNode;
}

Data DQRemoveFirst(Deque * pdeq){
    Node * rnode = pdeq->head;
    Data rdata;

    rdata = pdeq->head->data;

    pdeq->head = pdeq->head->next;
    free(rnode);

    if(pdeq->head == NULL)
        pdeq->tail = NULL;
    else   
        pdeq->head->prev=NULL;

    return rdata;
}

Data DQRemoveLast(Deque * pdeq){
    Node * rnode = pdeq->tail;
    Data rdata = pdeq->tail->data;

    pdeq->tail=pdeq->tail->prev;
    free(rnode);

    if(pdeq->tail == NULL)
        pdeq->head = NULL;
    else   
        pdeq->tail->next=NULL;

    return rdata;
}

Data DQGetFirst(Deque * pdeq){
    return pdeq->head->data;
}

Data DQGetLast(Deque * pdeq){
    return pdeq->tail->data;
}

int main(){
    Deque deq;
    
    DequeInit(&deq);

    DQAddFirst(&deq,3);
    DQAddFirst(&deq,2);
    DQAddFirst(&deq,1);

    DQAddLast(&deq,4);
    DQAddLast(&deq,5);
    DQAddLast(&deq,6);

    while(!DQIsEmpty(&deq))
        printf("%d ",DQRemoveFirst(&deq));

    printf("\n");

    DQAddFirst(&deq,3);
    DQAddFirst(&deq,2);
    DQAddFirst(&deq,1);

    DQAddLast(&deq,4);
    DQAddLast(&deq,5);
    DQAddLast(&deq,6);
    
    while(!DQIsEmpty(&deq))
        printf("%d ",DQRemoveLast(&deq));
}