샷건치며 배우는 자료구조 with C++, 7화

덱(Deque)에 대해 알아봅시다.

읽어주세요

자료구조를 배우기 위해 위대한 항로(?)를 넘어 여기까지 오신 분들 환영합니다. 본 게시글은 자료구조를 공부하면서 복습 겸 정리하기 위해 작성하였습니다. 개인적으로 강좌 형식 및 장난을 섞어가며 작성하는 걸 좋아하기 때문에 진지한 게시글을 원하신다면 뒤로 가기를 눌러주세요.

C++ 언어를 기반으로 하고 있습니다. 다른 프로그래밍 언어를 사용 중이신 경우 개념(이론)을 배우는 데 큰 문제는 없지만, 실제 코드로 구현할 땐 생각보다 차이가 있을 수 있습니다.

업데이트

1. C 언어 구현 내용 제거
   • 게시글의 내용이 너무 복잡해져 제거하였습니다.

게시글 개선을 위해 임시 숨김 처리

덱

Deque^{Double-ended Queue}는 덱이라 발음합니다. 유희왕에 나오는 그 덱이 아니구요...

그런데, 왜 '덱'이라고 발음할까요? 공식적인 내용은 발견하지 못했지만 Deque의 올바른(?) 영어 발음은 '디큐'에 가깝습니다. 하지만, 디큐라고 발음하면 데이터를 제거하는 Dequeue와 혼동될 가능성이 있기 때문에 '덱'이라 발음하는 거라 생각합니다.

덱은 양쪽 끝에서 데이터의 삽입과 제거 모두 가능한 큐의 일종입니다. 일반적으로 스택과 큐의 기능을 모두 포함할 수 있어 매우 유연한 자료구조라 할 수 있습니다.

특징

• 양방향

  ---

  덱은 앞(front)과 뒤(back)에서 데이터를 추가하거나 제거할 수 있습니다.

덱의 양방향은 대표적인 특징이라 할 수 있습니다.

한쪽 끝만 사용하는 스택과 앞에서 데이터를 제거하고 뒤에서 삽입하는 큐에 비하면 매우 유연한 구조를 갖고 있습니다. 그리고 양쪽 끝에서 데이터를 추가하고 제거하는 작업은 \(O(1)\)으로 매우 빠릅니다.

장단점

• 장점

  ---

  1. 양방향

     앞과 뒤에서 데이터를 추가하고 제거할 수 있어 스택이나 큐처럼 활용할 수 있습니다.

• 단점

  ---

  1. 중간 데이터 접근 불가

     스택처럼 중간에 있는 데이터에 접근할 수 없습니다. 큐는 앞에만 접근할 수 있습니다.

작동 원리

덱은 배열 또는 연결 리스트를 기반으로 구현할 수 있습니다. 우리는 아직 연결 리스트를 배우지 않았기 때문에 배열 기반으로 설명하고 배웁니다.

덱은 원형 배열을 활용하여 양쪽 끝에서 데이터를 추가하고 제거할 수 있도록 합니다.

Deque

push_front와 pop_front는 맨 앞에 요소(데이터)를 추가하고 제거하며, push_back과 pop_back은 맨 뒤에 요소(데이터)를 추가하고 제거합니다.

원형 배열 기반의 덱은 front와 rear라는 두 개의 인덱스 변수가 있습니다. push_front를 사용하면 front를 한 칸 앞으로 이동시킨 후 데이터를 추가합니다. push_back은 rear를 한 칸 뒤로 이동시킨 후 데이터를 추가하죠. pop_front와 pop_back은 이와 반대로 동작합니다. front와 rear가 가리키는 데이터를 제거하고 뒤 또는 앞으로 이동합니다.

• 통크

  ---

  

• 통크 과자

  ---

  

덱은 과자 '통크'를 떠올려보세요. 드셔본 적 없다구요? 흠... 그러면 양쪽 구멍이 뚫린 파이프(배관)를 상상해보세요.

이 파이프 양쪽 끝에 물건을 넣거나 뺄 수 있습니다. 이 파이프에 물건들로 꽉 차면 더 이상 넣을 수 없죠. 물건을 꺼내면 넣을 공간이 다시 생깁니다. 덱의 개념도 이와 같습니다.

덱은 스택과 큐의 한계를 극복하기 위해 나타났습니다. 단방향 큐는 앞에서 데이터를 제거하고, 뒤에서 데이터를 추가합니다. 스택은 한 쪽에서만 이루어지죠. 굳이 이러지 말고 양쪽 방향에서 데이터를 추가하고 제거할 수 있으면 편하죠. 그래서 C++ STL의 스택과 큐는 기본적으로 std::deque를 기반으로 하고 있습니다.

