Stack

자료 구조 중에서 데이터와 링크로 구성된 연결 리스트(Linked List)라는 것이 있다. 이 연결리스트를 어떻게 활용하여 만드느냐에 따라서 여러 자료 구조를 만들 수 있다. 이번엔 그 중에서 Stack에 대해서 얘기하겠다.

Stack(스택)

• 리스트형 데이터 구조 중에서 한 쪽에서만 데이터를 추가하고 삭제할 수 있는 LIFO(Last In First Out; 선입후출)식 데이터 구조이다.
• 벽돌을 쌓는것 처럼 표시하여 가장 먼저 들어온 데이터를 밑에, 가장 늦게 들어온 데이터를 제일 위에 쌓는다.
• 스택의 제일 위를 top, 제일 밑을 bottom이라고 한다.

스택의 구현 종류

• 배열을 활용한 스택
  • 배열을 활용할 시 고정 크기이므로 크기를 범위를 벗어날 수도 있다.
    • 배열이 사용 가능한 범위를 이상 구역을 접근하려고 할 때, Segmentation Fault가 발생하는데, 이를 스택 오버플로우(Stack Overflow)라고 한다.
    • 또한 범위 이하의 구역을 접근하려고 할때 Segmentation Fault가 발생하면, 스택 언더플로우(Stack Underflow)라고 한다.
• 링크드 리스트를 활용한 스택
  • 가변 크기이므로 왠만해서는 크기를 잘 벗어나지 않는다.
  • 하지만 전체 메모리 크기보다 큰 메모리를 할당하게 되면 터질 수도 있다.
• stack의 구현 방식에 따라 stack의 연산들의 시간 복잡도가 달라진다!

스택의 연산

• pop() : 스택의 가장 위에 있는 항목을 제거한다.
• push(item) : item 하나를 스택의 가장 윗 부분에 추가한다.
• peek() : 스택의 가장 위에 있는 항목을 리턴한다.
• is_empty() : 스택이 비어있으면 true(1)를 리턴한다.

스택의 구현

• stack 구현

typedef struct s_stack
{
	int data;
	struct s_stack *next;
} t_stack;

• pop() 구현

void pop(t_stack *stack)
{
	t_stack *node;
	t_stack *prev;

	if (!stack)
		return ;
	prev = stack;
	node = stack->next;
	while (node->next);
	{
		prev = node;
		node = node->next;
	}
	free(node);
	prev->next = NULL;
}

• push(item) 구현

void push(t_stack *stack, int item)
{
	t_stack *node;
	t_stack *new;

	node = stack;
	if ((new = (t_stack *)malloc(sizeof(stack))) == 0)
		return ;
	new->data = item;
	new->next = NULL;
	while (node->next)
		node = node->next;
	node->next = new;
}

• peek() 구현

int peek(t_stack *stack)
{
	t_stack *node;

	node = stack;
	while (node->next)
		node = node->next;
	return (node->data);
}

• is_empty() 구현

int is_empty(t_stack *stack)
{
	if (stack == NULL)
		return (1);
	return (stack->next == NULL);
}

• main 예시

#include "stack.h"

int main(void)
{
	t_stack *stack;

	stack = (t_stack *)malloc(sizeof(t_stack));
	for (int i = 0; i < 5; i++)
		push(stack, i);
	while (!is_empty(stack))
	{
		printf("%d ", stack.peek());
		pop(stack);
	}
	return (0);
}
// result
// 4 3 2 1 0