덱(Deque)

안녕하세요!!

이번에는 좀 빨리 돌아온 감이 없잖아 있네요 ㅎㅎ

요즘에 느끼는건 일을 미루지 말자에요 ㅎ

알면서도 지키기 어렵지만 이번에는 다시 마음 먹고 부지런하게 살아볼려구요!!

작심 삼일이 되지않게 더 노력해야겠네요 :)

---

목차

1. 덱(Deque)에대한 설명

2. 덱(Deque)의 추상 자료형 정의

3. 덱(Deque)의 구현

---

이번에 알아볼것은 덱(Deque)라는 것이에요

이름만 들어서는 감이 잘 안오시죠??

뭔가 합성어 같은 느낌이 확 오는 느낌인데, 맞습니다 ㅎㅎ double-ended-queue의 줄임말입니다

말 그대로 큐이기는 한데 양쪽끝에서 삽입과 삭제가 이루어질 수 있는 자료구조 입니다

원래의 큐는 FIFO구조로 First in First out이었는데

덱은 그런거 없이 First in 하구 Last out 할 수 도 있고 아니면 2번째로 나갈 수 도 있는 그런 구조 입니다

 

---

덱(Deque)을 추상 자료형으로 정의해 볼까요?

• is_empty() -> 덱이 비었는지 확인하는 함수이다
• is_full() -> 덱이 가득찼는지 확인하는 함수이다
• add_front(element) -> 덱의 앞부분에 데이터를 추가하는 함수이다
• add_rear(element) -> 덱의 뒷부분에 데이터를 추가하는 함수이다
• delete_front() -> 덱의 앞부분에 있는 요소를 반환하고 삭제하는 함수이다
• delete_rear() -> 덱의 뒷부분에 있는 요소를 반환하고 삭제하는 함수이다
• get_front() -> 덱의 앞부분의 요소를 반환하는 함수이다
• get_rear() -> 덱의 뒷부분의 요소를 반환하는 함수이다

아무래도 앞뒤로 데이터를 추가하고 삭제하다 보니깐 구성해야하는 부분도 2배로 많아 진것같네요 ㅎㅎ

 

이번에는 덱(Deque)을 실제로 구현해볼까요?

구현언어 : C언어

#define MAX_SIZE 10

typedef int element;

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

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

void error(char *message){
    fprintf(stderr, "%s", message);
    exit(1);
}

 

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

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

 

void add_front(DequeType *d, element value){
    if(is_full(d)) error("덱이 가득찼습니다");
    d->data[d->front] = value;
    d->front = (d->front-1+MAX_SIZE)%MAX_SIZE;
}

void add_rear(DequeType *d, element value){
    if(is_full(d)) error("덱이 가득찼습니다");
    d->rear = (d->rear+1)%MAX_SIZE;
    d->data[d->rear] = value;
}

 

int delete_front(DequeType *d){
    if(is_empty(d)) error("덱이 비었습니다");
    d->front = (d->front+1)%MAX_SIZE;
    return d->data[d->front];
}

int delete_rear(DequeType *d){
    if(is_empty(d)) error("덱이 비었습니다");
    int value = d->data[d->rear];
    d->rear = (d->rear-1+MAX_SIZE)%MAX_SIZE;
    return value;
}

 

int get_front(DequeType *d){
    if(is_empty(d)) error("덱이 비었습니다");
    return d->data[d->front];
}

int get_rear(DequeType *d){
    if(is_empty(d)) error("덱이 비었습니다");
    return d->data[(d->rear-1+MAX_SIZE)%MAX_SIZE];
}

보시면 아시겠지만 기본적인 구조는 원형큐와 비슷한데

거기에다가 양쪽으로의 삽입 삭제 연산이 가능하도록 추가되었습니다

제 생각에는 (d->(front 또는 rear)-1+MAX_SIZE)%MAX_SIZE 이부분이 핵심이라고 볼 수 있을 것 같습니다

0보다 작아지는 순간에 만약에 원형큐의 크기가 10이라면

다음은 9가 되어야 하는 부분을 해결해준 부분이라고 볼 수 있습니다

---

여기까지가 덱(Deque)에 대한 내용이었습니다!!

읽어주셔서 감사합니다!! :)

궁금하신 점이나 부족한 부분은 댓글로 남겨주세요^

건강 조심하시구 다음에 뵈요 ㅎㅎ