[Data Structure] 덱 (Deque)

덱 (Deque - Double Ended Queue)

- 큐(Queue) : 전단(front)에서 삭제, 후단(rear)에서 삽입

- 덱(Deque) : 큐의 전단(front), 후단(rear)에서 모두 삽입/삭제 가능

 

 

※ Example

- delete_rear / add_front

- MAX_DEQUE_SIZE = 5

front	rear	과정
0	0	Deque 초기화
0	1	add_rear
0	2	add_rear (1)
4	2	add_front (2)
3	2	add_front → 포화
4	2	delete_front
0	2	delete_front (3)
0	1	delete_rear (4)
0	0	delete_rear → 공백

(1) → (2)

front에서 add를 하려면 원래 front 인덱스에 item을 add 시키고, front를 한 칸 뒤로 옮기기(front - 1)

• → front - 1이 음수일 경우, (front-1)에다가 MAX_DEQUE_SIZE를 더하기 → (front-1+MAX_DEQUE_SIZE)
• 더한 값(front-1+MAX_DEQUE_SIZE)을 MAX_DEQUE_SIZE로 나눈 나머지 = front 인덱스 값

∴ add_front를 거친 front의 다음 인덱스 = (front-1+MAX_DEQUE_SIZE)%MAX_DEQUE_SIZE 

(3) → (4)

add_front와 마찬가지로, delete_rear은 현재 rear 인덱스에 있는 item을 다른 변수에 보관

• → 보관하고, rear를 한 칸 뒤로 옮기기(rear-1)

∴ delete_rear를 거친 rear의 다음 인덱스 = (rear-1+MAX_DEQUE_SIZE)%MAX_DEQUE_SIZE 

 

 

1.add_rear (int rear)

- 큐의 enqueue와 동일한 알고리즘

void add_rear(deque* d, element item) {
	// 큐의 enqueue와 동일
	if (is_full(d)) {
		fprintf(stderr, "Error : Deque is full\n");
		return;
	}
	else {
		d->rear = (d->rear + 1) % MAX_DEQUE_SIZE;
		d->deque[d->rear] = item;
	}
}

 

 

2. add_front (int front)

- 현재 front 인덱스에 item을 삽입

• → 삽입 후, front를 1칸 뒤로 옮기기 (front-1)

void add_front(deque* d, element item) {
	// front에 item을 넣고 front를 1칸 뒤로 설정
	if (is_full(d)) {
		fprintf(stderr, "Error : Deque is full\n");
		return;
	}
	else {
		d->deque[d->front] = item;
		d->front = (d->front - 1 + MAX_DEQUE_SIZE) % MAX_DEQUE_SIZE;
		/* 
		d->front - 1 의 결과가 음수일 경우, MAX_DEQUE_SIZE를 더하고,
		더한 최종 결과에 MAX_DEQUE_SIZE로 나눠준다
		*/
	}
}

 

 

3. delete_rear (int rear)

element delete_rear(deque* d) {
	// d->rear에 있는 item을 따로 보관하고, d->rear을 1칸 뒤로 옮긴다
	if (is_empty(d)) {
		fprintf(stderr, "Error : Deque is empty\n");
		return;
	}
	else {
		element item = d->rear;
		d->rear = (d->rear - 1 + MAX_DEQUE_SIZE) % MAX_DEQUE_SIZE;
		return d->deque[item];
	}
}

 

 

4. delete_front (int front)

- 큐의 dequeue와 동일한 알고리즘

element delete_front(deque* d) {
	// 큐의 dequeue와 동일
	if (is_empty(d)) {
		fprintf(stderr, "Error : Deque is empty\n");
		return;
	}
	else {
		d->front = (d->front + 1) % MAX_DEQUE_SIZE;
		return d->deque[d->front];
	}
}

 

 

5. Full Code (Deque With Array)

#include <stdio.h>
#include <stdlib.h>
#define MAX_DEQUE_SIZE 5
// 덱 (원형으로 구현)

typedef int element;

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

