자료구조

push_swap은 스택을 구성하고 과제에 필요한 명령어를 수행할 수 있는 코드를 작성해야 합니다.
기본적으로 stack은 FILO(first in last out)특성을 가지는 자료구조이지만 push_swap에서는 rotate와 reverse rotate를 수행할 수 있어야 하므로 double linked list형태의 circular queue가 가장 적합합니다.

double linked list는 각 node가 다음node와 이전node의 포인터를 가지고 있습니다. list를 circular로 구성하기 위해서는 top의 prev는 bottom을 가리키고 bottom의 next는 top을 가리켜야 합니다. 따라서 node와 stack 구조체는 다음과 같이 구성할 수 있습니다.

typedef struct	s_node
{
	int				value;
    struct s_node	*next;
    struct s_node	*prev;
}	t_node;

typedef struct s_stack
{
	size_t	len;
    t_node	*top;
}	t_stack;

이제 이 stack을 다룰 수 있는 기본적인 함수 몇 가지를 작성해 봅시다.
pointer를 사용하는 stack인 만큼 몇 가지 규칙을 엄밀히 지킬 수 있어야 합니다.

• node가 어떤 것과도 연결되어있지 않을 때 next와 prev는 NULL일 것
• stack의 길이가 0일 때 top은 NULL일것
• stack의 길이가 0일 때 top의 next와 prev는 자기 자신일 것

int		init_stack(t_stack *stack);
int		destry_stack(t_stack *stack);
int		push_node(t_stack *stack, t_node *node);
int		pop_node(t_stack *stack, t_node **node_ptr);
int		push_value(t_stack *stack, int value);
int		pop_value(t_stack *stack, int *value_ptr);

위에서 언급한 규칙 외에 stack의 함수는 stack을 항상 포인터 형식으로 받을것, int형 반환값을 통해 함수의 수행 결과를 나타낼것, 반환해야 하는 자료는 포인터를 받아 값을 담을것 등의 통일성을 주었습니다.

push_swap에서는 rotate, reverse rotate, 정렬을 수행해야 하므로 몇 가지 함수를 추가하도록 하겠습니다.

int		rotate(t_stack *stack);
int		reverse_rotate(t_stack *stack);
int		is_sorted(t_stack *stack);
int		is_rev_sorted(t_stack *stack);
int		to_array(t_stack *stack, int **array_ptr);
int		print_stack(t_stack *stack);

자세한 코드는 아래의 github에서 보실 수 있습니다.
42sangkkim_github