C 언어로 양방향 큐(Deque) 구현하기: 단계별 가이드

C 언어에서 양방향 큐(Deque)는 자료구조의 기초를 학습하는 데 있어 중요한 개념입니다. Deque는 양쪽 끝에서 데이터를 삽입하거나 삭제할 수 있는 자료구조로, 배열이나 연결 리스트를 활용하여 구현할 수 있습니다. 이 글에서는 Deque의 기본 개념부터 배열과 연결 리스트를 기반으로 구현하는 방법, 그리고 다양한 응용 예제까지 다룹니다. Deque를 이해하고 직접 구현해 보며, 자료구조와 알고리즘 설계 능력을 키워 보세요.

Deque란 무엇인가

Deque(Double-Ended Queue)는 양쪽 끝에서 데이터를 삽입하거나 삭제할 수 있는 선형 자료구조입니다.

Deque의 특징

Deque는 다음과 같은 특징을 가지고 있습니다.

양쪽 끝에서 삽입과 삭제가 모두 가능함.
큐(Queue)와 스택(Stack)의 기능을 모두 제공함.
FIFO(First In, First Out)와 LIFO(Last In, First Out)를 모두 지원할 수 있음.

Deque의 주요 종류

Deque는 다음과 같이 두 가지 주요 유형으로 나뉩니다.

입력 제한 Deque: 한쪽 끝에서만 삽입 가능, 양쪽 끝에서 삭제 가능.
출력 제한 Deque: 양쪽 끝에서 삽입 가능, 한쪽 끝에서만 삭제 가능.

Deque는 유연한 데이터 관리가 가능하여 다양한 문제 해결에 사용됩니다.

Deque의 주요 연산

Deque는 양쪽 끝에서 데이터를 처리할 수 있는 다양한 연산을 제공합니다. 아래는 Deque에서 수행 가능한 주요 연산들입니다.

삽입 연산

push_front()

Deque의 앞쪽에 데이터를 삽입합니다.

push_back()

Deque의 뒤쪽에 데이터를 삽입합니다.

삭제 연산

pop_front()

Deque의 앞쪽에서 데이터를 삭제합니다.

pop_back()

Deque의 뒤쪽에서 데이터를 삭제합니다.

조회 연산

front()

Deque의 앞쪽 데이터를 반환합니다.

back()

Deque의 뒤쪽 데이터를 반환합니다.

상태 확인 연산

is_empty()

Deque가 비어 있는지 확인합니다.

size()

Deque에 저장된 데이터의 개수를 반환합니다.

이러한 연산들을 활용하면 데이터를 유연하게 삽입, 삭제, 조회하며 효율적인 자료구조를 구성할 수 있습니다.

배열 기반 Deque 구현

배열을 사용하여 Deque를 구현하면 고정 크기의 메모리를 활용하여 효율적인 자료구조를 구성할 수 있습니다. 아래는 배열 기반 Deque의 구현 과정을 단계적으로 설명합니다.

1. 배열 기반 Deque의 구조

Deque는 고정 크기의 배열과 두 개의 인덱스(front와 rear)를 사용하여 데이터를 관리합니다.

front: Deque의 앞쪽 끝을 가리키는 인덱스.
rear: Deque의 뒤쪽 끝을 가리키는 인덱스.
배열은 순환(circular) 형태로 사용하여 공간 낭비를 최소화합니다.

2. 주요 연산의 구현

초기화

Deque를 초기화할 때는 배열 크기와 인덱스를 설정합니다.

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int front;
    int rear;
} Deque;

void initDeque(Deque *dq) {
    dq->front = 0;
    dq->rear = 0;
}

push_front()

배열의 앞쪽에 데이터를 삽입합니다.

void push_front(Deque *dq, int value) {
    dq->front = (dq->front - 1 + MAX_SIZE) % MAX_SIZE;
    dq->data[dq->front] = value;
}

push_back()

배열의 뒤쪽에 데이터를 삽입합니다.

void push_back(Deque *dq, int value) {
    dq->data[dq->rear] = value;
    dq->rear = (dq->rear + 1) % MAX_SIZE;
}

pop_front()

배열의 앞쪽 데이터를 삭제하고 반환합니다.

