[DS] Deque (Double-ended-queue)

# Deque

- double-ended queue

- 후단(rear)으로만 데이터를 삽입할 수 있었던 기존 선형 큐, 원형 큐와 달리 큐의 전단(front)

와 후단(rear)에서 모두 삽입과 삭제가 가능한 큐

* 데이터 삽입: front 감소, rear 증가

* 데이터 삭제: front 증가, rear 감소

# Abstract Data Type in deque

1) 매크로 및 타입 재정의

- boolean: 참과 거짓을 return하는 함수 및 변수들을 위해 정의

- 원하지 않는 곳에서 함수가 종료될 시 return 값 통일을 위해 ERROR(-1) 정의

- int type 이외에 다른 type에도 사용하기 위해 element로 type을 정의

#define TRUE 1
#define FALSE 0
#define ERROR -1
#define MAX_DEQUE_SIZE 5 

typedef int boolean;
typedef int element;

2) Deque 구조체

typedef struct __duqueueType {
    element *data;
    int rear, front;
}Deque;

3) init_deque

- 덱을 처음 생성하는 함수

- front == rear인 상태를 만들어줌

- MAX_DEQUE_SIZE만큼의 크기를 동적할당함

// 덱 초기화
void init_deque(Deque *q) {
    q->data = (element*)malloc(sizeof(element)*MAX_DEQUE_SIZE);
    q->front = q->rear = 0;
}

4) is_empty

- 실제로는 크기가 0 ~ MAX_DEQUE_SIZE -1의 index를 갖는 일자 배열의 형태

- 처음 비어있는 덱은 rear == front인 상태

- 원형 큐에서의 rear == front는 공백상태임을 의미

- 덱에서의 front 변수는 원형큐에서와 똑같이 항상 비어있는 배열을 가르킴

// 덱이 공백인지 검사
boolean is_empty(Deque *q) {
    if (q->front == q->rear) return TRUE;
    else return FALSE;
}

5) is_full

- 큐가 공백상태인지를 검사하기 위해, 현재 rear 변수에서 한 칸 업데이트 했을 때 front 변수와 같은지를 확인하여 같으면 true로 포화상태이고 아니라면 false임

//덱이 포화인지 검사
boolean is_full(Deque *q) {
    if (((q->rear + 1) % MAX_DEQUE_SIZE) == q->front) return TRUE;
    else return FALSE;
}

6) get_front

- 덱의 앞에서 삭제하지 않고 앞에 있는 요소를 반환

- front + 1을 하고 return을 하는 이유: front는 항상 공백을 가리키고 있기 때문

→ 실제 첫 요소는 front + 1 index에 위치하고 있기 때문

// 덱의 앞의 요소를 반환   
element get_front(Deque *q) {
    if (is_empty(q)) {
        printf("공백큐\n");
        return ERROR;
    }
    return q->data[(q->front + 1) % MAX_DEQUE_SIZE];
}

7) get_rear

- 덱의 뒤에서 삭제하지 않고 뒤에 있는 요소를 반환

// 덱의 rear를 반환
element get_rear(Deque *q) {
    if (is_empty) {
        printf("공백큐\n");
        return ERROR;
    }
    return q->data[q->rear];
}

8) add_front

- front 변수: 공백을 가르키기 때문에 한칸 씩 차이를 두고 데이터를 삽입

- 데이터의 삽입 방향

> q->front = (q->front-1 + MAX_DEQUE_SIZE) % MAX_DEQUE_SIZE

// 덱 앞에 요소 추가
void add_front(Deque *q, element data) {
    if (is_full(q)) {
        printf("포화큐\n");
        return;
    }
    q->data[q->front] = data;
    q->front = (q->front - 1 + MAX_DEQUE_SIZE) % MAX_DEQUE_SIZE;
    return;
}

9) add_rear

- rear가 index 초과시 0으로 돌아가게 해야하기 때문에 % 연산자를 사용하는 것

- 데이터의 삽입 방향

> q -> rear = (q -> rear + 1) % MAX_DEQUE_SIZE

// 덱의 뒤에 요소를 추가
void add_rear(Deque *q, element data) {
    if (is_full(q)) {
        printf("포화큐\n");
        return;
    }
    q->rear = (q->rear + 1) % MAX_DEQUE_SIZE;
    q->data[q->rear] = data;
}

10) delete_front

- front가 움직이면서 변수를 삭제

- 데이터 삭제 방향

> add_rear와 진행방향이 동일

> add_rear에서의 rear 변수의 업데이트 방식과 동일한 알고리즘 사용

// 덱의 앞의 요소를 반환후 삭제 
element delete_front(Deque *q) {
    if (is_empty(q)) {
        printf("공백큐\n");
        return ERROR;
    }
    element tmp = get_front(q);
    q->front = (q->front + 1) % MAX_DEQUE_SIZE;
    return tmp;
}

11) delete_rear

- 데이터 삭제 방향

> 원래 사용하던 수식(q->rear = (q->rear-1)%MAX_DEQUE_SIZE)을 사용하면 rear가 0일 때,

index가 -1이 되어 배열의 범위를 벗아나게 되므로 마이너스가 되는 것을 방지하기 위해

q->rear = (p->rear-1+MAX_DEQUE_SIZE)%MAX_DEQUE_SIZE를 사용함

// 덱의 뒤에 요소를 반환후 삭제

element delete_rear(Deque *q) {
    if (is_empty(q)) {
        printf("공백큐\n");
        return ERROR;
    }
    element tmp = q->data[q->rear];
    q->rear = (q->rear - 1 + MAX_DEQUE_SIZE) % MAX_DEQUE_SIZE;
    return tmp;
}

