덱(Deque)

오늘은 deque에 대해 공부해보겠습니다. deque는 stack과 queue를 합쳐 놓은 자료구조입니다. 메모리 공간을 push/pop_front 함수를 이용해 First In First Out(FIFO) 형태로 사용할 수 있고, push/pop_back 함수를 통해 Last In First Out(LIFO) 형태로도 활용 될 수 있습니다.

 

Deque 자료구조

STL을 활용한 deque의 선언법과 정의되어있는 멤버함수는 다음과 같습니다.

push_front: 데이터의 맨 앞쪽에 새로운 데이터를 넣습니다.
push_back: 데이터의 뒷쪽에 새로운 데이터를 넣습니다.
pop_front: 맨앞쪽의 데이터 하나를 제거합니다.
pop_back: 맨뒷쪽의 데이터 하나를 제거합니다.
empty: 메모리에 데이터가 비어있는지 확인하여 비었으면 true, 그렇지 않다면 false를 반환합니다.
clear: 메모리 내의 데이터를 비웁니다.
at: 메모리 값 내부를 index를 활용해 read/write를 할 수 있습니다.
front: 메모리의 맨 앞쪽의 데이터를 read 합니다.
back: 메모리의 맨 뒷쪽의 데이터를 read 합니다.

이번엔 STL에 구현된 deque을 사용해보겠습니다.

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

void print()
{
    for (int k = 0; k < (int)deq.size(); k++)
        printf("%d ", deq.at(k));
    printf("\n");
}

int main()
{
    deq.push_front(1);
    print();

    deq.push_front(2);
    print();

    deq.push_front(3);
    print();

    deq.pop_back();
    print();

    cout << "front: " << deq.front() << ", " << "end: " << deq.back() << endl;

    deq.pop_back();
    print();

    deq.pop_back();
    print();

    return 0;
}

push_front 연산에 의해 앞쪽에 data가 추가되었습니다.

push_front 과정

이번엔 deque를 직접 코드로 작성을 해보겠습니다.  STL의 deque 함수의 interface는 동일한데요. head는 data가 새롭게 insert될 위치를 항상 가리키고 있고, tail은 맨마지막 data 위치를 가리키고 있습니다. Tail 다음에 head가 위치하면 메모리가 가득 꽉 찬 상태며, head와 tail이 동일한 위치를 가리키면 비어있는 상태입니다.

 

가득찰 조건(full)과 빈 조건(empty)

#include <iostream>
using namespace std;
template <typename T>

class deque {
private:
    #define MAX_SIZE 16
    T dataArray[MAX_SIZE];
    int head, tail;

public:
    deque() : head(0), tail(0) 
    {
        memset(dataArray, 0, sizeof(dataArray));
    }

    ~deque() {}

    void push_front(T data)
    {
        if (full())
        {
            printf("deque is full\n");
            return;
        }
        dataArray[head] = data;
        head = (head + MAX_SIZE - 1) % MAX_SIZE;
    }

    void push_back(T data)
    {
        if (full())
        {
            printf("deque is full\n");
            return;
        }
        tail = (tail + 1) % MAX_SIZE;
        dataArray[tail] = data;
    }

    bool empty()
    {
        return head == tail;
    }

    bool full()
    {
        return ((tail + 1) % MAX_SIZE) == head;
    }

    void pop_front()
    {
        if (empty())
        {
            printf("deque is empty\n");
            return;
        }

        head = (head + 1) % MAX_SIZE;
    }

    void pop_back()
    {
        if (empty())
        {
            printf("deque is empty\n");
            return;
        }

        tail = (tail + MAX_SIZE - 1) % MAX_SIZE;
    }

    T front()
    {
        return dataArray[(head + 1) % MAX_SIZE];
    }

    T back()
    {
        return dataArray[tail];
    }

    void print()
    {
        int h = head, t = tail;
        while (h != t)
        {
            h = (h + 1) % MAX_SIZE;
            printf("%d ", dataArray[h]);
        }
        printf("\n");
    }
};

int main()
{
    deque<int> deq;
    deq.push_front(1);
    deq.print();

    deq.push_front(2);
    deq.print();

    deq.push_front(3);
    deq.print();

    deq.pop_back();
    deq.print();

    cout << "front: " << deq.front() << ", " << "end: " << deq.back() << endl;

    deq.pop_back();
    deq.print();

    deq.pop_back();
    deq.print();

    deq.pop_back();
    deq.print();

    return 0;
}

STL의 deque와 달리 메모리가 가득찼는지를 확인하는 full 함수가 추가되었습니다.

자 오늘은 여기까지