[자료구조] - 덱(deque)의 구조와 원형 덱 구현

1. 덱(deque)이란?

덱(deque)이란, double-ended queue의 줄임말로 큐의 front와 rear에서 삽입과 삭제가 모두 가능한 자료구조이다. 간단히 말해, 양방향 큐라고 볼 수 있다. 

 

덱은 양쪽에서 삽입과 삭제가 가능하다. 중간에 삽입하거나 삭제하는 것은 불가능하며, 양 끝만 가능하다.

 

 

---

2. 덱 구현을 위한 기본 함수

init (dq) - 덱 초기화
is_empty (dq) - 덱이 비어있는지 검사
is_full (dq) - 덱이 꽉 차있는지 검사
add_front (dq, e) - 덱의 맨 앞에 요소를 추가
add_rear (dq, e) - 덱의 맨 뒤에 요소를 추가
delete_front (dq) - 덱의 맨 앞 요소 반환 후 삭제
delete_rear (dq) - 덱의 맨 뒤 요소 반환 후 삭제
pop_front (dq) - 덱의 맨 앞 요소 반환(삭제X)
pop_rear (dq) - 덱의 맨 뒤 요소 반환(삭제X)

 

 

원형 덱 

 

단, 큐에서 공간 낭비 문제를 해결하기 위하여 원형큐 형태로 확장시킨 것처럼, 덱 또한 원형으로 구현하면 더 효율적이다. 

만약 삽입과 삭제 연산으로 인하여 front와 rear의 값이 기존 배열의 범위를 넘어간다면, 아래와 같이 새로운 값을 대입해주면 원형 덱을 구현할 수 있다. 

//add_rear() 연산 수행 시
rear ← (rear+1) % MAX;

//delete_front() 연산 수행 시
front ← (front+1) % MAX;

//add_front() 연산 수행시
rear ← (rear - 1 + MAX) % MAX;

//delete_rear() 연산 수행시
front ← (front - 1 + MAX) % MAX;

 

 

 

---

3. 원형 덱 구현하기

전체 코드로 원형 덱을 구현해보자.

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;

#define MAX 5
typedef int element;

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


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


//덱이 비어있는지 검사
int is_Empty(DequeType* q) {
	if (q->front == q->rear) return 1;
	else return 0;
}


//덱이 꽉 차있는지 검사
int is_full(DequeType* q) {
	if ((q->rear + 1) % MAX == q->front) return 1;
	else return 0;
}


//덱 출력 함수
void print_deque(DequeType* q) {
	//cout << "(front: " << q->front << " / rear: " << q->rear << ") -  ";
	if (is_Empty(q) == 0) {
		int i = q->front;
		 do{
			i = (i + 1) % MAX;
			cout << q->data[i] << " | ";
			if (i == q->rear)
				break;
		 } while (i != q->front);
	}
	cout << "\n";
}


//덱의 맨 앞에 삽입
void add_front(DequeType* q, element item) {
	if (is_full(q) == 1) {
		cout << "Overflow";
		exit(1);	//리턴값 없이 항수를 강제 종료
	}
	q->data[q->front] = item;
	q->front = (q->front - 1 + MAX) % MAX;
}


//덱의 맨 끝에 삽입
void add_rear(DequeType* q, element item) {
	if (is_full(q) == 1) {
		cout << "Overflow";
		exit(1);	//리턴값 없이 항수를 강제 종료
	}
	q->rear = (q->rear + 1) % MAX;
	q->data[q->rear] = item;
}


//덱의 맨 앞의 요소 제거 후 반환
element delete_front(DequeType* q) {
	if (is_Empty(q) == 1) {
		cout << "Empty";
		exit(1);  //리턴값 없이 함수를 강제 종료
	}
	q->front = (q->front + 1) % MAX;  //맨 앞의 요소는 front+1 의 인덱스에 있다.
	return q->data[q->front];
}


//덱의 맨 뒤 요소 제거 후 반환
element delete_rear(DequeType *q) {
	if (is_Empty(q) == 1) {
		cout << "Empty";
		exit(1);	//리턴값 없이 함수를 강제 종료
	}
	int x = q->rear;
	q->rear = (q->rear - 1 + MAX) % MAX;
	return q->data[x];
}


//덱의 맨 앞 요소 출력(삭제X)
element pop_front(DequeType* q) {
	if (is_Empty(q) == 1) {
		cout << "Empty!";
		exit(1);	//리턴값 없이 함수를 강제 종료
	}
	return q->data[(q->front + 1) % MAX];
}


//덱의 맨 뒤 요소 출력(삭제X)
element pop_rear(DequeType* q) {
	if (is_Empty(q) == 1) {
		cout << "Empty!";
		exit(1);	//리턴값 없이 함수를 강제 종료
	}
	return q->data[q->rear];
}

//main함수
int main() {
	DequeType q;

	init_deque(&q);
	for (int i = 0; i < 3; i++) {
		add_front(&q, i);
		cout << "add front " << i << "   =>  ";
		print_deque(&q);
	}
	add_rear(&q, 4);
	cout << "add rear " << 4 << "    =>  ";
	print_deque(&q);


	delete_rear(&q);
	cout << "delete rear " << "  =>  ";
	print_deque(&q);
	
	delete_front(&q);
	cout << "delete front " << " =>  ";
	print_deque(&q);
}

실행하면 위와 같다. add front를 수행하면 맨 앞에 요소가 삽입되고, add rear을 하면 맨 뒤에 요소가 추가되고, delete 연산도 마찬가지로 정상적으로 수행된 것을 확인할 수 있다.