[자료구조] 덱(Dequeue, 데크)

덱(Dequeue)

---

덱이란?

• Dequeue : Double-ended Queue

  • 여기선 큐의 출력을 의미하는 Dequeue와 다른 의미로 사용됨

  • a.k.a 데크

• 전단, 후단 양쪽에서 push, pop이 가능함

• 스택과 큐의 장점을 모아둔 자료구조

덱의 종류

• 스크롤 : 입력이 한쪽 끝으로만 가능하도록 제한, 입력 제한 덱이라고도 함

• 셀프(Shelf) : 출력이 한쪽 끝으로만 가능하도록 제한, 출력 제한 덱이라고도 함

• 보통 양쪽에서 입력/출력을 모두 하는 경우는 거의 없어 스크롤이나 셀프를 사용한다

덱의 용도

• 스케줄링

• 우선순위 조절

덱의 동작

• 입력과 출력이 양방향에서 가능하고, 입력과 출력의 순서를 맘대로 정할 수 있음

• 추가 및 삭제의 실행속도는 O(1)

이중 연결 리스트로 덱 구현

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

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

// Dequeue 정의
typedef struct {
    Node* front;
    Node* rear;
} Dequeue;

// Dequeue 초기화
void initDequeue(Dequeue* q) {
    q->front = q->rear = NULL;
}

// 노드 생성 함수
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        exit(1); // 메모리 할당 실패
    }
    newNode->data = data;
    newNode->prev = newNode->next = NULL;
    return newNode;
}

// 앞쪽에 추가
void insertFront(Dequeue* q, int data) {
    Node* newNode = createNode(data);
    if (q->front == NULL) {
        q->front = q->rear = newNode;
    } else {
        newNode->next = q->front;
        q->front->prev = newNode;
        q->front = newNode;
    }
}

// 뒤쪽에 추가
void insertRear(Dequeue* q, int data) {
    Node* newNode = createNode(data);
    if (q->rear == NULL) {
        q->front = q->rear = newNode;
    } else {
        newNode->prev = q->rear;
        q->rear->next = newNode;
        q->rear = newNode;
    }
}

// 앞쪽에서 삭제
int deleteFront(Dequeue* q) {
    if (q->front == NULL) {
        printf("Dequeue is empty\n");
        return -1;
    }
    Node* temp = q->front;
    int data = temp->data;
    q->front = q->front->next;
    if (q->front == NULL) {
        q->rear = NULL;
    } else {
        q->front->prev = NULL;
    }
    free(temp);
    return data;
}

// 뒤쪽에서 삭제
int deleteRear(Dequeue* q) {
    if (q->rear == NULL) {
        printf("Dequeue is empty\n");
        return -1;
    }
    Node* temp = q->rear;
    int data = temp->data;
    q->rear = q->rear->prev;
    if (q->rear == NULL) {
        q->front = NULL;
    } else {
        q->rear->next = NULL;
    }
    free(temp);
    return data;
}

int main() {
    Dequeue q;
    initDequeue(&q);

    insertFront(&q, 10);
    insertRear(&q, 20);
    insertFront(&q, 5);
    insertRear(&q, 25);

    printf("Front: %d\n", deleteFront(&q));
    printf("Rear: %d\n", deleteRear(&q));

    return 0;
}