chapter 3. 덱(deque)

안녕~!

 여러분 안녕하세요~! 제가 너무 오랜만에 글을 쓰나요?ㅎ.... 

 

오늘은 자료 구조 중에 deque에 대해 배워보는 시간입니다. 다들 준비되셨나요?

 

---

디큐?, 데크?, 덱? (뭐라고 읽는 거야...)

 

여러분은 deque을 어떻게 읽으시나요?

저도 영어를 잘하는 편이 아니라서 처음에 발음이 너무 헷갈렸는데요.

개발자들은 deque을 덱이라고 읽습니다. 

그렇다면 deque는 무슨 뜻일까요? 

 

deque는 double-ended queue라는 뜻입니다. 

굳이 우리나라 말로 바꾸자면 2개로 끝나는 queue 정도로 바꿀 수 있을 것 같습니다. 

 

그래도 이해가 안되나요? 

 

예전에 우리는 스택과 큐에 대해 배웠습니다. 기억나시나요?

 

기억이 안나시면 예전 글을 참고하시면 됩니다. ㅎ...

 

스택은 LIFO(Last In First Out) 구조를 가지고 있고 큐는 FIFO(First In First Out) 구조를 가지고 있습니다. 

 

덱은 스택과 큐를 합쳐 놓은 형태입니다. 

 

 

 

그렇기에 앞쪽과 뒤쪽에서 모두 자료를 저장하고 출력할 수 있습니다. 

 

스택과 큐보다 기능이 많기에 구현하기에 살짝 까다롭지만 엄청난 자료 구조입니다. 

 

 

---

deque의 주요 기능

 

 

push와 pop이 front와 rear부분에서 모두 가능합니다.

 

VISUALGO를 통해서 deque의 데이터 입출력 과정을 살펴보면 아래와 같습니다. 

 

 

VISUALGO

 

 

 

 

 

 

 

 

 

 

---

 

C++로 deque 구현

 

 

deque.cpp

#include <iostream>

using namespace std;

class deque
{

private:
    int size = 5;
    int number = 0;
    int data[5];
    int front, rear;

public:
    deque();
    void push_front(int x);
    void push_rear(int x);
    void pop_front();
    void pop_rear();
    void get_front();
    void get_rear();
    void display();
    void get_size();
    bool isEmpty();
    bool isFull();
};

deque::deque()
{
    front = 0;
    rear = 0;
}

bool deque::isEmpty()
{
    return number == 0 ? true : false;
}

bool deque::isFull()
{

    return number == size ? true : false;
}

void deque::push_front(int x)
{

    if (number == size)
    {
        cout << "FUll~!!" << endl;
    }
    else
    {
        data[front] = x;                   // 배열에 원하는 정보를 먼저 저장함
        front = (front - 1 + size) % size; //front를 감소시키므로 가리키고 있는 곳을 변경함. 인덱스가 음수를 가리키지 않도록 하기 위해서 size로 나눈 나머지를 다음 인덱스로 저장합니다.
        number += 1;
    }
}

void deque::push_rear(int x)
{

    if (number == size)
    {
        cout << "Full~!!" << endl;
    }
    else
    {
        rear = (rear + 1 + size) % size; // 이 부분은 위에서 작성한 내용하고 순서가 다른데요. 위에서는 배열에 데이터를 저장하고
        data[rear] = x;                  //인덱스를 바꿨다면 이번에는 인덱스를 먼저 바꾸고 데이터를 저장합니다.
        number += 1;
    }
}

void deque::pop_front()
{

    if (number == size)
    {

        cout << "Empty~!!" << endl;
    }
    else
    {
        front = (front + 1 + size) % size; // push front와 반대로 인덱스의 값을 1개씩 늘려주어여 합니다.
        number -= 1;                       //정해 놓은 사이즈를 넘어가면 인덱스가 앞쪽으로 돌아오도록 하기 위해서 size로 나눈 나머지를 front에 저장합니다.
    }
}

void deque::pop_rear()
{

    if (number == 0)
    {
        cout << "Empty~!!" << endl;
    }
    else
    {
        rear = (rear - 1 + size) % size; //push_rear에서와 반대로 pop을 진행하면 rear 값이 줄어들도록 설정
        number -= 1;
    }
}

void deque::get_size()
{

    cout << number << endl; //사이즈를 출력해주는 함수를 작성함. number는 배열에 실직적으로 담고 있는 값들의 개수를 알고 있음
}

void deque::display()
{

    if (number == 0)
    {

        cout << "there is nothing" << endl;
    }
    else // 이 부분이 오늘 하는 내용 중에 가장 어려운 내용임.
    {

        cout << "front~rear: ";

        int i = (front + 1 + size) % size; // 현재 front 부분이 배열에서 가리키는 것이 우리 저장한 정보가 담겨있는 곳이 아니기 때문에 +1을 해주어야함.
        //왜냐하면 위에서 구현을 할때 정보를 저장한 다음에 front에 -1을 해주었기에 현재 front는 다음 정보가 저장될 곳을 가리키고 있기 때문...

        for (int j = 0; j < number; j++) // 실제로 들어있는 데이터의 개수만큼 for문을 통해서 정보를 출력해주면 됨.
        {

            if (i == size) // 인덱스가 사이즈보다 커지거나 같아지는 것을 방지하기 위해서...
            {
                i = i % size;
            }

            cout << data[i] << "-->";
            i += 1; // 출력하고 싶은 배열의 인덱스 값을 증가시키면 됩니다.
        }

        cout << "end" << endl;
    }
}

 

 

main.cpp

#include <iostream>
#include "deque.cpp"

using namespace std;

int main()
{

    deque dq;

    dq.push_front(1);
    dq.display();

    dq.push_front(2);
    dq.display();

    dq.push_front(3);
    dq.display();

    dq.push_front(4);
    dq.display();

    dq.push_front(5);
    dq.display();

    dq.push_rear(10);
    dq.display();

    dq.pop_rear();
    dq.display();

    dq.pop_rear();
    dq.display();

    dq.pop_rear();
    dq.display();

    dq.pop_front();
    dq.display();

    dq.pop_front();
    dq.display();

    dq.push_rear(100);
    dq.display();

}

 

 

 

위에서 작성한 코드를 실행하면 터미널에 다음과 같이 결과가 출력됩니다. 

 

여러분들도 저와 동일하게 출력되었나요?