int size(deque *d){
	return MAX_DEQUE_SIZE;
}

void init_deque(deque* d) {
	d->front = d->rear = 0;
}

int is_full(deque* d) {
	return d->front == (d->rear + 1) % MAX_DEQUE_SIZE;
}

int is_empty(deque* d) {
	return d->front == d->rear;
}

void add_rear(deque* d, element item) {
	// 큐의 enqueue와 동일
	if (is_full(d)) {
		fprintf(stderr, "Error : Deque is full\n");
		return;
	}
	else {
		d->rear = (d->rear + 1) % MAX_DEQUE_SIZE;
		d->deque[d->rear] = item;
	}
}

void add_front(deque* d, element item) {
	// front에 item을 넣고 front를 1칸 뒤로 설정
	if (is_full(d)) {
		fprintf(stderr, "Error : Deque is full\n");
		return;
	}
	else {
		d->deque[d->front] = item;
		d->front = (d->front - 1 + MAX_DEQUE_SIZE) % MAX_DEQUE_SIZE;
		/* 
		d->front - 1 의 결과가 음수일 경우, MAX_DEQUE_SIZE를 더하고,
		더한 최종 결과에 MAX_DEQUE_SIZE로 나눠준다
		*/
	}
}

element delete_rear(deque* d) {
	// d->rear에 있는 item을 따로 보관하고, d->rear을 1칸 뒤로 옮긴다
	if (is_empty(d)) {
		fprintf(stderr, "Error : Deque is empty\n");
		return;
	}
	else {
		element item = d->rear;
		d->rear = (d->rear - 1 + MAX_DEQUE_SIZE) % MAX_DEQUE_SIZE;
		return d->deque[item];
	}
}

element delete_front(deque* d) {
	// 큐의 dequeue와 동일
	if (is_empty(d)) {
		fprintf(stderr, "Error : Deque is empty\n");
		return;
	}
	else {
		d->front = (d->front + 1) % MAX_DEQUE_SIZE;
		return d->deque[d->front];
	}
}

element peek_rear(deque* d) {
	if (is_empty(d)) {
		fprintf(stderr, "Error : Deque is empty\n");
		return;
	}
	else 
		return d->deque[d->rear];
}

element peek_front(deque* d) {
	if (is_empty(d)) {
		fprintf(stderr, "Error : Deque is empty\n");
		return;
	}
	else 
		return d->deque[(d->front + 1) % MAX_DEQUE_SIZE];
}

void deque_print(deque* d) {
	printf("DEQUE(front=%d rear=%d) = ", d->front, d->rear);
	if (!is_empty(d)) {
		element item = d->front;
		do {
			item = (item + 1) % MAX_DEQUE_SIZE;
			printf("%d |	", d->deque[item]);
			if (item == d->rear)
				break;
		} while (item != d->front);
	}
	printf("\n");
}

int main(void) {
	deque d;
	init_deque(&d);

	printf("Deque Size : %d\n\n", size(&d));

	printf(">>> add_rear 10\n"); add_rear(&d, 10); deque_print(&d);
	printf("\n>>> add_rear 20\n"); add_rear(&d, 20); deque_print(&d);
	printf("\n>>> add_front 30\n"); add_front(&d, 30); deque_print(&d);
	printf("\n>>> add_front 40\n"); add_front(&d, 40); deque_print(&d);
	printf("\n>>> add_front 50\n"); add_front(&d, 50); deque_print(&d);

	printf("\n>>> peek_rear\n"); printf("%d\n", peek_rear(&d));
	printf("\n>>> peek_front\n"); printf("%d\n", peek_front(&d));

	printf("\n>>> delete_rear\n"); delete_rear(&d); deque_print(&d);
	printf("\n>>> delete_rear\n"); delete_rear(&d); deque_print(&d);
	printf("\n>>> delete_front\n"); delete_front(&d); deque_print(&d);
	printf("\n>>> delete_front\n"); delete_front(&d); deque_print(&d);
	printf("\n>>> delete_front\n"); delete_front(&d); deque_print(&d);
}