덱이란?

deque은 double-ended queue의 줄임말로 큐의 전단(front)와 후단(rear)에서 모두 삽입과 삭제가 가능한 큐를 말한다. 그러나 중간에 삽입과 삭제를 하는 것은 허용하지 않는다.

덱의 특징

덱은 후단만 사용하면 스택이 되고 후단에서 삽입, 전단에서 삭제 연산을 수행하면 큐가 된다.

🛢️ 스택(Stack) push: add_rear, pop: delete_rear

💡 큐(Queue) enqueue: add_rear, dequeue: delete_front

덱의 연산 및 구현

바로 덱을 구현해보자. 덱도 원형 큐와 같이 전단(front)와 후단(rear)을 사용한다. front는 하나 앞을 가리킨다.

원형덱

덱에서도 원형 큐와 같은 개념이 들어간다. 다만 원형 큐와 달리 원형 덱에서는 add_front와 delete_rear은 시계반대 방향으로의 회전이 추가 된다.

📌 알아두자!
시계방향으로 증가하는 함수: delete_front, add_rear, is_full, get_front
반시계방향으로 감소하는 함수: add_front, delete_rear

⏱️ 시계, 반시계 방향으로 회전하는 방법!

• 시계 방향은 증가할 때 수행되는 연산이다.
  시계 방향: ( point + 1 ) % MAX_SIZE
• 반시계 방향은 감소할 때 수행되는 연산이다.
  반시계 방향: ( point - 1 + MAX_SIZE ) % MAX_SIZE

init_deque

덱을 초기화 한다.
front와 rear을 둘다 0으로 초기화 한다.

void init_deque(DequeType *q)
{
    q->front = q->rear = 0;
}

is_empty

덱이 비어 있는지 확인한다. 원형 큐와 마찬가지로 front와 rear가 같으면 비어있다.

int is_empty(DequeType *q)
{
    return q->front == q->rear;
}

is_full

덱의 공간이 가득 차있는 지 확인한다. front가 전단의 하나 앞을 가리키고 있기 때문에 rear+1 한 것과 front가 같으면 가득찬 경우이다. 여기서 +1 시에는 시계방향으로 회전한다.

int is_full(DequeType *q)
{
    return (q->rear + 1) % MAX_QUEUE_SIZE == q->front;
}

add_front

전단에 항목을 추가한다. front가 하나 앞을 가리키고 있어 먼저 항목을 삽입한 후 front를 감소 시킨다. -1 시에는 반시계 방향으로 회전한다.

void add_front(DequeType *q, element item)
{
    if (is_full(q))
        error("덱 포화 상태");
    q->data[q->front] = item; // 주의! 항목을 삽입후 감소
    q->front = (q->front - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
}

add_rear

후단에 항목을 추가한다. rear를 증가시킨 후 항목을 삽입한다.

void add_rear(DequeType *q, element item)
{
    if (is_full(q))
        error("덱 포화 상태");
    q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
    q->data[q->rear] = item;
}

delete_front

전단에 항목을 반환하고 삭제한다. front가 하나 앞을 가리키기 때문에 front를 증가한 후 해당 위치의 값을 반환한다.

element delete_front(DequeType *q)
{
    if (is_empty(q))
        error("덱 공백 상태");
    q->front = (q->front + 1) % MAX_QUEUE_SIZE;
    return q->data[q->front];
}

delete_rear

후단에 항목을 반환하고 삭제한다. rear에 해당하는 값을 저장한후 rear을 감소시키고 이후 저장한 값을 반환한다.

element delete_rear(DequeType *q)
{
    if (is_empty(q))
        error("덱 공백 상태");
    element item = q->data[q->rear];
    q->rear = (q->rear - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
    return item;
}

get_front

전단의 항목을 반환한다. front에서 하나 앞을 가리키는 것이 전단에 해당하는 값이다.

element get_front(DequeType *q)
{
    if (is_empty(q))
        error("덱 공백 상태");
    return q->data[(q->front + 1) % MAX_QUEUE_SIZE];
}

get_rear

후단의 항목을 반환한다.

element get_rear(DequeType *q)
{
    if (is_empty(q))
        error("덱 공백 상태");
    return q->data[q->rear];
}

전체 코드

#include <stdio.h>
#include <stdlib.h>
#define MAX_QUEUE_SIZE 5

typedef int element;
typedef struct
{
    element data[MAX_QUEUE_SIZE];
    int front, rear;
} DequeType;

// 오류 함수
void error(char *message)
{
    fprintf(stderr, "%s\n", message);
    exit(1);
}

// 초기화 함수
void init_deque(DequeType *q)
{
    q->front = q->rear = 0;
}

// 공백 상태 확인 함수
int is_empty(DequeType *q)
{
    return q->front == q->rear;
}

// 포화 상태 확인 함수
int is_full(DequeType *q)
{
    return (q->rear + 1) % MAX_QUEUE_SIZE == q->front;
}

// 전단 삽입 함수
void add_front(DequeType *q, element item)
{
    if (is_full(q))
        error("덱 포화 상태");
    q->data[q->front] = item; // 주의! 항목을 삽입후 감소
    q->front = (q->front - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
}

// 후단 삽입 함수
void add_rear(DequeType *q, element item)
{
    if (is_full(q))
        error("덱 포화 상태");
    q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
    q->data[q->rear] = item;
}

// 전단 삭제 함수
element delete_front(DequeType *q)
{
    if (is_empty(q))
        error("덱 공백 상태");
    q->front = (q->front + 1) % MAX_QUEUE_SIZE;
    return q->data[q->front];
}

// 후단 삭제 함수
element delete_rear(DequeType *q)
{
    if (is_empty(q))
        error("덱 공백 상태");
    element item = q->data[q->rear];
    q->rear = (q->rear - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
    return item;
}

// 전단 반환 함수
element get_front(DequeType *q)
{
    if (is_empty(q))
        error("덱 공백 상태");
    return q->data[(q->front + 1) % MAX_QUEUE_SIZE];
}

// 후단 반환 함수
element get_rear(DequeType *q)
{
    if (is_empty(q))
        error("덱 공백 상태");
    return q->data[q->rear];
}

// 원형 큐 출력 함수
void deque_print(DequeType *q)
{
    printf("DEQUE(front=%d rear=%d) = ", q->front, q->rear);
    if (!is_empty(q))
    {
        for (int i = q->front; i != q->rear; i = (i + 1) % MAX_QUEUE_SIZE)
            printf("%d | ", q->data[(i + 1) % MAX_QUEUE_SIZE]);
    }
    printf("\n");
}

int main(void)
{
    DequeType deque;

    init_deque(&deque);

    for (int i = 0; i < 3; i++)
    {
        add_front(&deque, i);
        deque_print(&deque);
    }
    for (int i = 0; i < 3; i++)
    {
        delete_rear(&deque);
        deque_print(&deque);
    }

    return 0;
}

마무리

이번에는 deque에 대해서 알아보았다. deque 큐와 스택을 전부 구현한 것과 같아서 유용하게 사용할 수 있다. 원형 덱에서 반시계 방향으로 회전하는 개념 또한 잘 알아두자!

📕 참고 문헌

다음의 책을 참고했습니다.
C언어로 쉽게 풀어쓴 자료구조 [ 개정3판 ]
천인국, 공용해, 하상호 저 | 생능출판사 | 2021년 08월 20일