자료구조 - 덱

[덱 (Dequq, Double-ended Queue)]

덱은 양쪽 끝에서 삽입과 삭제가 모두 가능한 큐입니다. 즉, 앞과 뒤 양쪽에서 데이터를 삽입하고 삭제할 수 있습니다.

하지만 여전히 중간에 삽입하거나 삭제하는 것은 불가능합니다.

 

덱은 양쪽 끝에서의 삽입과 삭제가 모두 필요한 경우에 유용합니다. 예를 들어, 스케줄링 문제나 슬라이딩 윈도우 알고리즘 등에서 사용됩니다.

덱의 구현은 다음 예시처럼 하면 됩니다.

#include <iostream>
#include <deque>

int main() 
{
    std::deque<int> dq;  // 덱 생성
    dq.push_back(1);     // 덱의 뒤에 1 삽입
    dq.push_back(2);     // 덱의 뒤에 2 삽입
    dq.push_front(0);    // 덱의 앞에 0 삽입

    // 덱이 비어있지 않은 동안 반복
    while (!dq.empty()) 
    {
        std::cout << dq.front() << " ";  // 덱의 front 요소 출력
        dq.pop_front();                  // 덱에서 front 요소 제거
    }

    return 0;
}

 

 

 

 

[덱의 추상 자료형(ADT)]

이번에는 덱의 추상 자료형에 대해 알아보고 구현해보겠습니다.

객체 : n개의 element형 요소들의 순서 있는 모임
연산 :
    create() ::= 덱 생성
    init(dq) ::= 덱 초기화
    is_empty(dq) ::= 덱이 공백 상태인지 검사
    is_full(dq) ::= 덱이 가득 차있는지 검사
    add_front(dq, e) ::= 덱의 앞에 요소를 추가
    add_rear(dq, e) ::= 덱의 뒤에 요소를 추가
    delete_front(dq) ::= 덱의 앞의 요소를 반환한 다음 삭제
    delete_rear(dq) ::= 덱의 끝의 요소를 반환한 다음 삭제
    get_front(q) ::= 덱의 앞에서 삭제하지 않고 앞에 있는 요소 반환
    get_reaㄱ(q) ::= 덱의 뒤에서 삭제하지 않고 뒤에 있는 요소 반환

 

덱의 추상 자료형을 구현해보겠습니다.

#include <iostream>
#define MAX_SIZE 10  // 덱의 최대 크기 정의

class Deque 
{
    private:
        int arr[MAX_SIZE];
        int front;
        int rear;
        int size;

    public:
        Deque() : front(-1), rear(0), size(0) {}  // 초기 생성자    

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

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

        // 덱의 앞쪽에 요소를 삽입
        void insertFront(int element) 
        {
            if (isFull()) 
            {
                std::cout << "Deque is full\n";
                return;
            }
            if (front == -1) 
            {
                front = rear = 0;
            } 
            else if (front == 0)
            {
                front = MAX_SIZE - 1;
            } 
            else
            {
            front = front - 1;
            }
            arr[front] = element;
            size++;
        }

        // 덱의 뒤쪽에 요소를 삽입
        void insertRear(int element) 
        {
            if (isFull()) 
            {
                std::cout << "Deque is full\n";
                return;
            }
            if (front == -1)
            {
                front = rear = 0;
            } 
            else if (rear == MAX_SIZE - 1) 
            {
                rear = 0;
            } 
            else 
            {
                rear = rear + 1;
            }
            arr[rear] = element;
            size++;
        }

        // 덱의 앞쪽에서 요소를 삭제
        void deleteFront() 
        {
            if (isEmpty()) 
            {
                std::cout << "Deque is empty\n";
                return;
            }
            if (front == rear) 
            {
                front = -1;
                rear = -1;
            }
            else if (front == MAX_SIZE - 1) 
            {
                front = 0;
            }
            else 
            {
                front = front + 1;
            }
            size--;
        }

        // 덱의 뒤쪽에서 요소를 삭제
        void deleteRear()
        {
            if (isEmpty()) 
            {
                std::cout << "Deque is empty\n";
                return;
            }
            if (front == rear) 
            {
                front = -1;
                rear = -1;
            } 
            else if (rear == 0) 
            {
                rear = MAX_SIZE - 1;
            }
            else 
            {
                rear = rear - 1;
            }
            size--;
        }        

        // 덱의 앞쪽 요소를 반환
        int getFront() 
        {
            if (isEmpty()) 
            {
                std::cout << "Deque is empty\n";
                return -1;
            }
            return arr[front];
        }    
    
        // 덱의 뒤쪽 요소를 반환
        int getRear() 
        {
            if (isEmpty() || rear < 0) 
            {
                std::cout << "Deque is empty\n";
                return -1;
            }
            return arr[rear];
        }
};

int main()
{
    Deque dq;

    dq.insertRear(5);
    dq.insertRear(10);
    std::cout << "Rear element: " << dq.getRear() << std::endl;

    dq.deleteRear();
    std::cout << "After deleting rear, new rear: " << dq.getRear() << std::endl;

    dq.insertFront(15);
    std::cout << "Front element: " << dq.getFront() << std::endl;

    dq.deleteFront();
    std::cout << "After deleting front, new front: " << dq.getFront() << std::endl;

    return 0;
}

 

 

[덱의 장점과 단점]

 

장점

• 양쪽 끝에서의 삽입과 삭제가 O(1) 시간 복잡도를 가집니다.
• 다양한 작업에 유연하게 사용할 수 있습니다.

 

단점

