[ch 07-5] 덱의 이해와 구현

[덱의 개념]

- 스택과 큐의 특성의 조합한 형태로서 데이터를 앞으로도 뒤로도 넣을 수 있고, 앞으로도 뒤로 뺄 수 있는 자료구조

[덱의 ADT]

void DequeInit(Deque * pdeq);

- 덱의 초기화를 진행

- 덱 생성 후 제일 먼저 호출되어야 하는 함수

int DQIsEmpty(Deque * pdeq);

- 덱이 빈 경우 TRUE(1)을 반환, 그렇지 않은 경우 FALSE(0)을 반환

void DQAddFirst(Deque * pdeq, int data);

- 덱의 '머리'에 데이터를 저장. data로 전달된 값을 저장

void DQAddLast(Deque * pdeq, int data);

- 덱의 '꼬리'에 데이터를 저장. data로 전달된 값을 저장

int DQRemoveFirst(Deque * pdeq);

- 덱의 '머리'에 위치한 데이터를 반환 및 소멸

int DQRemoveLast(Deque * pdeq);

- 덱의 '꼬리'에 위치한 데이터를 반환 및 소멸

int DQGetFirst(Deque * pdeq);

- 덱의 '머리'에 위치한 데이터를 소멸하지 않고 반환

int DQGetLast(Deque * pdeq);

- 덱의 '꼬리'에 위치한 데이터를 소멸하지 않고 반환

[소스 코딩]

■ Deque.h

#ifndef DEQUE_H_
#define DEQUE_H_
 
#define    TRUE     1
#define    FALSE    0
 
typedef struct _node        // 노드
{
    int data;               // 사용자에게 입력 받은 데이터를 저장
    struct _node * prev;    // 노드가 이전 노드를 가리킬 포인터 변수
    struct _node * next;    // 노드가 다음 노드를 가리킬 포인터 변수
} Node;
 
typedef struct _dlDque      // 양방향 연결 리스트 덱
{
    Node * head;            // 앞 노드를 가리킬 포인터 변수
    Node * tail;            // 뒤 노드를 가리킬 포인터 변수
} DLDeque;
 
typedef DLDeque Deque;
 
void DequeInit(Deque * pdeq);               // 덱을 초기화
int DQIsEmpty(Deque * pdeq);                // 덱에 데이터가 비워져 있는지 확인
 
void DQAddFirst(Deque * pdeq, int data);    // 덱의 앞에 노드를 추가
void DQAddLast(Deque * pdeq, int data);     // 덱의 뒤에 노드를 추가
 
int DQRemoveFirst(Deque * pdeq);            // 덱의 앞에 있는 노드를 삭제
int DQRemoveLast(Deque * pdeq);             // 덱의 뒤에 있는 노드를 삭제
 
int DQGetFirst(Deque * pdeq);               // 덱의 앞에 있는 노드의 데이터를 조회
int DQGetLast(Deque * pdeq);                // 덱의 뒤에 있는 노드의 데이터를 조회
 
#endif

■ Deque.c

#include <stdio.h>
#include <stdlib.h>        // malloc, free 함수를 사용하기 위함
#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, int 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, int 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;
}
 
// 덱의 앞에 있는 노드를 삭제 //
int DQRemoveFirst(Deque * pdeq)
{
    Node * rnode = pdeq->head;
    int rdata;
 
    if(DQIsEmpty(pdeq))
    {
        printf("Deque Memory Empty!!");
        exit(-1);
    }
 
    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;
}
 
// 덱의 뒤에 있는 노드를 삭제 //
int DQRemoveLast(Deque * pdeq)
{
    Node * rnode = pdeq->tail;
    int rdata;
 
    if(DQIsEmpty(pdeq))
    {
        printf("Deque Memory Empty!!");
        exit(-1);
    }
 
    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;
}
 
// 덱의 앞에 있는 노드의 데이터를 조회 //
int DQGetFirst(Deque * pdeq)
{
    if(DQIsEmpty(pdeq))
    {
        printf("Deque Memory Empty!!");
        exit(-1);
    }
 
    return pdeq->head->data;
}
 
