스택(Stack) - 링크드 리스트로 구현, C언어

스택

1. 요소의 삽입/삭제가 한쪽 끝에서만 이루어짐
2. 처음에 들어간 것이 마지막에 나오는 구조 - FILO(First In Last Out), LIFO(Last In First Out)
3. 자동 메모리, 대부분의 네트워크 프로토콜이 스택 기반

링크드 리스트를 이용하여 구현한 스택

1. 장점: 용량에 제한이 없음
2. 단점: 배열처럼 인덱스로 노드에 접근 불가능

---

0. 노드의 구조

인덱스로 노드에 접근할 수 없기 때문에, 자신의 위에 위치하는 노드에 대한 포인터를 갖고 있어야 함

typedef struct tagNode
{
	char			*data;
	struct tagNode	*next_node;
}	t_node;

---

1. 스택의 구조

리스트의 헤드(list)와 테일(top)을 가진 구조체로 표현

typedef struct tagLinnkedListStack
{
	t_node	*list;
	t_node	*top;
} t_ll_stack;

---

2. 스택 기본 연산

1. 스택 생성

void	create_stack(t_ll_stack **stack)
{
	// 스택을 힙 영역에 생성
	*stack = (t_ll_stack*)malloc(sizeof(t_ll_stack));
	(*stack)->list = NULL;
	(*stack)->top = NULL;
}

---

2. 스택 확인

// 비었는지 확인
int	is_empty(t_ll_stack *stack)
{
	if (stack->top == NULL)
		return (1);
	else
		return (0);
}

---

3. 노드 생성과 삭제

t_node	*create_node(char *str)
{
	t_node	*node;

	node = (t_node*)malloc(sizeof(t_node));
	node->data = (char*)malloc(strlen(str) + 1);
	strcpy(node->data, str);
	node->next_node = NULL;
	return (node);
}

void	destroy_node(t_node	*node)
{
	free(node->data);
	free(node);
}

---

4. Push

void	push(t_ll_stack *stack, t_node *new_node)
{
	if (is_empty(stack))
	{
		stack->list = new_node;
		stack->top = new_node;
		return ;
	}
	stack->top->next_node = new_node;
	stack->top = new_node;
}

---

5. Pop

t_node	*pop(t_ll_stack *stack)
{
	t_node	*popped;
	t_node	*prev_node;

	if (is_empty(stack))
		return (0);
	popped = stack->top;
	prev_node = find_prev_node(stack, popped);
	if (!prev_node)
	{
    	// 마지막 노드 pop
		stack->list = NULL;
		stack->top = NULL;
	}
	else {
    	// top의 이전 노드를 top으로 바꿈
		prev_node->next_node = NULL;
		stack->top = prev_node;
	}
	return (popped);
}

---

6. 스택 삭제

void	destroy_stack(t_ll_stack *stack)
{
	while (!is_empty(stack))
		destroy_node(pop(stack));
	free(stack);
}

---

7. 그외

t_node	*find_prev_node(t_ll_stack *stack, t_node *target)
{
	t_node	*prev_node;

	prev_node = stack->list;
    // 스택에 노드가 하나만 남았거나 가장 밑의 노드가 타겟일 때
	if (prev_node == stack->top || stack->list == target)
		return (0);
	while (prev_node->next_node != target)
		prev_node = prev_node->next_node;
	return (prev_node);
}

void	print_stack(t_ll_stack *stack)
{
	t_node	*curr_node;

	curr_node = stack->top;
	puts("현재 노드 주소\t데이터\t다음 노드 주소");
	while (curr_node != NULL)
	{
		printf("[%p] %s [%p]\n", curr_node, curr_node->data, curr_node->next_node);
		curr_node = find_prev_node(stack, curr_node);
	}
}

---

8. 예시

int	main(void)
{
	t_ll_stack	*stack;

	create_stack(&stack);
	push(stack, create_node("1"));
	push(stack, create_node("2"));
	push(stack, create_node("3"));
	puts("------");
	print_stack(stack);
	destroy_node(pop(stack));
	puts("------");
	print_stack(stack);
	destroy_node(pop(stack));
	push(stack, create_node("asdf"));
	puts("------");
	print_stack(stack);
	destroy_node(pop(stack));
	puts("------");
	print_stack(stack);
	destroy_stack(stack);
	return (0);
}