기본 구조

constexpr auto MAX_SIZE = 10;

//! @brief Deque
class Deque {
private:
    int m_Data[MAX_SIZE];
    int m_Front;
    int m_Rear;
    int m_Size;

public:
    //! @brief 기본 생성자
    Deque() noexcept {
        m_Front = 0;
        m_Rear = -1;
        m_Size = 0;
    }
};

int m_Data[MAX_SIZE]는 덱의 데이터를 저장하는 배열입니다. MAX_SIZE를 통해 고정된 크기를 갖습니다.

int m_Front는 덱의 맨 앞을 가리키는 인덱스 변수입니다. 새로운 데이터가 추가되거나 제거될 때 이 값이 변경됩니다.

int m_Rear는 덱의 맨 끝을 가리키는 인덱스 변수입니다. 새로운 데이터가 추가되거나 제거될 때 이 값이 변경됩니다.

int m_Size는 덱에 현재 저장된 데이터의 수를 나타냅니다. 데이터가 추가되면 증가하고, 제거되면 감소합니다. 이 변수는 IsFull과 IsEmpty 함수를 구현할 때 사용됩니다.

생성자는 덱의 멤버 변수를 초기화합니다. m_Front는 0으로, m_Rear는 -1로 설정합니다. m_Rear를 -1로 설정하는 이유는 PushBack 연산을 수행할 때 첫 데이터 추가 시 자연스럽게 0부터 시작하게 하기 위함입니다. 지금은 이렇게 이해하고 아래에서 자세히 알아봅시다.

기본적으로 큐의 기본 구조와 같으며, int m_Size가 추가된 것이라 보시면 됩니다.

주요 연산

덱의 주요 연산은 데이터를 추가하는 push와 데이터를 제거하는 pop입니다. 나머지 연산들은 덱의 보조적인 역할을 합니다.

큐와 유사한 구조를 갖기 때문에 생각보다 구현은 어렵지 않은 편입니다.

push_front

push_front 연산은 덱의 앞(front)에 데이터를 추가합니다. 데이터를 추가하기 전에 is_full 함수를 호출하여 덱이 가득 차 있는 지 확인해야 합니다. 그리고 front의 값을 한 칸 이동한 후 데이터를 추가합니다.

반시계 방향으로 추가된다

push_front 연산에서 헷갈릴 수 있는 사항이 하나 있습니다. 덱의 앞 데이터 추가 연산은 반시계 방향으로 데이터가 추가됩니다. 이렇게 말하니 더 헷갈리죠? 스택의 반대 방향처럼 데이터가 추가된다고 보시면 됩니다.

classstd::deque

constexpr auto MAX_SIZE = 10;

//! @brief Deque
class Deque {
private:
    int m_Data[MAX_SIZE];
    int m_Front;
    int m_Rear;
    int m_Size;

public:
    //! @brief 기본 생성자
    Deque() noexcept {
        m_Front = 0;
        m_Rear = -1;
        m_Size = 0;
    }

    //! @brief 앞에 데이터를 추가하는 메서드
    //! @param value 값
    void PushFront(int value) noexcept {
        // (1) 가득 찼는 지 확인
        if (IsFull()) { return; }

        // (2) front 값 조절
        m_Front = (m_Front - 1 + MAX_SIZE) % MAX_SIZE;

        // (3) 동기화
        if (m_Size == 0) {
            m_Rear = m_Front;
        }

        // (4) 데이터 추가
        m_Data[m_Front] = value;

        // (5) 크기 증가
        m_Size += 1;
    }
};

1. 가득 찼는 지 확인

   데이터를 추가할 수 있는 지 확인을 먼저해야 합니다.

2. front 값 조절

   앞에 데이터를 추가한다는 건 front가 가리키는 위치보다 한 칸 앞에 데이터를 추가한다는 의미입니다. 배열의 인덱스는 좌에서 우로 증가하죠? 한 칸 앞에 데이터를 추가하려면 인덱스를 감소해야 합니다. 그래서 front 값에 -1을 하는 겁니다. 하지만, -1 연산을 수행하면 음수가 되기 때문에 양수로 전환하기 위해 MAX_SIZE의 값을 더합니다. 더하면 MAX_SIZE 값을 초과할 수 있기 때문에 모듈러 연산을 수행하여 MAX_SIZE 범위 안의 값을 갖도록 합니다.

3. 데이터 추가

   연산 후 취득한 front 값을 통해 데이터를 추가합니다.

