[자료구조] 덱(Deque)의 개념과 연결 리스트로 구현(C언어)

INDEX

1. 덱의 개념

2. 덱의 ADT를 구성하는 함수

3. 구현

3-1. 노드와 덱 구조체

3-2. 덱의 초기화와 비어 있는지 확인

3-3. 덱의 Front삽입과 Rear삽입

3-4. 덱의 Front추출과 Rear추출

1. 덱의 개념

덱은 아래의 그림처럼 직관적으로 이해하는 것이 가장 편하다. 스택이 입구와 출구가 1개뿐이었고 큐가 입구와 출구가 구별되는 일방향 통로의 느낌이었다면 덱은 큐의 업그레이드 버전인 양방향 이동 통로라고 이해할 수 있다. 그만큼 큐보다 개념적인 것들이 더 등장하게 된다.

덱에서 정보의 접근과 저장은 오직 Front와 Rear에서만 가능하다. 즉 큐보다 데이터 접근성이 더 좋아진 것이다. 덱의 Front에서 시작해서 Rear까지 이동할 수 있고 그 반대도 마찬가지로 가능하다. 덱에서는 포인터를 통한 자유로운 일차원 이동이 가능해진 것이다. 물론 배열의 인덱싱만큼 자유롭지는 못해도 스택과 큐에 비해서는 상당히 자유로워진 것이다.

 

그렇다고 해서 스택이나 큐가 덱보다 열등하다는 뜻은 아니다. 각각의 자료구조는 나름의 목적이 있기 때문이다. 

 

물론 배열로 덱을 구현할 수 있지만 연결 리스트를 활용하는 것이 동적 메모리 차원에서 더 바람직하기 때문에 노드로 구현해보기로 한다.   

2. 덱의 ADT를 구성하는 함수

• Front 노드 삽입
• Rear 노드 삽입
• Front 노드 pop(데이터 반환 및 노드 삭제)
• Rear 노드 pop
• Front를 시작으로 내부 데이터 전부 읽기

3. 구현

3-1. 노드와 덱 구조체

위의 그림과 같이 덱을 구현하고 싶다고 치면 Front는 왼쪽, Rear는 오른쪽에 위치시킬 것이다.

 

결국 어떤 노드에서 왼쪽으로 가면 Front에 가까워지는 것이고 오른쪽이면 Rear에 가까워지게 되는 것이다.

즉 노드에는 데이터를 저장할 변수와 left, right 노드가 자기 참조 구조체로 정의되야 한다.

#include "stdio.h"
#include "stdlib.h"

typedef struct Node {
    int data;
    struct Node *leftNode;
    struct Node *rightNode;
} Node;

 

덱같은 경우 Front와 Rear, 안에 저장되어 있는 데이터의 개수를 세는(덱이 비어있는지 확인할 때 사용된다) count 변수가 있어야 한다.

typedef struct Deque {
    int count;
    Node *front;
    Node *rear;
} Deque;

 

3-2. 덱의 초기화와 비어 있는지 확인

덱을 선언하였고 초기 덱의 상태(완전히 비어 있는 상태)를 지정해 주는 함수와 비어 있는지 확인하는 함수이다. 

Deque *setDeque() {
    Deque *d = (Deque *) malloc(sizeof(Deque));
    d->front = d->rear = NULL;
    d->count = 0;
    return d;
}

int isEmpty(Deque *d) {
    return !(d->count);
}

 

3-3. 덱의 Front삽입과 Rear삽입

void insertFront(Deque *d, int data) {
    Node *newnode = (Node *) malloc(sizeof(Node));
    newnode->data = data;
    if (isEmpty(d)) { // 비어 있으면 front==rear==newnode 인 상태로 만들어줌
        newnode->leftNode = newnode->rightNode = NULL;
        d->front = d->rear = newnode;
    } else {
        newnode->leftNode = NULL;
        newnode->rightNode = d->front;
        d->front->leftNode = newnode;
        d->front = newnode;
    }
    d->count++;
}

void insertRear(Deque *d, int data) {
    Node *newnode = (Node *) malloc(sizeof(Node));
    newnode->data = data;
    if (isEmpty(d)) {
        newnode->leftNode = newnode->rightNode = NULL;
        d->front = d->rear = newnode;
    } else {
        newnode->rightNode = NULL;
        newnode->leftNode = d->rear;
        d->rear->rightNode = newnode;
        d->rear = newnode;
    }
    d->count++;
}

 

 

3-4. 덱의 Front추출과 Rear추출

int popFront(Deque *d) {
    Node *ptr = d->front;
    int tmp = d->front->data; // 삭제될 포인터 tmp
    if (d->count == 1) { // 덱에 들어 있는 원소가 하나이면 양쪽 모두 널 할당 
        d->front = d->rear = NULL;
    } else {
        d->front = ptr->rightNode;
        ptr->rightNode->leftNode = NULL;
    }
    d->count--;
    free(ptr);
    return tmp;
}

int popRear(Deque *d) {
    Node *ptr = d->rear;
    int tmp = d->rear->data;
    if (d->count == 1) {
        d->front = d->rear = NULL;
    } else {
        d->rear = ptr->leftNode;
        d->rear->rightNode = NULL;
    }
    free(ptr);
    d->count--;

    return tmp;
}

 

이 다음으로는 덱의 내용물을 확인할 수 있는 함수이다. 

void printDequeContents(Deque *d) {
    Node *ptr = d->front;
    printf("Front -> ");
    while (ptr != NULL) {
        printf("%d ", ptr->data);
        ptr = ptr->rightNode;
    }
    puts("<- Rear");
}