int pop_front(Deque *dq) {
    int value = dq->data[dq->front];
    dq->front = (dq->front + 1) % MAX_SIZE;
    return value;
}

pop_back()

배열의 뒤쪽 데이터를 삭제하고 반환합니다.

int pop_back(Deque *dq) {
    dq->rear = (dq->rear - 1 + MAX_SIZE) % MAX_SIZE;
    return dq->data[dq->rear];
}

3. 배열 기반 Deque의 작동 원리

Deque는 배열을 순환 방식으로 사용하여 인덱스가 배열 범위를 넘어갈 경우 처음으로 되돌아옵니다. 이를 통해 효율적인 공간 활용이 가능합니다.

4. 주의 사항

오버플로우 방지: 배열이 가득 찼는지 확인하는 조건을 추가해야 합니다.
언더플로우 방지: 데이터가 없는 상태에서 삭제 연산을 시도하지 않도록 주의해야 합니다.

이와 같은 배열 기반 구현은 고정된 크기의 데이터를 처리할 때 적합하며, 메모리 사용이 효율적입니다.

배열 기반 Deque의 장단점

배열 기반 Deque는 고정 크기의 배열과 순환 방식으로 효율적인 메모리 관리를 제공합니다. 그러나 한계도 존재합니다.

장점

1. 빠른 접근 속도

배열은 연속된 메모리 공간에 저장되므로 인덱스를 사용한 데이터 접근 속도가 빠릅니다.

2. 간단한 구현

배열 기반 Deque는 구조가 간단하며, 기본 배열 연산으로 구현이 가능합니다.

3. 메모리 관리 용이

배열은 정적으로 할당되므로 메모리 관리가 간단하며, 할당/해제의 부담이 적습니다.

단점

1. 고정된 크기

배열 크기가 고정되어 있어, Deque의 크기를 동적으로 확장하거나 축소할 수 없습니다.
데이터가 많아지면 오버플로우가 발생할 수 있습니다.

2. 메모리 낭비

배열 크기가 실제 데이터보다 크면 사용하지 않는 공간이 생겨 메모리가 낭비될 수 있습니다.

3. 크기 조정의 어려움

크기 제한을 극복하려면 새로운 배열을 생성하여 데이터를 복사해야 하므로, 추가적인 비용이 발생합니다.

배열 기반 Deque 사용 시 고려 사항

정해진 크기의 데이터를 다룰 경우 적합하지만, 데이터 크기가 동적으로 변하는 경우 연결 리스트 기반 Deque가 더 나은 선택일 수 있습니다.
효율적인 메모리 사용을 위해 적절한 배열 크기를 설계하는 것이 중요합니다.

이러한 장단점을 이해하면 특정 상황에서 배열 기반 Deque를 효과적으로 활용할 수 있습니다.

연결 리스트 기반 Deque 구현

연결 리스트를 기반으로 Deque를 구현하면 동적으로 크기를 조정할 수 있어 메모리 효율성과 유연성을 제공합니다. 아래는 연결 리스트를 활용한 Deque 구현 방법입니다.

1. 연결 리스트 기반 Deque의 구조

Deque는 노드(Node)와 포인터를 사용하여 데이터를 저장합니다.

Node 구조체: 데이터를 저장하며, 이전 노드와 다음 노드에 대한 포인터를 가집니다.
Deque 구조체: Deque의 시작(front)과 끝(rear)을 가리키는 포인터를 가집니다.

typedef struct Node {
    int data;
    struct Node *prev;
    struct Node *next;
} Node;

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

2. 주요 연산의 구현

초기화

Deque를 초기화할 때는 front와 rear를 NULL로 설정합니다.

void initDeque(Deque *dq) {
    dq->front = NULL;
    dq->rear = NULL;
}

push_front()

Deque의 앞쪽에 노드를 삽입합니다.

void push_front(Deque *dq, int value) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = value;
    newNode->prev = NULL;
    newNode->next = dq->front;

    if (dq->front != NULL) {
        dq->front->prev = newNode;
    }
    dq->front = newNode;

    if (dq->rear == NULL) {
        dq->rear = newNode;
    }
}

push_back()

Deque의 뒤쪽에 노드를 삽입합니다.

