Deque

덱 (Deque)

• “Double-Ended Queue”의 약자로, 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조이다
• 스택과 큐의 특징을 모두 가지고 있어 상황에 따라 두 가지 역할을 모두 수행할 수 있다
• 데이터의 선입선출(FIFO)과 후입선출(LIFO) 방식을 유연하게 선택하여 사용할 수 있다는 장점이 있다

주요 연산

• push_front: 덱의 맨 앞에 원소를 추가한다
• push_back: 덱의 맨 뒤에 원소를 추가한다
• pop_front: 덱의 맨 앞 원소를 제거하고 반환한다
• pop_back: 덱의 맨 뒤 원소를 제거하고 반환한다
• front / back: 덱의 맨 앞 또는 맨 뒤 원소를 제거하지 않고 확인한다

---

구현 방법

덱은 연결리스트나 배열을 이용하여 구현할 수 있다. 배열로 구현할 경우, 양방향 확장이 필요하므로 원형 배열(Circular Array) 방식을 사용하는 것이 일반적이다.

원형 배열을 이용한 구현

1. front와 rear라는 두 개의 포인터를 사용한다
2. 원소를 삽입할 때 포인터를 이동시킨 후 값을 저장한다
3. 배열의 인덱스가 범위를 벗어나면 반대편 끝으로 순환(Modular)하도록 처리한다

소스코드 (C언어)

#include <stdio.h>

typedef char bool;
const bool true = 1;
const bool false = 0;

#define MAX_IDX 100
int deque[MAX_IDX];
int front = 0;
int rear = 0;

bool isEmpty() {
    return (front == rear);
}

bool isFull() {
    return ((rear + 1) % MAX_IDX == front);
}

void push_front(int x) {
    if (isFull()) {
        printf("[Error] : Deque is full!\n");
        return;
    }
    // front를 반시계 방향으로 한 칸 이동 후 값 저장
    front = (front - 1 + MAX_IDX) % MAX_IDX;
    deque[front] = x;
}

void push_back(int x) {
    if (isFull()) {
        printf("[Error] : Deque is full!\n");
        return;
    }
    // 현재 rear 위치에 저장 후 시계 방향으로 이동
    deque[rear] = x;
    rear = (rear + 1) % MAX_IDX;
}

int pop_front() {
    if (isEmpty()) {
        printf("[Error] : Deque is empty!\n");
        return -1;
    }
    int res = deque[front];
    front = (front + 1) % MAX_IDX;
    return res;
}

int pop_back() {
    if (isEmpty()) {
        printf("[Error] : Deque is empty!\n");
        return -1;
    }
    rear = (rear - 1 + MAX_IDX) % MAX_IDX;
    return deque[rear];
}

int main() {
    push_back(10);
    push_front(20);
    push_back(30);

    printf("%d\n", pop_front()); // 20
    printf("%d\n", pop_back());  // 30
    return 0;
}

시간 복잡도

• 삽입/삭제: 양쪽 끝에서의 연산은 모두 $O(1)$의 시간 복잡도를 가진다
• 접근: 원형 배열 방식을 사용할 경우 인덱스를 통해 특정 원소에 $O(1)$로 접근 가능하다

활용 사례

• 데이터의 앞뒤에서 빈번한 삽입/삭제가 일어나는 경우
• 슬라이딩 윈도우(Sliding Window) 알고리즘에서 최댓값/최솟값을 찾을 때 유용하다
• 스케줄링 알고리즘(예: Work-stealing)에서 프로세스 관리에 사용된다