12) deque_print

- i를 front+1 변수로 초기화하고 rear를 만날 때까지 while을 반복

// 덱의 모든 요소 print 
void deque_print(Deque *q) {
    int i = (q->front + 1) % MAX_DEQUE_SIZE;
    printf("DEQUE(front=%d rear=%d) = ",q->front,q->rear);
    if (is_empty(q)) {
        printf("공백큐\n");
        return;
    }

    while (i!=q->rear) {
        printf("%d | ",q->data[i]);
        i = (i + 1) % MAX_DEQUE_SIZE;
    }

    printf("%d\n",q->data[i]);
}

13) Deque 구현

[코드]

#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define ERROR -1
#define MAX_DEQUE_SIZE 5

typedef int boolean;
typedef int element;
typedef struct __duqueueType {
    element *data;
    int rear, front;
}Deque;

void init_deque(Deque *q);
boolean is_empty(Deque *q);
boolean is_full(Deque *q);
element get_front(Deque *q);
element get_rear(Deque *q);
void add_front(Deque *q, element data);
void add_rear(Deque *q, element data);
element delete_front(Deque *q);
element delete_rear(Deque *q);
void deque_print(Deque *q);

int main() {

    Deque q;

    init_deque(&q);

    printf("# ADD FRONT\n\n");
    for (int i = 0; i < 3; i++) {
        add_front(&q, i);
        deque_print(&q);
    }

    printf("\n# DELETE REAR\n\n");
    for (int i = 0; i < 3; i++) {
        delete_rear(&q);
        deque_print(&q);
    }

    printf("\n# ADD REAR\n\n");
    for (int i = 0; i < 3; i++) {
        add_rear(&q, i);
        deque_print(&q);
    }

    printf("\n# DELETE FRONT\n\n");
    for (int i = 0; i < 3; i++) {
        delete_front(&q);
        deque_print(&q);
    }
    free(q.data);
    return 0;
}

void init_deque(Deque *q) {
    q->data = (element*)malloc(sizeof(element)*MAX_DEQUE_SIZE);
    q->front = q->rear = 0;
}

boolean is_empty(Deque *q) {
    if (q->front == q->rear) return TRUE;
    else return FALSE;
}

boolean is_full(Deque *q) {
    if (((q->rear + 1) % MAX_DEQUE_SIZE) == q->front) return TRUE;
    else return FALSE;
}

element get_front(Deque *q) {
    if (is_empty(q)) {
        printf("공백큐\n");
        return ERROR;
    }
    return q->data[(q->front + 1) % MAX_DEQUE_SIZE];
}

element get_rear(Deque *q) {
    if (is_empty) {
        printf("공백큐\n");
        return ERROR;
    }
    return q->data[q->rear];
}

void add_front(Deque *q, element data) {
    if (is_full(q)) {
        printf("포화큐\n");
        return;
    }
    q->data[q->front] = data;
    q->front = (q->front - 1 + MAX_DEQUE_SIZE) % MAX_DEQUE_SIZE;
    return;
}

void add_rear(Deque *q, element data) {
    if (is_full(q)) {
        printf("포화큐\n");
        return;
    }
    q->rear = (q->rear + 1) % MAX_DEQUE_SIZE;
    q->data[q->rear] = data;
}

element delete_front(Deque *q) {
    if (is_empty(q)) {
        printf("공백큐\n");
        return ERROR;
    }
    element tmp = get_front(q);
    q->front = (q->front + 1) % MAX_DEQUE_SIZE;
    return tmp;
}

element delete_rear(Deque *q) {
    if (is_empty(q)) {
        printf("공백큐\n");
        return ERROR;
    }
    element tmp = q->data[q->rear];
    q->rear = (q->rear - 1 + MAX_DEQUE_SIZE) % MAX_DEQUE_SIZE;
    return tmp;
}

void deque_print(Deque *q) {
    int i = (q->front + 1) % MAX_DEQUE_SIZE;
    printf("DEQUE(front=%d rear=%d) = ",q->front,q->rear);
    if (is_empty(q)) {
        printf("공백큐\n");
        return;
    }

    while (i!=q->rear) {
        printf("%d | ",q->data[i]);
        i = (i + 1) % MAX_DEQUE_SIZE;
    }

    printf("%d\n",q->data[i]);
}

[실행결과]

[참고]

[자료구조] 덱 Deque(Double-ended-queue) 큐 구현

덱 Deque(Double-ended-queue) 덱(deque)은 double-ended queue의 줄임말로써 후단(rear)으로만 데이터를 삽입했던 기존 선형 큐, 원형 큐와 달리 큐의 전단(front)와 후단(rear)에서 모두 삽입과 삭제가 가능한..

yjg-lab.tistory.com

c언어로 구현하는 덱(Deque) [자료구조]

[c언어로 구현하는 덱(Deque)] 덱은 double-ended queue의 줄임말으로, 큐의 앞, 뒤 모두에서 삽입 및 삭...

blog.naver.com

저작자표시 비영리 변경금지

'Study > Data Structure' 카테고리의 다른 글

[DS] 자료구조 개념 및 구현 Chapter 5 연습문제 (0)	2021.09.02
[DS] A Maze Problem (스택으로 미로 문제 풀기) (2)	2021.09.02
[DS] Evaluation of expression (수식의 평가) (0)	2021.09.02
[DS] Queue(큐) & Circular Queue(순환 큐) (0)	2021.08.31
[DS] Stack (스택) (0)	2021.08.31

# Deque

# Abstract Data Type in deque

'Study > Data Structure' 카테고리의 다른 글

검색 태그

티스토리툴바