void push_back(Deque *dq, int value) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;
    newNode->prev = dq->rear;

    if (dq->rear != NULL) {
        dq->rear->next = newNode;
    }
    dq->rear = newNode;

    if (dq->front == NULL) {
        dq->front = newNode;
    }
}

pop_front()

Deque의 앞쪽 노드를 삭제하고 반환합니다.

int pop_front(Deque *dq) {
    if (dq->front == NULL) {
        printf("Deque is empty.\n");
        return -1;
    }
    Node *temp = dq->front;
    int value = temp->data;
    dq->front = temp->next;

    if (dq->front != NULL) {
        dq->front->prev = NULL;
    } else {
        dq->rear = NULL;
    }

    free(temp);
    return value;
}

pop_back()

Deque의 뒤쪽 노드를 삭제하고 반환합니다.

int pop_back(Deque *dq) {
    if (dq->rear == NULL) {
        printf("Deque is empty.\n");
        return -1;
    }
    Node *temp = dq->rear;
    int value = temp->data;
    dq->rear = temp->prev;

    if (dq->rear != NULL) {
        dq->rear->next = NULL;
    } else {
        dq->front = NULL;
    }

    free(temp);
    return value;
}

3. 연결 리스트 기반 Deque의 작동 원리

각 노드는 동적으로 생성되어 메모리를 효율적으로 사용합니다.
양방향 포인터를 활용하여 삽입과 삭제 연산을 O(1)의 시간 복잡도로 수행합니다.

4. 연결 리스트 기반 Deque 사용 시 주의 사항

메모리 관리: 동적으로 할당된 메모리를 적절히 해제해야 메모리 누수를 방지할 수 있습니다.
복잡성 증가: 배열 기반에 비해 구현이 다소 복잡할 수 있습니다.

연결 리스트 기반 Deque는 크기 제한 없이 데이터를 유연하게 처리해야 하는 상황에서 특히 유용합니다.

연결 리스트 기반 Deque의 장단점

연결 리스트 기반 Deque는 배열 기반 Deque와 비교하여 동적 크기 조정 및 효율적인 연산을 제공하지만, 구현의 복잡성과 메모리 관리 문제가 동반될 수 있습니다.

장점

1. 동적 크기 조정

데이터의 양에 따라 메모리를 동적으로 할당하므로, 크기의 제한이 없습니다.

2. 삽입 및 삭제 연산의 효율성

양쪽 끝에서 삽입 및 삭제 연산을 O(1)의 시간 복잡도로 수행할 수 있습니다.
배열과 달리, 기존 데이터를 이동할 필요가 없습니다.

3. 메모리 활용의 유연성

필요한 만큼만 메모리를 사용하므로 공간 낭비가 없습니다.

단점

1. 구현의 복잡성

연결 리스트 기반 Deque는 배열 기반에 비해 구조가 복잡하며, 구현 시 추가적인 고려 사항이 필요합니다.

2. 메모리 오버헤드

각 노드마다 추가적인 포인터(prev와 next)가 필요하므로, 메모리 사용량이 증가합니다.

3. 메모리 관리 필요

동적으로 할당된 노드를 적절히 해제하지 않으면 메모리 누수가 발생할 수 있습니다.

연결 리스트 기반 Deque의 사용 적합성

크기가 동적으로 변하는 데이터를 처리해야 하거나, 데이터 삽입과 삭제가 빈번히 발생하는 경우에 적합합니다.
반면, 메모리 사용이 제한적이거나 단순한 구조가 필요한 경우에는 배열 기반 Deque가 더 나을 수 있습니다.

연결 리스트 기반 Deque의 장단점을 이해하면, 특정 응용 상황에 맞는 최적의 자료구조를 선택할 수 있습니다.

Deque 구현 코드 설명

Deque를 배열 기반과 연결 리스트 기반으로 구현하는 코드를 비교하며, 각 구현의 작동 원리를 상세히 설명합니다.

배열 기반 Deque 코드

아래는 배열 기반 Deque의 구현 코드 예제입니다.

#include <stdio.h>
#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int front;
    int rear;
} Deque;

void initDeque(Deque *dq) {
    dq->front = 0;
    dq->rear = 0;
}