4. 동기화

   보통 front와 rear는 서로 독립적으로 움직입니다. 하지만, 덱이 처음 비어 있다가 데이터가 추가될 때는 front와 rear의 값을 서로 동기화해줘야 합니다.

   덱은 양방향 접근이 가능하기 때문에 초기 데이터 추가 시 값을 동기화시켜야 합니다. 왜냐하면 push_front 후 pop_back을 하거나, push_back 후 pop_front 연산을 수행할 때 front와 rear가 첫 요소를 가리켜야 하기 때문입니다.

5. 크기 증가

   데이터를 추가하였으니 값을 증가시킵니다.

#include <deque>        // Required

int main() {
    // (1) Deque 선언
    std::deque<int> dq;

    // (2) 데이터 추가
    de.push_front(1);

    return 0;
}

C++은 std::deque라는 Deque 컨테이너를 지원하고 있습니다.

push_front 메서드를 통해 데이터를 추가할 수 있습니다.

pop_front

pop_front 연산은 덱의 앞(front)에서 데이터를 제거합니다. is_empty 함수를 호출해 덱이 비어 있으면 제거 연산을 수행하지 않습니다.

원형 배열을 기반으로 하기 때문에 front를 한 칸 앞으로(우측) 이동하면 제거 효과를 나타낼 수 있습니다.

push_front의 연산과는 다르게 -1을 하지 않고 +1을 하고, size의 값을 1 감소시킵니다.

classstd::deque

class Deque {
private:
    // ...

public:
    // ...

    //! @brief 앞 데이터를 제거하는 메서드
    //! @return 데이터
    int PopFront() noexcept {
        // (1) 비어 있는 지 확인
        if (IsEmpty()) { return -1; }

        // (2) 제거 전, 데이터 백업
        int value = m_Data[m_Front];

        // (3) front 값 조절
        m_Front = (m_Front + 1) % MAX_SIZE;

        // (4) 크기 감소
        m_Size -= 1;

        // (5) 동기화
        if (m_Size == 0) {
            m_Front = 0;
            m_Rear = -1;
        }

        // (6) 반환
        return value;
    }
};

1. 비어 있는 지 확인

   데이터를 제거할 수 있는 지 확인을 먼저해야 합니다.

2. 데이터 백업

   front 값이 변경되면 이전 데이터 요소에 접근할 수 없으니 미리 값을 백업합니다.

3. front 값 조절

   앞 데이터를 제거한다는 건 front가 가리키는 위치의 데이터를 제거한다는 의미입니다. push_front와 다르게 +1을 하는 이유는 그 다음 데이터를 가리켜야 하기 때문입니다. +1을 수행할 때 MAX_SIZE를 초과할 수 있으니 모듈러 연산을 통해 MAX_SIZE 범위 안의 값을 갖도록 합니다.

4. 크기 감소

   데이터를 제거하였으니 값을 감소시킵니다.

5. 동기화

   꼬임을 방지하기 위해 덱이 비었을 때 다시 초기값으로 되돌립니다.

6. 반환

   백업한 값을 반환합니다.

// ...
int main() {
    // ...

    // 데이터 제거
    dq.pop_front();

    return 0;
}

pop_front 메서드를 호출하여 데이터를 제거할 수 있습니다. 제거하기 전, 데이터를 확인하려면 front 메서드를 호출합니다.

push_back

push_back 연산은 덱의 뒤(rear)에 데이터를 추가합니다. 데이터를 추가하기 전에 is_full 함수를 호출하여 덱이 가득 차 있는 지 확인해야 합니다. 그리고 rear의 값을 한 칸 이동한 후 데이터를 추가합니다.

시계 방향으로 추가된다

push_back 연산에서 헷갈릴 수 있는 사항이 하나 있습니다. 덱의 뒤 데이터 추가 연산은 시계 방향으로 데이터가 추가됩니다. 이렇게 말하니 더 헷갈리죠? 스택처럼 데이터가 추가된다고 보시면 됩니다.

classstd::deque

constexpr auto MAX_SIZE = 10;

//! @brief Deque
class Deque {
private:
    // ...

public:
    // ...

    //! @brief 뒤에 데이터를 추가하는 메서드
    //! @param value 값
    void PushBack(int value) noexcept {
        // (1) 가득 찼는 지 확인
        if (IsFull()) { return; }

        // (2) rear 값 조절
        m_Rear = (m_Rear + 1) % MAX_SIZE;

        // (3) 동기화
        if (m_Size == 0) {
            m_Front = m_Rear;
        }

        // (4) 데이터 추가
        m_Data[m_Rear] = value;

        // (5) 크기 증가
        m_Size += 1;
    }
};

