deque

deque

 

double-end queue

 

deque의 구조

 

deque의 특징

 

전단과 후단에서 모두 삽입 삭제가 가능하다

데이터 구조에서는 좀 더 연산이 간단한 데이터구조를 채택하여 사용하는 것이 효율적 & 지향한다

 

deque의 용도

 

- 키보드 입력 버퍼

- screen scroll

 

deque ADT

 

"add와 delete가 양 쪽으로 있다"

create(max_size)

- 최대 크기가 max_size인 덱 생성

init(dq)

- 덱 초기화

is_empty(dq)

- if (size == 0) return TRUE;

  else return FALSE;

is_full(dq)

- if (size == max_size) return TRUE;

  else return FALSE;

add_front(dq, e)

- if (is_full(q)) full로 인한 오류;

  else q의 끝에 e를 추가

add_rear(dq, e)

- if (is_full(q)) full로 인한 오류;

  else q의 끝에 e를 추가

delete_front(dq)

- if (is_empty(q)) empty로 인한 오류;

  else q의 맨 앞에 있는 e를 제거하여 return

delete_rear(dq)

- if (is_empty(q)) empty로 인한 오류;

  else q의 맨 앞에 있는 e를 제거하여 return

get_front(q)

- if (is_empty(q)) empty로 인한 오류;

  else q의 맨 앞에 있는 e를 읽어서 return

get_rear(q)

- if (is_empty(q)) empty로 인한 오류;

  else q의 맨 앞에 있는 e를 읽어서 return

 

덱 동작원리

 

배열을 이용한 덱 실제 구현 - 원형큐 사용

 

#include <stdio.h>
#include <stdlib.h>
#define MAX_QUEUE_SIZE 5

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

// 오류함수
void error(char *message)
{
	fprintf(stderr, "%s\n", message);
    exit(1)
}

// 덱 초기화
void init_queue(DequeType *q)
{
	q->rear = 0;		// -1 -> 0
    q->front = 0;		// -1 -> 0
}

// 현재 덱 현황 출력 함수
void queue_print(DequeType *q)
{
	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");
}

// 덱 포화상태 확인
int is_full(DequeType *q) 
{
	if (q->front == (q->rear+1) % MAX_QUEUE_SIZE)
    	return 1;
    else
    	return 0;
}

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

// 큐 (일반적인 큐와 똑같다)
// 덱 데이터 후단 추가
void add_rear(DequeType *q, int item)
{
	// error 처리
	if (is_full(q)) {
    	printf("큐가 포화상태 입니다.");
    }
    q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;		// 추가 방법 다름
    q->data[q->rear] = item;
}

// 덱 데이터 전단 삭제
void delete_front(DequeType *q)
{
	// error 처리
	if (is_full(q)) {
    	printf("큐가 공백상태 입니다.");
        return -1;
    }
    q->front = (q->front + 1) % MAX_QUEUE_SIZE;		// 삭제 방법 다름
    return q->data[q->front];
}

// 스택 (원형큐에서 스택기능을 구현)
// 덱 데이터 전단 추가
void add_front(DequeType *q, int item)
{
	// error 처리
	if (is_full(q)) {
    	printf("큐가 포화상태 입니다.");
    }
    // 추가 방법 다름
    q->data[q->front] = item;
    q->front = (q->front - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
}

// 새로운 덱만의 기능
// 덱 데이터 후단 삭제
void delete_rear(DequeType *q)
{
	// error 처리
	if (is_full(q)) {
    	printf("큐가 공백상태 입니다.");
        return -1;
    }
    // 삭제 방법 다름
    int prev = q->rear;
    q->rear = (q->rear - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
    return q->data[prev];
}

// 메인 함수 사용자 사용
int main(void)
{
	int item = 0;
    QueueType q;
    
    init_queue(&q);
	
    enqueue(&q, 10); queue_print(&q);
    //...
    dequeue(&q); queue_print(&q);
    //...
    return 0;
}