// 덱의 뒤에 있는 노드의 데이터를 조회 //
int DQGetLast(Deque * pdeq)
{
    if(DQIsEmpty(pdeq))
    {
        printf("Deque Memory Empty!!");
        exit(-1);
    }
 
    return pdeq->tail->data;
}

■ 사용되는 함수의 설명

// 덱을 초기화 //
void DequeInit(Deque * pdeq)
{
    pdeq->head = NULL;
    pdeq->tail = NULL;
}

- 덱의 머리와 꼬리를 가리킬 포인터 변수 'head, tail'을 'NULL'로 초기화

// 덱에 데이터가 비워져 있는지 확인 //
int DQIsEmpty(Deque * pdeq)
{
    if(pdeq->head == NULL)
        return TRUE;
 
    else
        return FALSE;
}

- 'head'가 가리키는 대상을 기준으로 덱에 데이터가 존재하는지 판단

// 'head'가 가리키는 대상이 'NULL'일 경우

- TRUE(1)을 반환

// 아닐 경우

- FALSE(0)을 반환

// 덱의 앞에 노드를 추가 //
void DQAddFirst(Deque * pdeq, int 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;
}

★ 'head'가 가리키는 노드의 앞쪽에 새로운 노드를 배치하고 'head'가 다시 새로운 노드를 가리키게 됨

- 'newNode'라는 새로운 노드를 생성(동적 메모리 할당)

- 'newNode' 'data'에 사용자에게 입력된 'data'를 저장

- 'newNode'의 '다음(next)'에는 'head'가 가리키는 대상을 가리킴

// 덱에 노드가 없는 최초 상태일 경우

- 'tail'이 'newNode'를 가리킴

// 덱에 노드가 존재할 경우

- 'head'의 '이전(prev)'에는 'newNode'를 가리킴

- 머리에 있는 노드는 이전에 아무것도 없기 때문에 'newNode'의 '이전(prev)'에는 'NULL'을 저장

- 'head'가 'newNode'를 가리킴

// 덱의 뒤에 노드를 추가 //
void DQAddLast(Deque * pdeq, int 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;
}

★ 'tail'이 가리키는 노드의 다음에는 새로운 노드를 배치하고 'tail'이 다시 새로운 노드를 가리키게 됨

- 'newNode'라는 새로운 노드를 생성(동적 메모리 할당)

- 'newNode' 'data'에 사용자에게 입력된 'data'를 저장

- 'newNode'의 '이전(prev)'에는 'tail'이 가리키는 대상을 가리킴

// 덱에 노드가 없을(최초 상태 포함) 경우

- 'head'가 'newNode'를 가리킴

// 덱에 노드가 존재할 경우

- 'tail'의 '다음(next)'에는 'newNode'를 가리킴

- 꼬리에 있는 노드는 다음에 아무것도 없기 때문에 'newNode'의 '다음(next)'에는 'NULL'을 저장

- 'tail'이 'newNode'를 가리킴

// 덱의 앞에 있는 노드를 삭제 //
int DQRemoveFirst(Deque * pdeq)
{
    Node * rnode = pdeq->head;
    int rdata;
 
    if(DQIsEmpty(pdeq))
    {
        printf("Deque Memory Empty!!");
        exit(-1);
    }
 
    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;
}

★ 'head'가 가리키는 노드는 반환 및 소멸되고 'head'의 다음(next)에 있던 노드가 'head'가 됨

- 삭제할 노드를 가리킬 'rnode'가 'head'가 가리키는 노드를 가리킴

- 반환할 데이터를 저장할 'rdata' 선언

// 덱에 노드가 없을 경우

- 덱이 비워져 있다는 메시지 출력 후 프로그램 종료

- 'head'가 가리키는 노드의 'data'를 'rdata'에 저장

- 'head'가 가리키는 노드는 삭제될 예정이기 때문에 'head'는 가리키던 노드의 '다음(next)'에 있던 노드를 가리킴

- 'rnode' 삭제(가리키던 노드 포함)

