덱

덱(deque): double-ended-queue

- 큐의 전단(front)과 후단(rear)에서 모두 삽입과 삭제가 가능한 큐

- 중간에 삽입하거나 삭제하는 것은 불가

 

덱의 추상 자료형

- 덱은 스택과 큐의 연산들을 모두 가지고 있음

- add_front와 delete_front 연산은 스택의 push와 pop 연산과 동일

- add_rear 연산과 delete_front 연산은 각각 큐의 enqueue와 dequeue 연산과 동일

- 덱은 스택이나 큐에 비해 융통성 많은 자료 구조

- 덱의 전단과 관련된 연산들만을 사용하면 스택으로 동작

- 삽입은 후단, 삭제는 전단만을 사용하면 큐로 동작

---

배열을 이용한 덱의 구현

- 원형 큐와 덱은 매우 유사하므로 원형 큐를 확장하여 덱 구현 가능

- 큐에서 사용한 배열 data와 front, rear를 그대로 사용(추가 데이터 필요 x)

#define MAX_DEQUE_SIZE 5
typedef int element;
typedef struct {
	element data[MAX_DEQUE_SIZE];
    int front, rear;
} DequeType;

- is_empty(), is_full(), init_queue(), print_deque(), add_rear(), delete_front(), get_front() 등은 원형 큐 연산과 동일

- delete_rear(), add_front(), get_rear()가 새롭게 추가

 

- get_rear(): 공백상태가 아는 경우 rear가 가리키는 항목을 반환

- delete_rear(), add_front(): 원형 큐와 달리 반대 방향의 회전 필요

front = (front-1 + MAX_DEQUE_SIZE) % MAX_DEQUE_SIZE;
rear = (rear-1 + MAX_DEQUE_SIZE) % MAX_DEQUE_SIZE;

- front나 rear를 감소

- 감소시킨 값이 음수가 되면 MAX_QUEUE_SIZE를 더해주어야 함

---

덱 구현

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

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

void error(char* message) {
	fprintf(stderr, "%s\n", message);
	exit(1);
}
void init_deque(DequeType* q) {
	q->front = 0;
	q->rear = 0;
}
int is_empty(DequeType* q) {
	return (q->front == q->rear);
}
int is_full(DequeType* q) {
	return (q->front == (q->rear + 1) % MAX_DEQUE_SIZE);
}
void deque_print(DequeType* q) {
	printf("DEQUE(front=%d rear=%d) = ", q->front, q->rear);
	if (!is_empty(q)) {
		int i = q->front;
		do {
			i = (i + 1) % MAX_DEQUE_SIZE;
			printf("%d | ", q->data[i]);
			if(i==q->rear)
				break;
		} while (i != q->front);
	}
	printf("\n");
}
void add_rear(DequeType* q, element item) {
	if (is_full(q))
		error("큐가 포화 상태입니다.");
	q->rear = (q->rear + 1) % MAX_DEQUE_SIZE;
	q->data[q->rear] = item;

}
element delete_front(DequeType* q) {
	if (is_empty(q))
		error("큐가 공백 상태입니다.");
	q->front = (q->front + 1) % MAX_DEQUE_SIZE;
	return q->data[q->front];
}
element get_front(DequeType* q) {
	if (is_empty(q))
		error("큐가 공백 상태입니다.");
	return q->data[(q->front+1)%MAX_DEQUE_SIZE];
}
void add_front(DequeType* q, element val) {
	if (is_full(q))
		error("큐가 포화 상태입니다.");
	q->data[q->front] = val;
	q->front = (q->front - 1 + MAX_DEQUE_SIZE) % MAX_DEQUE_SIZE;
}
element delete_rear(DequeType* q) {
	int prev = q->rear;
	if (is_empty(q))
		error("큐가 공백 상태입니다.");
	q->rear = (q->rear - 1 + MAX_DEQUE_SIZE) % MAX_DEQUE_SIZE;
	return q->data[prev];
}
element get_rear(DequeType* q) {
	if (is_empty(q))
		error("큐가 공백 상태입니다.");
	return q->data[q->rear];
}

int main(void) {
	DequeType queue;

	init_deque(&queue);
	for (int i = 0; i < 3; i++) {
		add_front(&queue, i);
		deque_print(&queue);
	}
	for (int i = 0; i < 3; i++) {
		delete_rear(&queue);
		deque_print(&queue);
	}
	return 0;
}

>>