• 일반 큐보다 구현이 복잡합니다.
• 양쪽 끝을 관리하기 위해 추가적인 메모리와 포인터가 필요합니다.

 

 

 

[원형 덱(Circular Deque)]

원형 큐와 덱은 공통점이 많은데 원형 큐를 확장해서 덱 또한 손쉽게 구현이 가능합니다.

덱도 원형 큐와 같이 전단과 후단을 사용하고, 큐에서 사용한 배열 data와 front, rear을 그대로 사용하면 되고 추가적인 데이터가 필요하지 않습니다.

 

덱에서 새롭게 추가된 연산은 delete_rear(), add_front(), get_rear()가 있습니다. 

get_rear()가 가장 간단한데 공백 상태가 아닌 경우 rear가 가리키는 항목을 반환하면 됩니다.

 

delete_rear() 와 add_front() 에서는 원형 큐와 다르게 반대 방향의 회전이 필요합니다. 

front 혹은 rear 를 감소시켜야 하는데, 감소시킨 값이 음수가 되면 MAX_QUEUE_SIZE 를 더해주어야 합니다.

front <- (front-1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
rear <- (rear-1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;

 

 

 

[원형 덱의 장점과 단점]

 

장점

 

• 고정된 크기 내에서 메모리를 효율적으로 사용합니다.
• 양쪽 끝에서의 삽입과 삭제가 O(1) 시간 복잡도를 가집니다.

 

 

단점

 

• 구현이 매우 복잡합니다.
• 큐가 가득 찬 상태와 비어 있는 상태를 구분하기 위해 추가적인 공간과 로직이 필요합니다.

 

 

 

원형 덱의 예시 코드

#include <iostream>
#define MAX_SIZE 5  // 원형 덱의 최대 크기 정의

class CircularDeque 
{
    private:
        int front;              // 덱의 front 포인터
        int rear;               // 덱의 rear 포인터
        int arr[MAX_SIZE];      // 원형 덱 배열    

    public:
        CircularDeque() : front(-1), rear(-1) {}  // 초기 생성자    

        // 덱이 가득 찼는지 확인
        bool isFull() 
        {
            return (front == (rear + 1) % MAX_SIZE);
        }

        // 덱이 비어있는지 확인
        bool isEmpty() 
        {
            return (front == -1);
        }

        // 덱의 앞에 요소를 삽입
        void insertFront(int value) 
        {
            if (isFull()) 
            {
                std::cout << "Deque is Full\n";
                return;
            }
            if (front == -1) 
            {
                front = rear = 0;  // 첫 요소 삽입 시 포인터 초기화
            } 
            else if (front == 0) 
            {
                front = MAX_SIZE - 1;  // front 포인터 이동
            }
            else
            {
                front--;
            }
            arr[front] = value;  // 새로운 값 삽입
        }

        // 덱의 뒤에 요소를 삽입
        void insertRear(int value) 
        {
            if (isFull()) 
            {
                std::cout << "Deque is Full\n";
                return;
            }
            if (front == -1) 
            {
                front = rear = 0;  // 첫 요소 삽입 시 포인터 초기화
            } 
            
            else if (rear == MAX_SIZE - 1) {
                rear = 0;  // rear 포인터 이동
            } 
            else 
            {
                rear++;
            }
            arr[rear] = value;  // 새로운 값 삽입
        }    

        // 덱의 앞에서 요소 제거
        void deleteFront() 
        {
            if (isEmpty()) 
            {
                std::cout << "Deque is Empty\n";
                return;
            }
            if (front == rear) 
            {
                front = rear = -1;  // 마지막 요소 제거 시 포인터 초기화
            } 
            else if (front == MAX_SIZE - 1) 
            {
                front = 0;  // front 포인터 이동
            }
            else
            {
                front++;
            }
        }

        // 덱의 뒤에서 요소 제거
        void deleteRear() 
        {
            if (isEmpty()) 
            {
                std::cout << "Deque is Empty\n";
                return;
            }
            if (front == rear) 
            {
                front = rear = -1;  // 마지막 요소 제거 시 포인터 초기화
            } 
            else if (rear == 0) 
            {
                rear = MAX_SIZE - 1;  // rear 포인터 이동
            } 
            else 
            {
                rear--;
            }
        }

        // 덱의 front 요소를 반환
        int getFront()
        {
            if (isEmpty())
            {
                std::cout << "Deque is Empty\n";
                return -1;
            }
            return arr[front];
        }

        // 덱의 rear 요소를 반환
        int getRear() 
        {
            if (isEmpty())
            {
                std::cout << "Deque is Empty\n";
                return -1;
            }
            return arr[rear];
        }
};

int main()
{
    CircularDeque cdq;  // 원형 덱 생성
    cdq.insertRear(1);  // 원형 덱의 뒤에 1 삽입
    cdq.insertRear(2);  // 원형 덱의 뒤에 2 삽입
    cdq.insertFront(0);  // 원형 덱의 앞에 0 삽입

    std::cout << "Front element: " << cdq.getFront() << "\n";  // 원형 덱의 front 요소 출력
    std::cout << "Rear element: " << cdq.getRear() << "\n";    // 원형 덱의 rear 요소 출력

    cdq.deleteFront();  // 원형 덱의 앞에서 요소 제거
    cdq.deleteRear();   // 원형 덱의 뒤에서 요소 제거

    std::cout << "Front element: " << cdq.getFront() << "\n";  // 원형 덱의 front 요소 출력
    std::cout << "Rear element: " << cdq.getRear() << "\n";    // 원형 덱의 rear 요소 출력

    return 0;
}