void push_front(Deque *dq, int value) {
    dq->front = (dq->front - 1 + MAX_SIZE) % MAX_SIZE;
    dq->data[dq->front] = value;
}

void push_back(Deque *dq, int value) {
    dq->data[dq->rear] = value;
    dq->rear = (dq->rear + 1) % MAX_SIZE;
}

int pop_front(Deque *dq) {
    if (dq->front == dq->rear) {
        printf("Deque is empty.\n");
        return -1;
    }
    int value = dq->data[dq->front];
    dq->front = (dq->front + 1) % MAX_SIZE;
    return value;
}

int pop_back(Deque *dq) {
    if (dq->front == dq->rear) {
        printf("Deque is empty.\n");
        return -1;
    }
    dq->rear = (dq->rear - 1 + MAX_SIZE) % MAX_SIZE;
    return dq->data[dq->rear];
}

작동 원리

순환 배열: 배열의 처음과 끝이 연결되어 있는 것처럼 동작합니다.
인덱스 관리: front와 rear를 순환적으로 증가 또는 감소시켜 데이터 삽입 및 삭제를 수행합니다.

제약 사항

배열이 가득 차거나 비었을 때를 확인하는 조건이 필요합니다.
배열 크기가 고정되어 동적 크기 조정이 어렵습니다.

연결 리스트 기반 Deque 코드

아래는 연결 리스트 기반 Deque의 구현 코드 예제입니다.

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

typedef struct Node {
    int data;
    struct Node *prev;
    struct Node *next;
} Node;

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

void initDeque(Deque *dq) {
    dq->front = NULL;
    dq->rear = NULL;
}

void push_front(Deque *dq, int value) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = value;
    newNode->prev = NULL;
    newNode->next = dq->front;

    if (dq->front != NULL) {
        dq->front->prev = newNode;
    }
    dq->front = newNode;

    if (dq->rear == NULL) {
        dq->rear = newNode;
    }
}

void push_back(Deque *dq, int value) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;
    newNode->prev = dq->rear;

    if (dq->rear != NULL) {
        dq->rear->next = newNode;
    }
    dq->rear = newNode;

    if (dq->front == NULL) {
        dq->front = newNode;
    }
}

int pop_front(Deque *dq) {
    if (dq->front == NULL) {
        printf("Deque is empty.\n");
        return -1;
    }
    Node *temp = dq->front;
    int value = temp->data;
    dq->front = temp->next;

    if (dq->front != NULL) {
        dq->front->prev = NULL;
    } else {
        dq->rear = NULL;
    }

    free(temp);
    return value;
}

int pop_back(Deque *dq) {
    if (dq->rear == NULL) {
        printf("Deque is empty.\n");
        return -1;
    }
    Node *temp = dq->rear;
    int value = temp->data;
    dq->rear = temp->prev;

    if (dq->rear != NULL) {
        dq->rear->next = NULL;
    } else {
        dq->front = NULL;
    }

    free(temp);
    return value;
}

작동 원리

노드 동적 생성: 필요한 데이터를 저장할 때마다 새로운 노드를 동적으로 생성합니다.
양방향 연결: 각 노드는 이전 노드와 다음 노드의 포인터를 가지며, Deque의 양쪽 끝에서 삽입 및 삭제가 용이합니다.

제약 사항

구현이 배열보다 복잡하며, 메모리 관리가 필요합니다.
각 노드마다 추가적인 메모리 공간(prev, next)이 필요합니다.

배열 기반과 연결 리스트 기반의 비교

기준	배열 기반 Deque	연결 리스트 기반 Deque
메모리 관리	정적 크기, 고정 배열	동적 크기, 메모리 효율적 사용
구현 복잡성	상대적으로 단순	상대적으로 복잡
삽입/삭제 성능	O(1) (끝에서만)	O(1) (양쪽 끝 모두)
메모리 오버헤드	낮음	높음 (추가 포인터 공간 필요)

두 구현 방법의 작동 방식을 비교하고, 상황에 따라 적합한 방식을 선택하는 것이 중요합니다.

Deque 활용 예제

Deque는 양방향에서 데이터를 처리할 수 있는 특성 덕분에 다양한 응용 분야에서 활용됩니다. 아래는 Deque를 사용한 실제 사례와 코드 예제입니다.

1. 회문 검사

