덱,디큐(Deque)

덱(Deque)이란?

양쪽 끝에서 삽입과 삭제가 모두 가능한 선형 자료구조
덱은 스택과 큐의 장점을 모두 갖추고 있어, 양방향에서 삽입과 삭제가 필요한 상황에 유용하게 사용 가능

특징

1. 양방향 접근 가능: 앞과 뒤에서 삽입과 삭제가 가능
2. 큐와 스택의 기능 결합: 스택처럼 후입선출(LIFO) 구조와 큐처럼 선입선출(FIFO) 구조를 모두 지원
3. 유연한 연산: 중간 접근은 불가능하지만, 양쪽 끝에서의 삽입 및 삭제가 빠르게 수행
4. 시간 복잡도: 덱의 삽입과 삭제 연산은 O(1)의 시간 복잡도를 가지며, 양쪽 끝에서의 접근이 매우 빠름

장점

1. 양방향 데이터 처리: 앞과 뒤 모두에서 삽입과 삭제가 가능하여, 양쪽에서 데이터를 효율적으로 관리
2. 유연한 데이터 구조: 덱을 사용하여 스택과 큐의 모든 연산을 구현할 수 있습니다.
3. 사용 용이성: 다양한 경우에 덱의 특성을 활용하여 복잡한 문제를 쉽게 해결

단점

1. 중간 접근 불가: 덱은 중간에 있는 요소에 접근하거나 수정할 수 없음
2. 메모리 사용량 증가: 각 요소마다 앞뒤를 가리키는 포인터를 추가로 저장해야 하므로 메모리 사용량이 증가할 수 있음

사용 예시

• 양방향 탐색 알고리즘: 너비 우선 탐색(BFS), 최단 경로 탐색 등에서 양쪽 끝을 자유롭게 탐색
• 슬라이딩 윈도우 문제: 슬라이딩 윈도우를 구현할 때, 앞쪽과 뒤쪽 모두에서 효율적으로 데이터의 추가 및 삭제가 가능
• 캐시 구현 (LRU Cache): LRU(Least Recently Used) 알고리즘에서, 최근에 사용된 항목을 앞이나 뒤로 이동시키기 위해 사용
• 편집기 기능 구현: 텍스트 편집기에서 커서를 이동하거나 특정 위치에 텍스트를 추가/삭제하는 기능을 구현
• 펠린드롬 검사: 문자열의 앞과 뒤에서 동시에 접근하여 대칭을 검사

주요 연산

• push_front: 덱의 앞에 새로운 요소를 추가
• push_back: 덱의 뒤에 새로운 요소를 추가
• pop_front: 덱의 앞에 있는 요소를 제거하고 반환
• pop_back: 덱의 뒤에 있는 요소를 제거하고 반환
• front: 덱의 앞에 있는 요소를 반환 (제거하지 않음)
• back: 덱의 뒤에 있는 요소를 반환 (제거하지 않음)
• isEmpty: 덱이 비어 있는지 확인
• size: 덱에 있는 요소의 개수를 반환

구현 방식

배열 기반 덱

고정 크기의 덱을 사용하며, 앞과 뒤의 인덱스를 조정하여 요소를 삽입/삭제
메모리 사용 효율이 좋지만, 크기 변경이 어렵고 삽입/삭제 시 배열의 이동이 필요할 수 있음

#include <iostream>
using namespace std;

#define MAX 10

class Deque {
    int arr[MAX];
    int front, rear, size;

public:
    Deque() {
        front = -1;
        rear = -1;
        size = 0;
    }

    // 덱이 비어 있는지 확인
    bool isEmpty() {
        return size == 0;
    }

    // 덱이 가득 찼는지 확인
    bool isFull() {
        return size == MAX;
    }

    // 덱의 앞에 요소 삽입
    void push_front(int value) {
        if (isFull()) {
            cout << "Deque is Full\n";
            return;
        }
        if (isEmpty()) {  // 덱이 비어있을 때
            front = rear = 0;
        } else if (front == 0) {
            front = MAX - 1;
        } else {
            front--;
        }
        arr[front] = value;
        size++;
        cout << value << " pushed at front\n";
    }

    // 덱의 뒤에 요소 삽입
    void push_back(int value) {
        if (isFull()) {
            cout << "Deque is Full\n";
            return;
        }
        if (isEmpty()) {  // 덱이 비어있을 때
            front = rear = 0;
        } else if (rear == MAX - 1) {
            rear = 0;
        } else {
            rear++;
        }
        arr[rear] = value;
        size++;
        cout << value << " pushed at back\n";
    }

    // 덱의 앞 요소 제거
    void pop_front() {
        if (isEmpty()) {
            cout << "Deque is Empty\n";
            return;
        }
        cout << arr[front] << " popped from front\n";
        if (front == rear) {  // 덱이 비면 초기화
            front = rear = -1;
        } else if (front == MAX - 1) {
            front = 0;
        } else {
            front++;
        }
        size--;
    }

    // 덱의 뒤 요소 제거
    void pop_back() {
        if (isEmpty()) {
            cout << "Deque is Empty\n";
            return;
        }
        cout << arr[rear] << " popped from back\n";
        if (front == rear) {  // 덱이 비면 초기화
            front = rear = -1;
        } else if (rear == 0) {
            rear = MAX - 1;
        } else {
            rear--;
        }
        size--;
    }
};

int main() {
    Deque dq;
    dq.push_back(10);
    dq.push_front(20);
    dq.pop_front();  // 20 popped
    dq.pop_back();   // 10 popped
    return 0;
}

이중 연결 리스트 기반 덱

각 노드가 앞과 뒤의 노드를 가리키는 포인터를 갖고 있으며, 동적으로 크기를 조절할 수 있음
메모리 사용량이 증가하지만, 삽입과 삭제 연산이 빠르게 수행됨

라이브러리

#include <iostream>
#include <deque>
using namespace std;

int main() {
    deque<int> dq;

    // 요소 추가
    dq.push_back(10);  // 뒤에 10 추가
    dq.push_front(20); // 앞에 20 추가
    dq.push_back(30);  // 뒤에 30 추가

    cout << "덱의 맨 앞 요소: " << dq.front() << endl;  // 20
    cout << "덱의 맨 뒤 요소: " << dq.back() << endl;   // 30

    // 양쪽 끝 요소 제거
    dq.pop_front();  // 20 제거
    dq.pop_back();   // 30 제거
    cout << "덱의 맨 앞 요소 (제거 후): " << dq.front() << endl;  // 10

    return 0;
}

정리 : 덱은 큐와 스택을 대체하여 유연한 데이터 구조를 제공