C - 자료구조 덱

덱이란 ?
deque은 double-ended queue의 약자이며 일반 큐와 다르게 전단 후단 모두 삽입 및 삭제가 가능하다.
당연히 덱의 중간에 값을 삭제하거나 삽입하는 것은 불가능하다.


덱의 추상자료형

creat() : 덱 생성
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_rear(q) : 덱의 후단 값을 삭제하지 않고 뒤에 있는 요소를 반환

덱의 특징으로는 스택과 큐의 연산을 모두 가지고 있다.
위의 추상자료형을 토대로 살펴보면 add_front와 delete_front는 스택의 push와 pop연산과 같고
add_rear과 delete_front는 큐의 enqueue와 dequeue 연산과 같다.

스택과 큐에 비해 훨씬 융통성 많은 자료구조이며 덱의 전단 관련 동작만 이용시 스택이고, 삽입은 후단 삭제는 전단만을 사용하면 큐로 동작한다.

덱을 이용한 은행 서비스 시뮬레이션 프로그램


* 배열을 이용한 덱의 구현

#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 deque_print(DequeType *q){
    printf("DEQUE(front = %d rear = %d) = ", q->front, q->rear);
    if(!is_empty(q)){
        int i = q->front;
        do{
            i=(i+1) % MAX_QUEUE_SIZE;
            printf("%d | ", q->data[i]);
            if(i==q->rear) break;
        } while (i != q->front);
    }
    printf("\n");
}

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;
}

int delete_front(DequeType *q){ //전단 삭제
    if(is_empty(q)) error("큐가 공백상태입니다");
    q->front = (q->front+1) % MAX_QUEUE_SIZE;
    return q->data[q->front];
}

int get_front(DequeType *q){  
    return q->data[(q->front+1)%MAX_QUEUE_SIZE];
}

void add_front(DequeType *q, element val){ //전단 삽입
    q->data[q->front] = val;
    q->front = (q->front-1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
}

int delete_rear(DequeType *q) { //후단 삭제
    int prev= q->rear;
    q->rear = (q->rear - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
    return q->data[prev];
}

int get_rear(DequeType *q) {
    return q->data[q->rear];
}

int main(void){
    DequeType queue;
    init_deque(&queue);
    for(int i=0;i<3;i++){
        add_front(&queue,i);
        deque_print(&queue);
    }
   
    for(int i=-0;i<3;i++){
        delete_rear(&queue);
        deque_print(&queue);
    }
    return 0;

}

출력 결과

DEQUE(front = 4 rear = 0) = 0 | 
DEQUE(front = 3 rear = 0) = 1 | 0 | 
DEQUE(front = 2 rear = 0) = 2 | 1 | 0 | 
DEQUE(front = 2 rear = 4) = 2 | 1 | 
DEQUE(front = 2 rear = 3) = 2 | 
DEQUE(front = 2 rear = 2) =