Deque는 문자열이 회문인지 검사하는 데 유용합니다. 문자열의 양쪽 끝을 비교하며 검사를 진행할 수 있습니다.

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

#define MAX_SIZE 100

typedef struct {
    char data[MAX_SIZE];
    int front;
    int rear;
} Deque;

void initDeque(Deque *dq) {
    dq->front = 0;
    dq->rear = 0;
}

void push_back(Deque *dq, char value) {
    dq->data[dq->rear] = value;
    dq->rear = (dq->rear + 1) % MAX_SIZE;
}

char pop_front(Deque *dq) {
    char value = dq->data[dq->front];
    dq->front = (dq->front + 1) % MAX_SIZE;
    return value;
}

char pop_back(Deque *dq) {
    dq->rear = (dq->rear - 1 + MAX_SIZE) % MAX_SIZE;
    return dq->data[dq->rear];
}

bool isPalindrome(char *str) {
    Deque dq;
    initDeque(&dq);
    int length = strlen(str);

    for (int i = 0; i < length; i++) {
        if (str[i] != ' ') { // 공백은 무시
            push_back(&dq, str[i]);
        }
    }

    while (dq.front != dq.rear) {
        if (pop_front(&dq) != pop_back(&dq)) {
            return false;
        }
    }
    return true;
}

int main() {
    char str[] = "racecar";
    if (isPalindrome(str)) {
        printf("The string '%s' is a palindrome.\n", str);
    } else {
        printf("The string '%s' is not a palindrome.\n", str);
    }
    return 0;
}

2. 슬라이딩 윈도우 문제 해결

Deque는 슬라이딩 윈도우 기법에서 최대값 또는 최소값을 효율적으로 찾는 데 사용할 수 있습니다.
예: 배열에서 크기 k의 윈도우 내 최대값 찾기.

#include <stdio.h>

void maxSlidingWindow(int arr[], int n, int k) {
    Deque dq;
    initDeque(&dq);

    for (int i = 0; i < n; i++) {
        // 윈도우 범위를 벗어난 요소 제거
        if (dq.front != dq.rear && dq.front == (i - k)) {
            pop_front(&dq);
        }

        // 새 요소보다 작거나 같은 값을 가진 요소 제거
        while (dq.front != dq.rear && arr[dq.data[dq.rear - 1]] <= arr[i]) {
            pop_back(&dq);
        }

        // 현재 인덱스 추가
        push_back(&dq, i);

        // 첫 윈도우 이후부터 최대값 출력
        if (i >= k - 1) {
            printf("%d ", arr[dq.data[dq.front]]);
        }
    }
}

int main() {
    int arr[] = {1, 3, -1, -3, 5, 3, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;

    printf("Maximum values in each sliding window: ");
    maxSlidingWindow(arr, n, k);
    return 0;
}

3. BFS 알고리즘에서의 큐 대체

Deque는 BFS(너비 우선 탐색)에서 큐를 대체해, 양방향으로 탐색이 필요한 경우 유용하게 사용됩니다.

4. 캐시 구현

Deque를 활용하여 LRU(Least Recently Used) 캐시를 구현할 수 있습니다.

최근 사용된 데이터는 Deque의 뒤에 저장하고, 오래된 데이터는 앞쪽에서 제거합니다.

Deque는 이러한 문제들 외에도 스택과 큐의 특성을 모두 활용해야 하는 문제에서 자주 사용됩니다. Deque의 유연한 연산과 효율성을 통해 문제를 효과적으로 해결할 수 있습니다.

요약

Deque는 양쪽 끝에서 삽입과 삭제가 가능한 자료구조로, 배열과 연결 리스트를 기반으로 구현할 수 있습니다. 배열 기반 Deque는 간단한 구조와 빠른 접근 속도를 제공하지만, 크기가 고정적입니다. 반면, 연결 리스트 기반 Deque는 동적으로 크기를 조정할 수 있어 유연성이 높지만, 메모리 오버헤드가 발생합니다.

Deque는 회문 검사, 슬라이딩 윈도우, BFS, 캐시 구현 등 다양한 응용 사례에서 사용됩니다. 이를 통해 효율적인 자료구조 설계와 문제 해결 능력을 배울 수 있습니다.