문과생이 이해한 덱(deque- double-ended queue)

출처 : <c언어로 쉽게 풀어쓴 자료구조> + 학교 수업

 

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

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

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

int is_empty(DequeType* q) {
	return (q->front == q->rear);
}

int is_full(DequeType* q) {
	return ((q->rear+1)%MAX==q->front);
}

void deque_print(DequeType* q) {
	printf("Deque (front = %d, rear = %d) = ", q->front, q->rear);
	if (is_empty(q)) return;

	int i = q->front;
	do {
		i = (i + 1) % MAX;
		printf("%d  ", q->data[i]);
		if (i == q->rear) break;
	} while (i != q->front);
	
	printf("\n\n");
}

void add_rear(DequeType* q, int item) {
	if (is_full(q))
		fprintf(stderr, "큐가 포화 상태입니다.\n");
	q->rear = (q->rear + 1) % MAX;
	q->data[q->rear] = item;
}

int delete_front(DequeType* q) {
	if (is_empty(q))
		fprintf(stderr, "큐가 공백상태입니다.\n");
	q->front = (q->front + 1) % MAX;
	return q->data[q->front];
}

void add_front(DequeType* q, int val) {
	if(is_full(q))
		fprintf(stderr, "큐가 포화 상태입니다\n");
	q->data[q->front] = val;
	q->front = (q->front - 1 + MAX) % MAX;
}

int delete_rear(DequeType* q) {
	int prev = q->rear;
	if(is_empty(q))
		fprintf(stderr, "큐가 공백상태입니다.\n");
	q->rear = (q->rear - 1 + MAX) % MAX;
	return q->data[prev];
}

int main() {
	DequeType queue;
	init_deque(&queue);
	for (int i = 0; i < 3; i++) {
		add_front(&queue, i);
		deque_print(&queue);
		printf("\n");
	}

	for (int i = 0; i < 3; i++) {
		delete_rear(&queue);
		deque_print(&queue);
		printf("\n");
	}

	return 0;
}

 

덱 : 큐의 전단과 후단에서 모두 삽입과 삭제가 가능한 큐

 

 덱은.. 그냥 이중 연결리스트라고 봐도 될 듯... 사실 연결된 스택~ 연결된 큐하면서 이 정도면 그냥 연결리스트 아닌가...? 하는 생각이 종종 든다. 

 

 그리고 지금 트리하는데 엿 된 거 같음.. 

 

 

#main()

 

 덱은 원형 큐로 구현한댜...

 

 

~여기서 잠깐~

 삽입할 때 rear는 원래 큐가 넣는 방향대로 front는 뒤로간다!

 

 

#add_front

 

 일단 front(전단)은 원래 출력만 했던 녀석이엇쥬? 근데 이제 삽입/입력도 할거임ㅇㅇ 일단 큐가 full인지 아닌지 확인하고

 

 

 뀨? 일단 full()이 아니니까 남은 건 삽입 연산..후후후

 

 일단 rear와 다르게 일단 값을 넣어주고 시작한다. 왜? print할 때 front부터 시작하니까 한 칸 후진시켜놓는거다.

 

 저 54번째 코드와 덱을 print하는 함수가 아마 덱의 하이라이트가 아닐까 싶다. 현재 MAX는 5. q->front는 0이니까, 연산을 하면 4가 나온다.

 

 요로케!!! 한 번 더 삽입 연산하면

 

 

 요러케 되겠쥬? 

 

 

#delete_front

 

  main문 연산은 아니지만 소개하겟다. 

 일단 메모리 기본 상태! 연산은 스스로!!!

 

 

#add_rear

 

 

#delete_rear

 delete_rear니까 rear가 역으로 가겠쥬?

 

 요러케 하면 prev에 저장된(빨간색 표시) 부분이 삭제됩니당

 

 

#deque_print

 일단 메모리 상태는 이거라고 가정해보자. 3번째 Deque를 출력하는거다. 

 

 자 여기까지 출력하고 나면 i==q->rear가 되므로 while문을 탈출하게 된다. 

 

 

<출력창>