[자료구조] 덱(Deque) 컨셉, 배열/연결리스트 구현 매커니즘

덱, Deque(Double- ended- Queue)는 큐의 front 와 rear에서 모두 삽입,삭제가 가능한 큐로서, 스택과 큐의 특성을 모두 가지고 있다. 이는 덱을 스택으로도, 큐로도 사용할 수 있음을 의미한다.

 

- 스택으로 사용시: top > rear일때, push()  >> deque의 insertRear()와 비슷, Pop() > deleteRear()와 비슷함

- 큐로 사용시 : enqueue > insertRear()와 비슷, Dequeue()  > deleteFront()와 비슷

 

덱도 스택과 큐에서 구현한 방식처럼, 1) 배열로 구현하는 방법과, 2) 연결 리스트를 이용한 방법이 있다.  배열로 구현한 경우, 양쪽 끝에서 삽입/삭제 연산을 수행하면서 크기 변화와 저장된 원소의 순서변화가 많으므로 배열은 비효율적이다. 

따라서 연결리스트를 이용한 방법을 많이 사용한다. 양방향으로 연산이 가능한 이중 연결 리스트를 사용한다.

 

[이중 연결 리스트를 이용한 Deque 구현]

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

// 덱의 노드 구조체 정의
typedef struct Node {
    int data;
    struct Node *prev;
    struct Node *next;
} Node;

// 덱 구조체 정의
typedef struct Deque {
    Node *front;
    Node *rear;
} Deque;

// 덱 초기화 함수
void initializeDeque(Deque *deque) {
    deque->front = NULL;
    deque->rear = NULL;
}

// 덱이 비어있는지 확인하는 함수
int isEmpty(Deque *deque) {
    return (deque->front == NULL);
}

// 덱의 앞에 원소 추가 함수
void insertFront(Deque *deque, int data) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    if (newNode == NULL) {
        fprintf(stderr, "메모리 할당 오류\n");
        exit(EXIT_FAILURE);
    }

    newNode->data = data;
    newNode->prev = NULL;
    newNode->next = deque->front;

    if (isEmpty(deque)) {
        // 덱이 비어있을 경우 front와 rear를 새로 추가한 노드로 설정
        deque->front = newNode;
        deque->rear = newNode;
    } else {
        // 덱이 비어있지 않을 경우 기존 front의 prev를 새로 추가한 노드로 설정
        deque->front->prev = newNode;
        deque->front = newNode;
    }
}

// 덱의 뒤에 원소 추가 함수
void insertRear(Deque *deque, int data) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    if (newNode == NULL) {
        fprintf(stderr, "메모리 할당 오류\n");
        exit(EXIT_FAILURE);
    }

    newNode->data = data;
    newNode->prev = deque->rear;
    newNode->next = NULL;

    if (isEmpty(deque)) {
        // 덱이 비어있을 경우 front와 rear를 새로 추가한 노드로 설정
        deque->front = newNode;
        deque->rear = newNode;
    } else {
        // 덱이 비어있지 않을 경우 기존 rear의 next를 새로 추가한 노드로 설정
        deque->rear->next = newNode;
        deque->rear = newNode;
    }
}

// 덱의 앞에서 원소 삭제 함수
void deleteFront(Deque *deque) {
    if (isEmpty(deque)) {
        fprintf(stderr, "덱이 비어있습니다.\n");
        return;
    }

    Node *temp = deque->front;
    deque->front = deque->front->next;

    if (deque->front == NULL) {
        // 덱이 비어있게 되면 rear도 NULL로 설정
        deque->rear = NULL;
    } else {
        // 덱이 비어있지 않을 경우 새로운 front의 prev를 NULL로 설정
        deque->front->prev = NULL;
    }

    free(temp);
}

// 덱의 뒤에서 원소 삭제 함수
void deleteRear(Deque *deque) {
    if (isEmpty(deque)) {
        fprintf(stderr, "덱이 비어있습니다.\n");
        return;
    }

    Node *temp = deque->rear;
    deque->rear = deque->rear->prev;

    if (deque->rear == NULL) {
        // 덱이 비어있게 되면 front도 NULL로 설정
        deque->front = NULL;
    } else {
        // 덱이 비어있지 않을 경우 새로운 rear의 next를 NULL로 설정
        deque->rear->next = NULL;
    }

    free(temp);
}

// 덱의 전체 원소 출력 함수
void printDeque(Deque *deque) {
    if (isEmpty(deque)) {
        printf("덱이 비어있습니다.\n");
        return;
    }

    Node *current = deque->front;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

// 덱 메모리 해제 함수
void freeDeque(Deque *deque) {
    while (!isEmpty(deque)) {
        deleteFront(deque);
    }
}

int main() {
    Deque myDeque;
    initializeDeque(&myDeque);

    insertFront(&myDeque, 1);
    insertRear(&myDeque, 2);
    insertFront(&myDeque, 3);

    printf("덱의 원소: ");
    printDeque(&myDeque);

    deleteFront(&myDeque);

    printf("덱의 원소(앞에서 하나 삭제 후): ");
    printDeque(&myDeque);

    deleteRear(&myDeque);

    printf("덱의 원소(뒤에서 하나 삭제 후): ");
    printDeque(&myDeque);

    freeDeque(&myDeque);

    return 0;
}