덱(Deque)

덱이란?

사진 출처 : https://book.naver.com/bookdb/book_detail.nhn?bid=14566230

• double-ended queue의 줄임말, "deck"과 발음이 같음
• 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조
• 두 개의 포인터를 사용하여, 양쪽에서 삭제와 삽입을 발생시킬 수 있다. 큐와 스택을 합친 형태로 생각할 수 있다.

덱의 주요 연산

• add_front(dq, e) :덱의 앞에 요소 삽입
• add_rear(dq, e) : 덱의 뒤에 요소 삽입
• delete_front(dq) : 덱의 앞에 있는 요소를 반환한 다음 삭제
• delete_rear(dq) : 덱의 뒤에 있는 요소를 반환한 다음 삭제
• get_front(dq) : 덱의 앞에서 삭제하지 않고 앞에 있는 요소를 반환
• get_rear(dq) : 덱의 뒤에서 삭제하지 않고 뒤에 있는 요소를 반환

---

배열을 이용한 덱 구현

#define DEQUE_SIZE 100
int arr[DEQUE_SIZE];
int f = DEQUE_SIZE / 2, r = DEQUE_SIZE / 2;
void add_front(int x) {
	arr[f--] = x;
}
void add_back(int x) {
	arr[++r] = x;
}
int is_empty() {
	if (r == f) return 1;
	else return 0;
}
int delete_front() {
	if (is_empty()) return -1;
	else {
		int re = arr[f + 1];
		arr[++f] = 0;
		return re;
	}
}
int delete_back() {
	if (is_empty()) return -1;
	else {
		int re = arr[r];
		arr[r--] = 0;
		return re;
	}
}
int get_front() {
	if (is_empty()) return -1;
	else return arr[f + 1];
}
int get_rear() {
	if (is_empty()) return -1;
	else return arr[r];
}

연결리스트를 이용한 덱 구현

typedef struct node {
	int data;
	struct node* prev;
	struct node* next;
} node;
typedef struct {
	node* front;
	node* rear;
	int count;
} Deque;
void initDeque(Deque* deque) {
	deque->front = deque->rear = NULL;
	deque->count = 0;
}
int is_empty(Deque* deque) {
	if (deque->count == 0) return 1;
	else return 0;
}
void add_front(Deque* deque, int data) {
	node* now = (node*)malloc(sizeof(node));
	if (is_empty(deque)) {
		deque->front = now;
		deque->rear = now;
		now->next = NULL;
	}
	else {
		deque->front->prev = now;
		now->next = deque->front;
		deque->front = now;
	}
	now->prev = NULL;
	now->data = data;
	(deque->count)++;
}
void add_back(Deque* deque, int data) {
	node* now = (node*)malloc(sizeof(node));
	if (is_empty(deque)) {
		deque->front = now;
		deque->rear = now;
		now->prev = NULL;
	}
	else {
		now->prev = deque->rear;
		deque->rear->next = now;
		deque->rear = now;
	}
	now->next = NULL;
	now->data = data;
	(deque->count)++;
}
int delete_front(Deque* deque) {
	if (is_empty(deque)) return -1;
	else {
		int rdata;
		node* rnode;
		rdata = deque->front->data;
		rnode = deque->front;
		deque->front = deque->front->next;
		if (deque->count == 1) deque->rear = NULL;
		free(rnode);
		(deque->count)--;
		return rdata;
	}
}
int delete_back(Deque* deque) {
	if (is_empty(deque)) return -1;
	else {
		int rdata;
		node* rnode;
		rdata = deque->rear->data;
		rnode = deque->rear;
		deque->rear = deque->rear->prev;
		if (deque->count == 1) deque->rear = NULL;
		free(rnode);
		(deque->count)--;
		return rdata;
	}
}
int get_front(Deque* deque) {
	if (is_empty(deque)) return -1;
	else return deque->front->data;
}
int get_rear(Deque* deque) {
	if (is_empty(deque)) return -1;
	else return deque->rear->data;
}