[push_swap] Deque 만들기

Deque란?

Double Ended Queue라는 이름처럼 기존의 큐와 다르게 앞,뒤에서 바로 자료를 넣고 뺄 수 있는 구조

Deque를 선택한 이유

• push_swap에서 값들을 계속 넣고 빼고 하기에는 양방향연결리스트를 사용하는것이 가장 편할듯 함
• ra, rb, rr등의 필요 기능들을 구현할때 리스트의 가장 앞과 가장 뒤에서 값을 넣고 뺄 수 있는 deque형식을 사용하는것이 가장 편할것 같았으므로 deque를 사용하게 되었음

구현해야 할것

• 처음과 마지막 노드를 알 수있는 t_deque 구조체
• deque 내부에서 특정 값과 이전, 다음 노드의 주소를 가지고있을 t_node 구조체
• deque의 앞에 새로운 노드를 추가할 push_node_front 함수
• deque의 끝에 새로운 노드를 추가할 push_node_back 함수
• deque의 가장 앞에있는 노드를 없에주는 pop_node_front 함수
• deque의 가장 끝에있는 노드를 없에주는 pop_node_back 함수

주의사항

• 노드들을 새로 추가하거나 삭제할 때에 이전, 또는 다음 노드와의 연결을 다시 지정해주어야함
• 비어있는 deque에 노드를 추가하거나 삭제로인해 deque에 노드가 하나만 남거나 비게될 경우 deque의 first와 last를 잘 설정해주어야함

구현

기본 구조체

typedef struct s_node
{
	int				num; // 값
	struct s_node	*prev; //이전 노드
	struct s_node	*next; //다음 노드
}	t_node;

typedef struct s_deque
{
	t_node	*first; // deque의 첫 노드
	t_node	*last; // deque의 마지막 노드
}	t_deque;

Push

int	push_node_back(t_deque *deq, int num)
{
	t_node	*new_node;

	if (check_duplicate(deq, num))
		return (1);
	new_node = malloc(sizeof(t_node));
	if (new_node == NULL)
		return (1);
	new_node->num = num;
	new_node->next = NULL;
	new_node->prev = deq->last;
	if (deq->last == NULL && deq->first == NULL)
	{
		deq->last = new_node;
		deq->first = new_node;
	}
	else
	{
		if (deq->last != NULL)
			deq->last->next = new_node;
		deq->last = new_node;
	}
	return (0);
}

int	push_node_front(t_deque *deq, int num)
{
	t_node	*new_node;

	if (check_duplicate(deq, num))
		return (1);
	new_node = malloc(sizeof(t_node));
	if (new_node == NULL)
		return (1);
	new_node->num = num;
	new_node->prev = NULL;
	if (deq->first == NULL)
	{
		deq->first = new_node;
		deq->last = new_node;
		new_node->next = NULL;
	}
	else
	{
		deq->first->prev = new_node;
		new_node->next = deq->first;
		deq->first = new_node;
	}
	return (0);
}

pop

int	pop_node_front(t_deque *deq)
{
	t_node	*save;

	if (deq->first == NULL)
		return (0);
	save = deq->first->next;
	free(deq->first);
	if (save == NULL)
	{
		deq->first = save;
		deq->last = save;
		return (1);
	}
	deq->first = save;
	save->prev = NULL;
	return (1);
}

int	pop_node_back(t_deque *deq)
{
	t_node	*save;

	if (deq->last == NULL)
		return (0);
	save = deq->last->prev;
	free(deq->last);
	if (save == NULL)
	{
		deq->first = save;
		deq->last = save;
		return (1);
	}
	deq->last = save;
	save->next = NULL;
	return (0);
}