자료구조 : 덱

참고문헌 :

 

m.blog.naver.com/PostView.nhn?blogId=isaac7263&logNo=221507063144&proxyReferer=https:%2F%2Fwww.google.com%2F

[자료구조] 덱(Deque)의 이해와 구현

jjudrgn.tistory.com/15

자료구조 : 덱(deque)

ldgeao99.tistory.com/249

챕터2-3. 자료구조 | 덱(Deque)

 

---

1. 덱 (Deque)

1.1 정의 : deque( Double-ended Queue )로 양쪽 끝에서 삽입과 삭제가 가능한 자료구조입니다.

 

1.2 메서드 종류

- push_front : 덱의 앞에 데이터 추가

- push_back : 덱의 뒤에 데이터 추가

- pop_front : 덱의 앞에서 데이터 제거

- pop_back : 덱의 뒤에서 데이터 제거

 

---

2. 구현하기

덱을 구현할 때 주로 이중 연결 리스트(Doubly-linked List)를 사용하여 구현을 하지만 해당 포스트에서는 원형 큐를 사용하여 구현하도록 하겠습니다.

 

C99

#include<stdio.h>
#include<Windows.h>

#define MAX_SIZE 20

typedef int element;

typedef struct _deque{
	element data[MAX_SIZE];
	int front, rear;
}deque;

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

	for (int i = 0; i < MAX_SIZE; i++)
		q->data[i] = 0;
}

int isEmpty(deque q) {
	return q.front == q.rear ? 1 : 0;
}

int isFull(deque q) {
	return (q.rear + 1) % MAX_SIZE == q.front ? 1 : 0;
}

void push_front(deque* q, element data) {
	if (isFull(*q)) {
		fprintf(stderr, "deque is full!");
		exit(1);
	}
	q->data[q->front--] = data;
	q->front = (q->front + MAX_SIZE) % MAX_SIZE;
}

void push_rear(deque* q, element data) {
	if (isFull(*q)) {
		fprintf(stderr, "deque is full!");
		exit(1);
	}
	q->rear = (q->rear + 1) % MAX_SIZE;
	q->data[q->rear] = data;
}

element pop_front(deque* q) {
	if (isEmpty(*q)) {
		fprintf(stderr, "deque is empty!");
		exit(1);
	}
	q->front = (q->front + 1) % MAX_SIZE;
	return q->data[q->front];
}

element pop_rear(deque* q) {
	element val;
	if (isEmpty(*q)) {
		fprintf(stderr, "deque is empty!");
		exit(1);
	}
	val = q->data[q->rear];
	q->rear = (q->rear - 1 + MAX_SIZE) % MAX_SIZE;
	return val;
}