1. 가득 찼는 지 확인

   데이터를 추가할 수 있는 지 확인을 먼저해야 합니다.

2. rear 값 조절

   뒤에 데이터를 추가한다는 건 rear가 가리키는 위치보다 한 칸 뒤에 데이터를 추가한다는 의미입니다. 배열의 인덱스는 좌에서 우로 증가하죠? 한 칸 뒤에 데이터를 추가하려면 인덱스를 증가해야 합니다. 그래서 rear 값에 +1을 하는 겁니다. 하지만, +1 연산을 수행하다보면 MAX_SIZE 값을 초과할 수 있기 때문에 모듈러 연산을 수행하여 MAX_SIZE 범위 안의 값을 갖도록 합니다.

3. 데이터 추가

   연산 후 취득한 rear 값을 통해 데이터를 추가합니다.

4. 동기화

   보통 front와 rear는 서로 독립적으로 움직입니다. 하지만, 덱이 처음 비어 있다가 데이터가 추가될 때는 front와 rear의 값을 서로 동기화해줘야 합니다.

   덱은 양방향 접근이 가능하기 때문에 초기 데이터 추가 시 값을 동기화시켜야 합니다. 왜냐하면 push_front 후 pop_back을 하거나, push_back 후 pop_front 연산을 수행할 때 front와 rear가 첫 요소를 가리켜야 하기 때문입니다.

5. 크기 증가

   데이터를 추가하였으니 값을 증가시킵니다.

#include <deque>

int main() {
    // (1) Deque 선언
    std::deque<int> dq;

    // (2) 데이터 추가
    de.push_back(1);

    return 0;
}

push_back 메서드를 통해 데이터를 추가할 수 있습니다.

pop_back

pop_back 연산은 덱의 뒤(rear)에서 데이터를 제거합니다. is_empty 함수를 호출해 덱이 비어 있으면 제거 연산을 수행하지 않습니다.

원형 배열을 기반으로 하기 때문에 rear를 한 칸 앞으로(좌측) 이동하면 제거 효과를 나타낼 수 있습니다.

push_back의 연산과는 다르게 +1을 하지 않고 -1을 하고, size의 값을 1 감소시킵니다.

classstd::deque

class Deque {
private:
    // ...

public:
    // ...

    //! @brief 뒤 데이터를 제거하는 메서드
    //! @return 데이터
    int PopBack() noexcept {
        // (1) 비어 있는 지 확인
        if (IsEmpty()) { return -1; }

        // (2) 제거 전, 데이터 백업
        int value = m_Data[m_Rear];

        // (3) rear 값 조절
        m_Rear = (m_Rear - 1 + MAX_SIZE) % MAX_SIZE;

        // (4) 크기 감소
        m_Size -= 1;

        // (5) 동기화
        if (m_Size == 0) {
            m_Front = 0;
            m_Rear = -1;
        }

        // (6) 반환
        return value;
    }
};

1. 비어 있는 지 확인

데이터를 제거할 수 있는 지 확인을 먼저해야 합니다.

1. 데이터 백업

   rear 값이 변경되면 이전 데이터 요소에 접근할 수 없으니 미리 값을 백업합니다.

2. rear 값 조절

   뒤 데이터를 제거한다는 건 rear가 가리키는 위치의 데이터를 제거한다는 의미입니다. push_back와 다르게 -1을 하는 이유는 그 다음 데이터를 가리켜야 하기 때문입니다. -1을 수행할 때 음수가 될 수 있으니 MAX_SIZE를 더합니다. 더한 후 MAX_SIZE를 초과할 수 있으니 모듈러 연산을 통해 MAX_SIZE 범위 안의 값을 갖도록 합니다.

3. 크기 감소

   데이터를 제거하였으니 값을 감소시킵니다.

4. 동기화

   꼬임을 방지하기 위해 초기값으로 되돌립니다.

5. 반환

   백업한 값을 반환합니다.

// ...
int main() {
    // ...

    // 데이터 제거
    dq.pop_back();

    return 0;
}

pop_back 메서드를 호출하여 데이터를 제거할 수 있습니다. 제거하기 전, 데이터를 확인하려면 back 메서드를 호출합니다.

front, back

front와 back은 앞과 뒤에 있는 데이터를 반환합니다. is_empty 함수를 선호출하여 비어 있는 상태인지 확인합니다. 비어있지 않다면 front 또는 rear에 있는 데이터를 반환하도록 합니다.

classstd::deque

class Deque {
private:
    // ...

public:
    // ...

    //! @brief 앞 데이터 취득 함수
    //! @return 데이터
    int Front() noexcept {
        return (IsEmpty()) ? -1 : m_Data[m_Front];
    }

