덱(Deque, double-ended queue)

개요

덱(Double Ended Queue)은 앞과 뒤 양쪽 모두에서 데이터의 삽입과 제거가 가능한 큐를 말합니다.

구현

덱을 구성하는 연산은 다음과 같습니다.

fnIinit () : 덱을 초기화 합니다.
fnAddFront(item) : 덱의 전단에 item 을 삽입합니다.
fnDelFront() : 덱의 전단에서 item 을 1개 삭제 합니다.
fnAddRear(item) : 덱의 후단에 item 을 삽입합니다.
fnDelRear() : 덱의 후단에서 item 을 1개 삭제 합니다.
fnGetFront() : 덱의 전단에 있는 item 을 1개 얻습니다. 단, 삭제는 하지 않습니다.
fnGetRear() : 덱의 후단에 있는 item 을 1개 얻습니다. 단, 삭제는 하지 않습니다.
fnIsEmpty() : 덱이 비어 있는 경우 true 를 반환합니다.
fnIsFull() : 덱이 가득찬 경우 true 를 반환합니다.

저는 이 목록 중, GetFront 와 GetRear 는 사용하지 않기 때문에 구현항목에서 제외하였습니다.

앞서 구현하였던 원형큐에서 데이터의 삽입과 제거가 양측에서 이루어질 수 있도록 수정합니다. 이를 위해 기존의 코드를 재사용하고 fnAddFront()와 fnDelRear() 를 추가하겠습니다.

#include <stdio.h>

#define QUEUESIZE 256

typedef struct QueueType
{
    int head, tail;
    int items[QUEUESIZE];
} Queue;

// ▼ 추가
typedef Queue Deque;

void fnIinit(Queue *q)
{
    q->head = q->tail = 0;
}

int fnEnque(Queue *q, int i)
{
    if (fnIsFull(q) == 1)
    {
        return -1;
    }
    else
    {
        q->items[(q->tail++) % QUEUESIZE] = i;
        return 0;
    }
}

int fnDeque(Queue *q,
            /*out*/ int *pVal)
{
    if (fnIsEmpty(q) == 1)
    {
        return -1;
    }
    else
    {
        *pVal = q->items[(q->head++) % QUEUESIZE];
        return 0;
    }
}

int fnIsEmpty(Queue *q)
{
    if (q->tail == q->head)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

int fnIsFull(Queue *q)
{
    if (((q->tail + 1) % QUEUESIZE) == q->head)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

// ▼ 이하 추가
int fnAddRear(Deque *q, int i)
{
    return fnEnque(q, i);
}

int fnDelFront(Deque *q, int *pVal)
{
    return fnDeque(q, pVal);
}

int fnAddFront(Deque *q, int i)
{
    if (fnIsFull(q) != 1)
    {
        /*
          0 -> (QUEUESIZE - 1) : 254
          1 -> 0
          2 -> 1
        */
        if (q->head == 0)
        {
            q->head = QUEUESIZE - 1;
        }
        else
        {
            q->head--;
        }
        q->items[q->head] = i;
        return 0;
    }
    else
    {
        return -1;
    }
}

int fnDelRear(Deque *q, int *pVal)
{
    if (fnIsEmpty(q) != 1)
    {
        *pVal = q->items[(q->tail--) % QUEUESIZE];
        return 0;
    }
    else
    {
        return -1;
    }
}

int main(void)
{
    Deque q;
    int i, val;
    fnIinit(&q);

    for (i = 0; i < 10; i++)
    {
        if (i % 2 == 0)
        {
            fnAddFront(&q, i);
        }
        else
        {
            fnAddRear(&q, i);
        }
    }

    printf("Result : ");
    for (i = 0; i < 10; i++)
    {
        fnDelFront(&q, &val);
        printf("[%d] ", val);
    }
    printf("\n");

    return 0;
}

결론

앞서 언급했던 바와 같이 기존에 구현한 큐를 이용하여 간단히 덱을 구현해보았습니다. 위 코드를 실행하면 다음 그림과 같은 결과를 얻을 수 있습니다.

Result : [8] [6] [4] [2] [0] [1] [3] [5] [7] [9]

동작 시험을 위하여 앞과 뒤단에 번갈아가면서 데이터를 삽입하였으며 삽입된 데이터를 앞단에서 하나씩 제거하여 출력함으로써 짝수는 내림차순으로 데이터가 먼저 출력되고 홀수가 오름차순으로 나중에 출력되는 것을 직접 확인할 수 있었습니다.