[자료구조][C] 덱 (deque)

🐰 덱(deque) ? 

덱은 double-ended queue의 줄임말로서 큐의 전단(front)나 후단(rear)에서 모두 삽입과 삭제가 가능한 큐이다. 

덱의 연산
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_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) // q->front == 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; // rear의 값을 먼저 하나 더하고
    q->data[q->rear] = item; // 더해진 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 get_front(DequeType* q){
    if(is_empty(q))
        error("큐가 공백상태입니다");
    return q->data[(q->front+1) % MAX_QUEUE_SIZE];
}
void add_front(DequeType* q,element val){
    if (is_full(q))
        error ("큐가 포화상태입니다");
    q->data[q->front]=val; // front는 공백이니깐
    q->front=(q->front-1+MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
}
element delete_rear(DequeType* q){
    int prev=q->rear;
    if (is_empty(q))
        error("큐가 공백상태입니다");
    q->rear=(q->rear-1+MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
    return q->data[prev];
}
element get_rear(DequeType* q){
    if (is_empty(q))
        error("큐가 공백상태입니다");
    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;
}

 

 

---

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

처음의 비어있는 덱은 rear == front 상태이다. rear == front는 공백상태 임을 나타낸다. 

 

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

front + 1 을 하는 이유는 front는 항상 공백을 가르키고 있기 때문에 실제 첫 요소는 front + 1 의 index에 위치하고 있기 때문이다. 

 

void add_rear(DequeType* q,element item){
    if(is_full(q))
        error("큐가 포화상태입니다");
    q->rear = (q->rear+1) % MAX_QUEUE_SIZE; // rear의 값을 먼저 하나 더하고
    q->data[q->rear] = item; // 더해진 rear 인덱스에 item의 값을 넣어준다
}

원형큐와 마찬가지로 rear 변수는 0 -> 1 -> 2 ... -> Deque_Max_SIZE 로 진행하다 index 초과시 다시 0으로 돌아가야한다. 따라서 나머지 연산자를 활용해준다. 

 

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

front 가 움직이면서 데이터를 삭제한다. 이때의 front 변수의 움직임 방향은 위의 add_rear과 동일하므로 동일한 알고리즘을 활용해준다. 

 

element delete_rear(DequeType* q){
    int prev=q->rear;
    if (is_empty(q))
        error("큐가 공백상태입니다");
    q->rear=(q->rear-1+MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
    return q->data[prev];
}

데이터 삭제방향이 이제까지와는 반대다. 이제까지 q->rear = (q->rear+1) % MAX_QUEUE_SIZE와 같은 알고리즘을 활용했으니 q->rear = (q->rear-1) % MAX_QUEUE_SIZE 를 하면 해결된다고 생각하겠지만 rear 변수가 0일때 위를 계산해보면 -1이 나오게 되어 배열의 인덱스 범위를 벗어나버린다. 따라서, 마이너스가 되는 것을 방지하기 위해 + MAX_QUEUE_SIZE를 해준다. 

 

void add_front(DequeType* q,element val){
    if (is_full(q))
        error ("큐가 포화상태입니다");
    q->data[q->front]=val; // front는 공백이니깐
    q->front=(q->front-1+MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
}

위와 동일한 알고리즘이다.