자료구조 (데크)

---

참고자료

https://jung-story.tistory.com/23?category=826491 

자료구조 (순차 스택)

https://jung-story.tistory.com/24?category=826491 

자료구조 (연결 스택)

https://jung-story.tistory.com/25?category=826491 

자료구조 (원형 큐)

https://jung-story.tistory.com/26?category=826491 

자료구조 (연결 큐)

 

---

개요

 

이번에는 자료구조의 데크에 대해서 배워보도록 하겠습니다.

 

---

데크 란?

 

덱(deque, "deck"과 발음이 같음 ←double-ended queue)은 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료 구조의 한 형태이다.

두 개의 포인터를 사용하여, 양쪽에서 삭제와 삽입을 발생시킬 수 있습니다.

https://jung-story.tistory.com/26(큐) 와

https://jung-story.tistory.com/23(스택)을 합친 형태로 생각할 수 있습니다.

 

---

데크 구현

 

#include <stdio.h>
#include <malloc.h>

typedef char element;
typedef struct DQNode {
	struct DQNode* llink;
	struct DQNode* rlink;
	element data;
}DQNode;
typedef struct {
	DQNode* front, * rear;
}DQType;

DQType* createDq() {
	DQType* DQ;
	DQ = (DQType*)malloc(sizeof(DQType));
	DQ->front = NULL;
	DQ->rear = NULL;
	return DQ;
}
int isEmpty(DQType* DQ) {
	if (DQ->front == NULL) {
		return 1;
	}
	else {
		return 0;
	}
}

void insertfront(DQType* DQ, element item) {
	DQNode* newnode = malloc(sizeof(DQNode));
	newnode->data = item;
	if (DQ->front == NULL) {
		DQ->front = newnode;
		DQ->rear = newnode;
		newnode->llink = NULL;
		newnode->rlink = NULL;
	}
	else {
		DQ->front->llink = newnode;
		newnode->llink = NULL;
		newnode->rlink = DQ->front; // 새로만든 newnode의 rlink에 원래있던 front노드 대입해준다.
		DQ->front = newnode;	// DQ가 가리키는 front노드를 newnode로 설정해준다!.
	}
}
void insertrear(DQType* DQ, element item) {
	DQNode* newnode = malloc(sizeof(DQNode));
	newnode->data = item;
	if (DQ->rear == NULL) {
		DQ->front = newnode;
		DQ->rear = newnode;
		newnode->llink = NULL;
		newnode->rlink = NULL;
	}
	else {
		DQ->rear->rlink = newnode;
		newnode->rlink = NULL;
		newnode->llink = DQ->rear;
		DQ->rear = newnode;
	}
}

void ShowInfo(DQType* DQ) {
	DQNode* temp = DQ->front;
	while (temp) {
		printf("%3c , ", temp->data);
		temp = temp->rlink;
	}

}

element deletfront(DQType* DQ) {
	DQNode* old = DQ->front;
	element item;
	if (isEmpty(DQ)) {

		return 0;

	}
	else {
		item = old->data;
		if (DQ->front->rlink == NULL) {
			DQ->front = NULL;
			DQ->rear = NULL;

		}
		else {
			DQ->front = DQ->front->rlink;	// 현재 front노드의 오른쪽에 노드가 있다면 포인터front를 오른쪽 노드로 이동한다.
			DQ->front->llink = NULL;	// 삭제할 노드와의 연결을 해지한다.

		}
		free(old);
	}
	return item;
}
element deletrear(DQType* DQ) {
	DQNode* old = DQ->rear;
	element item;

	if (isEmpty(DQ)) {
		return 0;
	}
	else {
		item = old->data;

		if (DQ->rear->llink == NULL) {
			DQ->front = NULL;
			DQ->rear = NULL;
		}
		else {

			DQ->rear = DQ->rear->llink;
			DQ->rear->rlink = NULL;

		}
		free(old);
		return item;
	}


}


void main() {
	DQType* DQ = createDq();
	element data;
	insertfront(DQ, 'A');
	insertfront(DQ, 'B');
	insertrear(DQ, 'C');
	insertfront(DQ, 'D');
	deletfront(DQ);
	deletrear(DQ);
	ShowInfo(DQ);

}

 

---

실행화면

front로 A,B,D를 삽입 rear로 C를 삽입 front 1개삭제 rear 1개 삭제 시

 

---