// 'head'가 이동 후 가리키는 대상이 없어 'NULL'일 경우

- 'tale'도 'NULL'을 저장

// 아닐 경우

- 'head'의 '이전(prev)'은 'NULL'을 저장

- 반환할 데이터를 저장했던 'rdata'를 반환

// 덱의 뒤에 있는 노드를 삭제 //
int DQRemoveLast(Deque * pdeq)
{
    Node * rnode = pdeq->tail;
    int rdata;
 
    if(DQIsEmpty(pdeq))
    {
        printf("Deque Memory Empty!!");
        exit(-1);
    }
 
    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;
}

★ 'tail'이 가리키는 노드는 반환 및 소멸되고 'tail'의 '이전(prev)'에 있던 노드가 'tail'이 됨

- 삭제할 노드를 가리킬 'rnode'가 'tail'이 가리키는 노드를 가리킴

- 반환할 데이터를 저장할 'rdata' 선언

// 덱에 노드가 없을 경우

- 덱이 비워져 있다는 메시지 출력 후 프로그램 종료

- 'tail'이 가리키는 노드의 'data'를 'rdata'에 저장

- 'tail'이 가리키는 노드는 삭제될 예정이기 때문에 'tail'는 가리키던 노드의 '이전(prev)'에 있던 노드를 가리킴

- 'rnode' 삭제(가리키던 노드 포함)

// 'tail'이 이동 후 가리키는 대상이 없어 'NULL'일 경우

- 'head'도 'NULL'을 저장

// 아닐 경우

- 'tail'의 '다음(next)'은 'NULL'을 저장

- 반환할 데이터를 저장했던 'rdata'를 반환

// 덱의 앞에 있는 노드의 데이터를 조회 //
int DQGetFirst(Deque * pdeq)
{
    if(DQIsEmpty(pdeq))
    {
        printf("Deque Memory Empty!!");
        exit(-1);
    }
 
    return pdeq->head->data;
}

// 덱에 노드가 없을 경우

- 덱이 비워져 있다는 메시지 출력 후 프로그램 종료

- 'head'가 가리키는 노드의 'data'를 반환

// 덱의 뒤에 있는 노드의 데이터를 조회 //
int DQGetLast(Deque * pdeq)
{
    if(DQIsEmpty(pdeq))
    {
        printf("Deque Memory Empty!!");
        exit(-1);
    }
 
    return pdeq->tail->data;
}

// 덱에 노드가 없을 경우

- 덱이 비워져 있다는 메시지 출력 후 프로그램 종료

- 'tail'이 가리키는 노드의 'data'를 반환

■ DequeMain.c

#include <stdio.h>
#include "Deque.h"
 
int main(void)
{
    // 덱 생성 및 초기화 //
    Deque deq;
    DequeInit(&deq);
 
    /* [데이터 넣기 1차] */
    // 데이터 넣기(앞) //
    DQAddFirst(&deq, 3); DQAddFirst(&deq, 2); DQAddFirst(&deq, 1);
 
    // 데이터 넣기(뒤) //
    DQAddLast(&deq, 4); DQAddLast(&deq, 5); DQAddLast(&deq, 6);
 
    // 데이터 꺼내기(앞부터) //
    printf("[데이터 앞에서부터 꺼내기]\n");
    while(!DQIsEmpty(&deq))
        printf("%d ", DQRemoveFirst(&deq));
 
    printf("\n\n");
 
    /* [데이터 넣기 2차] */
    // 데이터 넣기(앞) //
    DQAddFirst(&deq, 3); DQAddFirst(&deq, 2); DQAddFirst(&deq, 1);
 
    // 데이터 넣기(뒤) //
    DQAddLast(&deq, 4); DQAddLast(&deq, 5); DQAddLast(&deq, 6);
 
    // 데이터 꺼내기(뒤부터) //
    printf("[데이터 뒤에서부터 꺼내기]\n");
    while(!DQIsEmpty(&deq))
        printf("%d ", DQRemoveLast(&deq));
 
    return 0;
}

■ 실행결과