C언어로 덱(Deque) 구현하기

덱이란?

일반적인 큐, 원형큐에서는 rear에서 삽입, front에서 삭제가 가능했다.

Deque은 double edged queue의 줄임말로, 큐의 front, rear에서 삽입, 삭제가 모두 가능한 큐를 말한다.

큐, 스택과 마찬가지로 중간에서 삽입과 삭제는 일어나지 않는다.

---

덱을 구현하기 위해 필요한 것

1. 덱 생성

2. 덱 초기화

3. 공백상태인지 포화상태인지 검사

4. add_front(앞에 추가) / add_rear(뒤에 추가)

5. delete_front(앞에서 삭제) / delete_rear(뒤에서 삭제)

6. get_front(뒤에서 요소반환) / get_rear(뒤에서 요소반환)

7. 덱 출력

---

1. 덱 생성

#include <stdio.h>
#define MAX_DEQUE 5

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

 

2. 덱 초기화

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

덱을 초기화할 때, front = 0 rear = 0이 된다.(0부터 시작)

 

3. 공백상태인지 포화상태인지 검사

int is_empty(DequeType *dq)
{
    if(dq->front == dq->rear)
        return 1; //공백 상태
    else
        return 0;
}

int is_full(DequeType *dq)
{
    if(dq->front == (dq->rear + 1) % MAX_DEQUE)
        return 1; //포화 상태
    else
        return 0;
}

포화상태는 (rear+1)%MAX_DEQUE이 front와 같다면 포화상태라고 판단한다.

 

4. add_front(앞에 추가) / add_rear(뒤에 추가)

void add_front(DequeType *dq, element item)
{
    if(is_full(dq) == 1){
        printf("full\n");
    }
    else{
        dq->data[dq->front] = item;
        dq->front = (dq->front - 1 + MAX_DEQUE) % MAX_DEQUE;
    }
}

front에 데이터 삽입할 때, 일단 front에 데이터 삽입 후, 반시계 방향으로 한칸 이동.

 

void add_rear(DequeType *dq, element item)
{
    if(is_full(dq) == 1){
        printf("full\n");
    }
    else{
        dq->rear = (dq->rear + 1) % MAX_DEQUE;
        dq->data[dq->rear] = item;
    }
}

rear에 데이터를 삽입할 때, rear를 시계방향으로 한칸 이동 후, 데이터 삽입한다.

 

5. delete_front(앞에서 삭제) / delete_rear(뒤에서 삭제)

int delete_front(DequeType *dq)
{
    if(is_empty(dq) == 1){
        printf("empty\n");
    }
    else{
        dq->front = (dq->front + 1) % MAX_DEQUE;
        return dq->data[dq->front];
    }
}

앞에서 삭제할 때, front를 시계방향으로 한칸 이동 후, 데이터를 삭제한다.

 

int delete_rear(DequeType *dq)
{
    element item;
    if(is_empty(dq) == 1){
        printf("empty\n");
    }
    else{
        item = dq->data[dq->rear];
        dq->rear = (dq->rear - 1 + MAX_DEQUE) % MAX_DEQUE;
        return item;
    }
}

 

뒤에서 삭제할 때, 일단 현재의 rear에 있는 데이터를 item변수에 넣어 놓고,

rear를 반시계 방향으로 한칸 이동한다.

그리고 미리 넣어놨던 item을 출력함.

 

6. get_front(앞에서 요소반환) / get_rear(뒤에서 요소반환)

int get_front(DequeType *dq)
{
    if(is_empty(dq) == 1){
        printf("empty\n");
    }
    else{
        return dq->data[(dq->front + 1) % MAX_DEQUE];
    }
}

앞에서 요소만 반환할 때, dq->front = (dq->front+1)%MAX_DEQUE를 안하는 이유는,

front의 위치를 변경할 필요가 없기 때문이다.

why? front의 위치를 변경한다는건 요소를 삭제하는 것과 같다.

그래서, 현재 위치해 있는 front보다 시계방향으로 한칸앞에  있는 요소를 뽑아내면 된다.(front의 위치를 변경하는게 아님에 주의하자!)

 

int get_rear(DequeType *dq)
{
    if(is_empty(dq) == 1){
        printf("empty\n");
    }
    else{
        return dq->data[dq->rear];
    }
}

뒤에서 요소만 반환할 때, 그냥 rear위치에 있는 요소만 반환하면 된다.

rear를 이동시키지 않아도 된다.

 

7.덱 출력

void print_deque(DequeType *dq)
{
    printf("(front = %d rear = %d) = ");
    if(!is_empty(dq) == 1){
        int i = dq->front;
        do{
            i = (i + 1) % MAX_DEQUE;
            printf("%d | ", dq->data[i]);
            if(i == dq->rear)
                break;
        } while(i != dq->front);
        printf("\n");
    }
}

---

전체코드를 확인하고, 결과를 보자

#include <stdio.h>
#define MAX_DEQUE 5

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

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

int is_empty(DequeType *dq)
{
    if(dq->front == dq->rear)
        return 1; //공백 상태
    else
        return 0;
}

int is_full(DequeType *dq)
{
    if(dq->front == (dq->rear + 1) % MAX_DEQUE)
        return 1; //포화 상태
    else
        return 0;
}

void add_front(DequeType *dq, element item)
{
    if(is_full(dq) == 1){
        printf("full\n");
    }
    else{
        dq->data[dq->front] = item;
        dq->front = (dq->front - 1 + MAX_DEQUE) % MAX_DEQUE;
    }
}

void add_rear(DequeType *dq, element item)
{
    if(is_full(dq) == 1){
        printf("full\n");
    }
    else{
        dq->rear = (dq->rear + 1) % MAX_DEQUE;
        dq->data[dq->rear] = item;
    }
}

int delete_front(DequeType *dq)
{
    if(is_empty(dq) == 1){
        printf("empty\n");
    }
    else{
        dq->front = (dq->front + 1) % MAX_DEQUE;
        return dq->data[dq->front];
    }
}

int delete_rear(DequeType *dq)
{
    element item;
    if(is_empty(dq) == 1){
        printf("empty\n");
    }
    else{
        item = dq->data[dq->rear];
        dq->rear = (dq->rear - 1 + MAX_DEQUE) % MAX_DEQUE;
        return item;
    }
}

int get_front(DequeType *dq)
{
    if(is_empty(dq) == 1){
        printf("empty\n");
    }
    else{
        return dq->data[(dq->front + 1) % MAX_DEQUE];
    }
}

int get_rear(DequeType *dq)
{
    if(is_empty(dq) == 1){
        printf("empty\n");
    }
    else{
        return dq->data[dq->rear];
    }
}

void print_deque(DequeType *dq)
{
    printf("(front = %d rear = %d) = ", dq->front, dq->rear);
    if(!is_empty(dq) == 1){
        int i = dq->front;
        do{
            i = (i + 1) % MAX_DEQUE;
            printf("%d | ", dq->data[i]);
            if(i == dq->rear)
                break;
        } while(i != dq->front);
        printf("\n");
    }
}

int main(void)
{
    DequeType dq;
    init_deque(&dq);

    add_rear(&dq, 1); //뒤에 삽입
    print_deque(&dq);

    add_rear(&dq, 2); //뒤에 삽입
    print_deque(&dq);

    add_front(&dq, 3); //앞에 삽입
    print_deque(&dq);

    delete_rear(&dq); //뒤에서 삭제
    print_deque(&dq);

    delete_front(&dq); //앞에서 삭제
    print_deque(&dq);

    return 0;
}

 

결과

 

이상 끝!