자료 구조 - 덱

자료 구조 - 덱

이전 시간에 공부한 큐(queue)는  삽입 삭제가 Front, Rear에서 발생하였습니다.

이를 보완한 것이 덱(Dequeue)입니다.

덱(Dequeue)은 Double ended queue의 약어이며 큐(queue)의 Front, Rear에서 각각 삽입, 삭제가 가능한 구조입니다.

- FRONT 단에서 front_enqueue(삽입), front_dequeue(삭제)

- REAR 단에서 rear_enqueue(삽입), rear_dequeue(삭제) 

배열 혹은 리스트로 모두 구현 가능하다. 기존에 큐(queue)에서 구현했던 enqueue는 rear_enqueue가 되고 dequeue는 front_dequeue가 된다. 나머지 rear_dequeue, front_enqueue만 구현하면 됩니다. FRONT, REAR 에서 삽입, 삭제가 발생하므로 삽입 삭제 시 FRONT, REAR 포인트의 위치 이동에 주의하여 구현하면 어렵지 않게 구현가능합니다.

---

이중 링크드 리스트로 구현한 덱(Dequeue)

1. 구조체 구현

typedef struct _node{

    int value;

    struct _node *next;

    struct _node *prev;

}node, *nptr;

typedef struct _queue{

    nptr front;

    nptr rear;

    int count;

}queue;

2. init 구현

queue *init_queue()

{

    queue *qptr = (queue*)malloc(sizeof(queue));

    qptr->front = NULL;

    qptr->rear = NULL;

    qptr->count = 0;

    return qptr;

}

3. front_enqueue 구현

void front_enqueue(queue *qptr, int _value)

{

    node *new_node = (node*)malloc(sizeof(node));

    new_node->value = _value;

    new_node->next = NULL;

    new_node->prev = NULL;

    if(qptr->count == 0)

    {

       qptr->front = new_node;

       qptr->rear = new_node;

    }

    else

    {

        qptr->front->prev = new_node;

        new_node->next = qptr->front;

        qptr->front = new_node;

    }

    qptr->count++;

}

4. front_dequeue 구현

void front_dequeue(queue *qptr)

{

    nptr remove;

    if(qptr->count == 0)

    {

        printf("Error : out of range\n");

    }

    else if(qptr->count == 1)

    {

        remove = qptr->rear;

        qptr->rear = NULL;

        qptr->front = NULL;

        qptr->count--;

        free(remove);

    }

    else

    {

        remove = qptr->front;

        remove->next->prev = NULL;

        qptr->front = remove->next;

        free(remove);

        qptr->count--;

    }

}

5. rear_enqueue 구현

void rear_enqueue(queue *qptr, int _value)

{

    node *new_node = (node*)malloc(sizeof(node));

    new_node->value = _value;

    new_node->next = NULL;

    new_node->prev = NULL;

    if(qptr->count == 0)

    {

       qptr->front = new_node;

       qptr->rear = new_node;

    }

    else

    {

        qptr->rear->next = new_node;

        new_node->prev = qptr->rear;

        qptr->rear = new_node;

    }

    qptr->count++;

}

6. rear_dequeue 구현

void rear_dequeue(queue *qptr)

{

    nptr remove;

    if(qptr->count == 0)

    {

        printf("Error : out of range\n");

    }

    else if(qptr->count == 1)

    {

        remove = qptr->rear;

        qptr->rear = NULL;

        qptr->front = NULL;

        qptr->count--;

        free(remove);

    }

    else

    {

        remove = qptr->rear;

        remove->prev->next = NULL;

        qptr->rear = remove->prev;

        free(remove);

        qptr->count--;

    }

}

7. print 구현

void print_queue(queue *qptr)

{

    nptr tmp;

    if(qptr->count == 0)

    {

        printf("Error : My dequeue is empty \n");

    }

    else

    {

        tmp = qptr->front;

        printf("value is : ");

        while(tmp != NULL)

        {

            printf("%d ",tmp->value);

            tmp = tmp->next;

        }

        printf("\n");       

    }

}

---

Result

=> front 에서 삽입 삭제를 수행한 결과

=> rear 에서 삽입 삭제를 수행한 결과

---