Chap07. 덱 (Deque)

Deque = Double ended queue 

앞으로도 뒤로도 데이터를 넣고 뺄수 있는 자료구조 

 

덱의 ADT

void DequeInit(Deque *pdeq);

 

int DQIsEmpty(Deque *pdeq);

 

void DQAddFirst(Deque *pdeq, Data data);

 

void DQAddLast(Deque *pdeq, Data data);

 

Data DQRemoveFirst(Deque *pdeq);

 

Data DQRemoveLast(Deque *pdeq);

 

Data DQGetFirst(Deque *pdeq);

 

Data DQGetLast(Deque *pdeq);

 

---

양방향 연결 리스트 기반 덱의 구현

덱은 배열로도 연결 리스트로도 구현이 가능하지만, 가장 많이 사용하는 것은 양방향 연결 리스트를 이용한 구현이다.

이는 덱에서 마지막 요소를 지우는 연산을 구현할때 노드가 양방향으로 연결되어 있어야 구현이 쉽기 때문이다.

 

 

Deque.h

/*
 * 양방향 연결 리스트 기반 덱 (deque)
 */

#ifndef DEQUE_DEQUE_H
#define DEQUE_DEQUE_H

#define TRUE 1
#define FALSE 0

typedef int Data;

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

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

void DequeInit(Deque *pdeq);
int DQIsEmpty(Deque *pdeq);

void DQAddFirst(Deque *pdeq, Data data);
void DQAddLast(Deque *pdeq, Data data);

Data DQRemoveFirst(Deque *pdeq);
Data DQRemoveLast(Deque *pdeq);

Data DQGetFirst(Deque *pdeq);
Data DQGetLast(Deque *pdeq);


#endif //DEQUE_DEQUE_H

Deque.c

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

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

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

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

    // newNode가 기존 첫 노드 가르키도록함
    newNode->next = pdeq->head;

    // 첫 노드 삽입시, tail이 삽입하는 노드 가리키도록
    if(DQIsEmpty(pdeq))
        pdeq->tail = newNode;
    // 두 번째 이후 노드 삽입시, 기존 첫 노드의 prev가 새 노드 가르키도록
    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;
    if(DQIsEmpty(pdeq))
    {
        printf("Deque Memory Error");
        exit(-1);
    }
    rdata = pdeq->head->data;

    // head 한 칸 옮기고 메모리 해제
    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;
    if(DQIsEmpty(pdeq))
    {
        printf("Deque Memory Error");
        exit(-1);
    }
    rdata = pdeq->tail->data;

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

    // remove 결과 덱이 비었다
    if(pdeq->tail == NULL)
        pdeq->head = NULL;
    else
        pdeq->tail->next = NULL;

    return rdata;
}

Data DQGetFirst(Deque *pdeq)
{
    if(DQIsEmpty(pdeq))
    {
        printf("Deque Memory Error");
        exit(-1);
    }
    return pdeq->head->data;
}

Data DQGetLast(Deque *pdeq)
{
    if(DQIsEmpty(pdeq))
    {
        printf("Deque Memory Error");
        exit(-1);
    }
    return pdeq->tail->data;
}

DequeMain.c

#include <stdio.h>
#include "Deque.h"


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

    // data input
    DQAddFirst(&deq, 3);
    DQAddFirst(&deq, 2);
    DQAddFirst(&deq, 1);

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

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

    printf("\n");

    // data input
    DQAddFirst(&deq, 3);
    DQAddFirst(&deq, 2);
    DQAddFirst(&deq, 1);

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

    // data dequeue
    while(!DQIsEmpty(&deq))
        printf("%d ", DQRemoveLast(&deq));
}

 

 

---

문제 07-1 [덱을 기반으로 큐를 구현하기]

덱은 큐가 갖고있는 기능을 모두 포함하고 있기 때문에 큐의 기능에 맞는 덱의 함수를 콜해주기만 하면 된다.

 

DequeBaseQueue.h

/*
 * Deque 기반 Queue 구현 (Deque.h 헤더 사용)
 */

#ifndef CHAP07_DEQUEBASEQUEUE_DEQUEBASEQUEUE_H
#define CHAP07_DEQUEBASEQUEUE_DEQUEBASEQUEUE_H

#include "Deque.h"

typedef Deque Queue;

void QueueInit(Queue *pq);
int QIsEmpty(Queue *pq);
void Enqueue(Queue *pq, Data data);
Data Dequeue(Queue *pq);
Data QPeek(Queue *pq);


#endif //CHAP07_DEQUEBASEQUEUE_DEQUEBASEQUEUE_H

DequeBaseQueue.c

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

void QueueInit(Queue *pq)
{
    DequeInit(pq);
}

int QIsEmpty(Queue *pq)
{
    return DQIsEmpty(pq);
}

void Enqueue(Queue *pq, Data data)
{
    DQAddLast(pq, data);
}

Data Dequeue(Queue *pq)
{
    return DQRemoveFirst(pq);
}

Data QPeek(Queue *pq)
{
    return DQGetFirst(pq);
}