데크 Deque

이번에 소개할 자료구조는 데크(덱)입니다. 어떤 문서에서는 데크, 다른 문서에서는 덱이라고 하길래 저는 제가 배웠던 '데크'라는 명칭으로 소개하려고합니다.

---

1. 데크

데크는 새로운 자료구조 같지만 큐의 변형 자료구조 중 하나입니다. 데크의 의미는 Double Ended Queue로써 끝이 2개인 큐를 의미합니다. 기존의 큐는 아래 그림처럼 한 끝에서만 삽입, 다른 한 끝에서만 삭제가 이루어졌습니다. 하지만 데크는 양 쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조입니다. 한 가지 착각 하지 말아야 하는 점은 연결 리스트처럼 중간 삭제는 불가능하고 스택과 큐처럼 자료구조 양 끝에서만 삽입 삭제가 이루어 진다는 점입니다.

큐

데크

구현 방식은 데크의 특징을 잘 생각해서 다음 두가지만 명심하고 구현하면됩니다.

• front에서 삭제와 삽입
• rear에서 삭제와 삽입

 

 

 

2. 데크의 구현

2-1. 노드 구성

데크는 양방향의 성격을 띄고있습니다. 그래서 이중 연결리스트와 유사한 듯한 느낌도 있는데요. 노드 구성이 이중 연결 리스트 처럼 데이터 필드 양옆에 링크 필드를 가지고 있습니다.

typedef struct DequeNode {
	element data;
	struct DequeNode* leftLink;
	struct DequeNode* rightLink;
}DequeNode;

 

 

2-2. 인큐

언급했듯이 front와 rear 양쪽에서 인큐/디큐가 이루어지므로, 두 개의 함수가 만들어져야합니다. 우선 front 인큐를 보겠습니다.

int insertFront(DequeType* DQ, element elem) {
	DequeNode* newNode = (DequeNode*)malloc(sizeof(DequeNode));

	newNode->data = elem;

	if (DQ->front == NULL) { //front가 비어있다면, 즉 첫 노드라면
		DQ->front = newNode;	
		DQ->rear = newNode;	//front와 rear가 인큐된 노드이며,

		newNode->rightLink = NULL;
		newNode->leftLink = NULL;	//가리키고 있는 다른 노드는 없다.
	}
	else {
    		//프론트로 삽입
        	//삽입 이전 프론트의 왼쪽 링크가 새노드를 가리키게한다.
		DQ->front->leftLink = newNode;

		newNode->rightLink = DQ->front;	//새 노드의 오른쪽 링크는 이전 front를 가리키게한다.
		newNode->leftLink = NULL;

		DQ->front = newNode; //마지막으로 front를 삽입한 노드로 설정
	}
}

그림으로 인큐과정을 그려보았습니다.

그러면 반대로 rear에서 인큐하는 과정을 보겠습니다.

void insertRear(DequeType* DQ, element elem) {
	DequeNode* newNode = (DequeNode*)malloc(sizeof(DequeNode));

	newNode->data = elem;

	if (DQ->rear == NULL) {
		DQ->front = newNode;
		DQ->rear = newNode;

		newNode->rightLink = NULL;
		newNode->leftLink = NULL;
	}
	else {
		DQ->rear->rightLink = newNode;

		newNode->rightLink = NULL;
		newNode->leftLink = DQ->rear;

		DQ->rear = newNode;
	}
}

 

2-3. 디큐

void deleteFront(DequeType* DQ) {	//front에서 디큐 실행
	DequeNode* oldNode = DQ->front;
	
	if (isEmpty(DQ)) {
		return 0;
	}
	else {
		if (DQ->front->rightLink == NULL) { //front노드가 유일한 노드일 때
			DQ->front = NULL;
			DQ->rear = NULL;
		}
		else {
        		//front를 front의 다음 노드로 설정
			DQ->front = DQ->front->rightLink;
            		//front 왼쪽 링크필드를 비움. 즉, 왼쪽 링크는 아무것도 안가리키게 된다.
			DQ->front->leftLink = NULL;
		}

		free(oldNode);

		return 0;
	}
}

else문 부분을 그림으로 표현했습니다. front를 이동시키고 연결을 끊음으로써 삭제가 됩니다.

element deleteRear(DequeType* DQ) {
	DequeNode* oldNode = DQ->rear;

	if (isEmpty(DQ)) {
		return 0;
	}
	else {
		if (DQ->rear->leftLink == NULL) {
			DQ->front = NULL;
			DQ->rear = NULL;
		}
		else {
			DQ->rear = DQ->rear->leftLink;
			DQ->rear->rightLink = NULL;
		}

		free(oldNode);

		return 0;
	}
}

 

2-4. 피크

피크도 마찬가지로 front의 요소를 보는 피크와 rear의 요소를 보는 피크로 나뉩니다.

element peekFront(DequeType* DQ) {
	element elem;

	if (isEmpty(DQ)) {
		return 0;
	}
	else {
		return elem = DQ->front->data;
	}
}

element peekRear(DequeType* DQ) {
	element elem;

	if (isEmpty(DQ)) {
		return 0;
	}
	else {
		return elem = DQ->rear->data;
	}
}

간단하게도, front피크라면 front의 데이터를, rear피크라면 rear의 데이터를 return 하면 됩니다.

---

https://github.com/Bam-j/DataStructure/blob/main/DataStructure/Deque.c

GitHub - Bam-j/DataStructure: 블로그와 함께 가는 자료구조