개념

Deque (Double-Ended Queue)

• 프런트와 리어 모두에서 추가, 삭제 연산이 가능한 자료구조

연산

• 덱 생성, 덱 삭제
• 앞 추가, 뒤 추가, 앞 제거, 뒤 제거, 앞 반환, 뒤 반환

구현

• Double linked list로 구현
• 헤드 노드는 프런트, 리어 노드의 주소를 가짐

구조체와 함수 원형

typedef struct DequeNodeType
{
	char					data;
	struct DequeNodeType*	pRLink;
	struct DequeNodeType*	pLLink;
}	DequeNode;

typedef struct LinkedDequeType
{
	int			currentElementCount;	// 현재 원소의 개수
	DequeNode*	pFrontNode;				// Front 노드의 포인터
	DequeNode*	pRearNode;				// Rear 노드의 포인터
}	LinkedDeque;

LinkedDeque*	createLinkedDeque();
int				insertFrontLD(LinkedDeque* pDeque, DequeNode element);
int				insertRearLD(LinkedDeque* pDeque, DequeNode element);
DequeNode*		deleteFrontLD(LinkedDeque* pDeque);
DequeNode*		deleteRearLD(LinkedDeque* pDeque);
DequeNode*		peekFrontLD(LinkedDeque* pDeque);
DequeNode*		peekRearLD(LinkedDeque* pDeque);
void			deleteLinkedDeque(LinkedDeque* pDeque);
int				isLinkedDequeEmpty(LinkedDeque* pDeque);
void			displayLinkedDeque(LinkedDeque *pDeque);

덱 생성

LinkedDeque*	createLinkedDeque()
{
	LinkedDeque	*deque;

	deque = (LinkedDeque *)malloc(sizeof(LinkedDeque));
	if (deque == NULL)
		return (NULL);
	deque->currentElementCount = 0;
	deque->pFrontNode = NULL;
	deque->pRearNode = NULL;
	return (deque);
}

앞 추가

빈 덱인 경우

• 새 노드가 프론트이자 리어
• 새 노드의 오른쪽, 왼쪽 모두 NULL을 가리킴

아닌 경우

1. 현재 프론트 노드의 왼쪽은 새 노드를 가리킴
2. 새 노드의 오른쪽은 현재 프론트 노드를 가리킴
3. 헤드 노드의 프론트 노드는 새 노드를 가리킴

int	insertFrontLD(LinkedDeque* pDeque, DequeNode element)
{
	DequeNode	*new;

	new = (DequeNode *)malloc(sizeof(DequeNode));
	if (new == NULL)
		return (FALSE);
	*new = element;
	if (isLinkedDequeEmpty(pDeque) == TRUE)
	{
		new->pLLink = NULL;
		new->pRLink = NULL;
		pDeque->pFrontNode = new;
		pDeque->pRearNode = new;
	}
	else
	{
		new->pLLink = NULL;
		new->pRLink = pDeque->pFrontNode;
		pDeque->pFrontNode->pLLink = new;
		pDeque->pFrontNode = new;
	}
	pDeque->currentElementCount++;
	return (TRUE);
}

뒤 추가

빈 덱인 경우

• 새 노드가 프론트이자 리어
• 새 노드의 오른쪽, 왼쪽 모두 NULL을 가리킴

아닌 경우

1. 현재 리어 노드의 오른쪽은 새 노드를 가리킴
2. 새 노드의 왼쪽은 현재 리어 노드를 가리킴
3. 헤드 노드의 리어 노드는 새 노드를 가리킴

int	insertRearLD(LinkedDeque* pDeque, DequeNode element)
{
	DequeNode	*new;

	new = (DequeNode *)malloc(sizeof(DequeNode));
	if (new == NULL)
		return (FALSE);
	*new = element;
	if (isLinkedDequeEmpty(pDeque) == TRUE)
	{
		new->pLLink = NULL;
		new->pRLink = NULL;
		pDeque->pFrontNode = new;
		pDeque->pRearNode = new;
	}
	else
	{
		new->pRLink = NULL;
		new->pLLink = pDeque->pRearNode;
		pDeque->pRearNode->pRLink = new;
		pDeque->pRearNode = new;
	}
	pDeque->currentElementCount++;
	return (TRUE);
}

앞 제거

공통

1. 반환할 노드는 현재 프론트 노드
2. 헤드 노드의 프론트 노드는 현재 프론트 노드의 오른쪽 노드
3. 반환할 노드의 오른쪽은 NULL을 가리킴

노드가 1개인 경우

헤드 노드와 리어 노드는 NULL

아닌 경우

새로운 프론트 노드의 왼쪽은 NULL을 가리킴

DequeNode*	deleteFrontLD(LinkedDeque* pDeque)
{
	DequeNode	*ret;

	ret = peekFrontLD(pDeque);
	if (ret == NULL)
		return (NULL);
	if (pDeque->currentElementCount == 1)
	{
		pDeque->pFrontNode = NULL;
		pDeque->pRearNode = NULL;
	}
	else
	{
		pDeque->pFrontNode = ret->pRLink;
		pDeque->pFrontNode->pLLink = NULL;
	}
    ret->pRLink = NULL;
	pDeque->currentElementCount--;
	return (ret);
}

뒤 제거

공통

1. 반환할 노드는 현재 리어 노드
2. 헤드 노드의 리어 노드는 현재 리어 노드의 왼쪽 노드
3. 반환할 노드의 왼쪽은 NULL을 가리킴

노드가 1개인 경우

헤드 노드의 프론트 노드는 NULL

아닌 경우

새로운 리어 노드의 오른쪽은 NULL을 가리킴

DequeNode*	deleteRearLD(LinkedDeque* pDeque)
{
	DequeNode	*ret;

	ret = peekRearLD(pDeque);
	if (ret == NULL)
		return (NULL);
	if (pDeque->currentElementCount == 1)
	{
		pDeque->pFrontNode = NULL;
		pDeque->pRearNode = NULL;
	}
	else
	{
		pDeque->pRearNode = ret->pLLink;
		pDeque->pRearNode->pRLink = NULL;
	}
	ret->pLLink = NULL;
	pDeque->currentElementCount--;
	return (ret);
}

🔗 이중 연결 리스트로 구현한 덱 전체 코드