[자료구조] linked list로 스택(stack) 구현하기

스택은 LIFO(Last In First Out)방식으로 가장 나중에 들어온 값이 가장 먼저 빠져나간다. 

top이라는 변수는 스택의 가장 앞의 값을 가리키고 있고, push()를 수행하면 top의 값이 삽입되고 pop()을 수행하면 top의 값이 제거된다.

linked list의 기본 요소는 값을 저장할 멤버인 data와 다음 노드의 주소를 저장할 멤버인 next이다. 

이를 이용해 linked list로 stack을 구현해보았다.

 

 

 

먼저 struct NODE형인 top변수를 NULL로 초기화 시켜주었다. 

 

 

push()함수에서 하는 일은 struct NODE형인 임시변수를 하나 생성한 후 거기에 삽입할 값을 저장해두는 것이다.

제일 처음에 값이 들어올 때는 top이 바로 위에서 만든 임시변수가 되면 된다.

하지만 스택에 이미 값이 저장되어있을 때는 top이 새로운 값을 저장하고 있어야 하기 때문에, 위에서 만든 임시변수의 next는 기존에 저장된 top을 가리키게 만든 후에 top을 새로운 값을 저장하고 있는 임시변수가 되게 만들어야 한다. 

 

 

 

 

pop()함수에서 하는 일은 현재 top의 값을 제거하고, top의 위치를 한칸 뒤로 옮겨주는 것이다. 

struct NODE형인 임시변수를 하나 생성한 후, 현재 top을 저장한다. 

그 후 top을 한 칸 뒤인 top의 next값을 할당해준다. 

이제 위에서 만든 임시변수를 free() 시켜주면 된다. 

 

 

 

위의 그림을 코드로 구현해보았다. 

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 10

struct NODE
{
	struct NODE* next;
	int data;
};
int node_cnt = 0;
struct NODE* top = NULL;

int stack_full()
{
	if (node_cnt >= MAX_SIZE)
		return 1;
	return 0;
}

int stack_empty()
{
	if (node_cnt == 0)
		return 1;
	return 0;
}

void push(int n)
{
	if (!stack_full())
	{
		struct NODE* newNode = malloc(sizeof(struct NODE));
		if (newNode == NULL)
			return;
		newNode->data = n;
		newNode->next = NULL;
		node_cnt++;
		if (top != NULL)
			newNode->next = top;
		top = newNode;
	}
}

int pop()
{
	if (!stack_empty())
	{
		struct NODE* temp = top;
		int value = top->data;
		top = top->next;
		free(temp);
		node_cnt--;
		return value;
	}
	return -1;
}

void print_stack()
{
	if (stack_empty())
		printf("stack empty\n");
	else 
	{
		struct NODE* temp;
		temp = top;
		while (temp)
		{
			printf("%d ", temp->data);
			temp = temp->next;
		}
		printf("\n");
	}
}

int main()
{
	for (int i = 0; i < 10; i++)
		push(i);
	printf("1:\n");
	print_stack();
	push(10);
	printf("\n2:\n");
	print_stack();
	printf("\n3:\n");
	for (int i = 0; i < 10; i++)
		printf("%d ", pop());
	printf("\n\n4:\n");
	print_stack();
}