데크

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

데크의 구현

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

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

노드 정의

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

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

인큐

언급했듯이 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;
	}
}

디큐

디큐도 역시 front와 rear 양끝단에서 각자 이루어집니다.

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문 내부의 동작을 그림으로 나타내면 다음과 같습니다.
이번엔 rear의 디큐를 보겠습니다.

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;
	}
}

피크

피크도 마찬가지로 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 하면 됩니다.

---

전체 코드는 GitHub에서 확인하실 수 있습니다.