    //! @brief 뒤 데이터 취득 함수
    //! @return 데이터
    int Back() noexcept {
        return (IsEmpty()) ? -1 : m_Data[m_Rear];
    }
};

// ...

int main() {
    // ...

    int val1 = dq.front();
    int val2 = dq.back();

    return 0;
}

is_full, is_empty

is_full은 덱이 데이터로 가득 차 있는 지 확인하고, is_empty는 비어 있는 지 확인합니다.

classstd::deque

class Deque {
    // ...

    //! @brief 가득 차 있는 지 확인하는 함수
    //! @return Boolean
    bool IsFull() noexcept {
        return m_Size == MAX_SIZE;
    }

    //! @brief 비어 있는 지 확인하는 함수
    //! @return Boolean
    bool IsEmpty() noexcept {
        return m_Size == 0;
    }
};

// ...
int main() {
    // ...

    bool isEmpty = dq.empty();

    return 0;
}

std::deque는 동적으로 관리되기 때문에 is_full과 같은 메서드가 존재하지 않습니다. 대신에 empty 메서드로 덱이 비어 있는 지를 확인할 수 있습니다.

정리

Deque(덱)은 원형 배열 또는 연결 리스트를 기반으로 하는 양방향 접근이 가능한 큐의 일종입니다. 큐와 스택의 기능을 모두 지원하기 때문에 유연성이 매우 뛰어납니다.

다만, 큐와 스택의 특징처럼 순수(?) 이론적인 개념으론 중간 삽입과 제거를 지원하지 않습니다. 왜냐하면 시프트 연산을 필요로 하기 때문에 성능 문제가 있습니다.

덱은 브라우저의 히스토리(뒤로 가기와 앞으로 가기), 탭 메뉴 등을 구현할 때 사용합니다.

연습문제 1

반대로 봐도 같은 문장을 회문^Palindrome이라 합니다. 공백과 구두점을 따지진 않습니다. 아래는 그 여러 개의 회문 중 일부입니다. 아래의 문장을 거꾸로 출력해보세요.

"No lemon, no melon"

해답

classstd::deque

#include <iostream>

constexpr auto MAX_SIZE = 20;

class Deque {
private:
    char m_Data[MAX_SIZE];
    int m_Front;
    int m_Rear;
    int m_Size;

public:
    Deque() noexcept : m_Front(0), m_Rear(-1), m_Size(0) {}

    void PushFront(char ch) noexcept {
        if (!IsFull()) {
            m_Front = (m_Front - 1 + MAX_SIZE) % MAX_SIZE;
            m_Data[m_Front] = ch;

            if (m_Size == 0) {
                m_Rear = m_Front;
            }
            m_Size += 1;
        }
    }

    void PushBack(char ch) noexcept {
        if (!IsFull()) {
            m_Rear = (m_Rear + 1) % MAX_SIZE;
            m_Data[m_Rear] = ch;

            if (m_Size == 0) {
                m_Front = m_Rear;
            }
            m_Size += 1;
        }
    }

    void PopFront() noexcept {
        if (IsEmpty()) { return; }

        m_Front = (m_Front + 1) % MAX_SIZE;
        m_Size -= 1;
        if (m_Size == 0) {
            m_Front = 0;
            m_Rear = -1;
        }
    }

    void PopBack() noexcept {
        if (IsEmpty()) { return; }

        m_Rear = (m_Rear - 1 + MAX_SIZE) % MAX_SIZE;
        m_Size -= 1;
        if (m_Size == 0) {
            m_Front = 0;
            m_Rear = -1;
        }
    }

    char Front() noexcept {
        return (IsEmpty()) ? '\0' : m_Data[m_Front];
    }

    char Back() noexcept {
        return (IsEmpty()) ? '\0' : m_Data[m_Rear];
    }

    bool IsEmpty() noexcept {
        return m_Size == 0;
    }

    bool IsFull() noexcept {
        return m_Size == MAX_SIZE;
    }
};

int main() {
    std::string str = "No lemon, no melon";
    Deque dq;

    for (auto i = 0; i < str.length(); ++i) {
        dq.PushFront(str[i]);
    }

    while (!dq.IsEmpty()) {
        std::cout << dq.Front();
        dq.PopFront();
    }

    return 0;
}

#include <iostream>
#include <deque>

int main() {
    std::string str = "No lemon, no melon";
    std::deque<char> dq;

    for (auto i = 0; i < str.length(); ++i) {
        dq.push_front(str[i]);
    }

    while (!dq.empty()) {
        std::cout << dq.front();
        dq.pop_front();
    }

    return 0;
}