[자료구조] 연결리스트를 활용한 스택 구현

연결리스트로 구현한 스택

스택을 구현하는 데 있어서 연결리스트를 활용할 수 있습니다. 연결리스트로 스택을 구성하면 배열로 구성된 스택에 비해 크기의 제한이 없다는 장점이 있지만 반대로 메모리를 동적으로 할당하므로 할당과 해제에 따른 시간이 소모된다는 단점이 있습니다.

 

삽입 연산

 

연결리스트로 구현된 스택에 노드를 삽입하는 연산의 경우 다음 두 순서의 변경 사항이 필요합니다.

1. temp(삽입할 노드)의 link를 top으로 할당.

2. top을 temp로 할당.

 

이때 순서가 변경되어서는 안됩니다. 만약 top을 temp로 할당하는 과정을 먼저 수행하면 temp의 link가 가리킬 위치를 알 수 없게됩니다.

 

 

삭제 연산

연결리스트로 구현된 스택에 노드를 삭제하는 연산의 경우 다음 두 순서의 변경 사항이 필요하며 순서가 변경되어서는 안됩니다.

1. top을 top의 link로 할당.

2. top 앞의 메모리 해제

 

2는 실행하지 않아도 동작합니다. 하지만 이 경우 메모리 해제가 안되어 정크 값으로 남아 메모리 누수가 일어나므로 꼭 메모리를 해제해주시는 것이 좋습니다.

 

 

알고리즘

#include <stdio.h>
#include <malloc.h>

typedef int element;

typedef struct {
	element data;
	struct StackNode* link;
} StackNode;

typedef struct {
	StackNode* top;
} LinkedStackType;

// 초기화 함수
void init(LinkedStackType* s)
{
	s->top = NULL;
}
// 공백 검출
int is_empty(LinkedStackType* s) {
	return (s->top == NULL);
}
// 포화 검출
int is_full(LinkedStackType* s) {
	return 0;
}
// 삽입
void push(LinkedStackType* s, element item) {
	StackNode* temp =
		(StackNode*)malloc(sizeof(StackNode));
	temp->data = item;
	temp->link = s->top;
	s->top = temp;
}
// 삭제
element pop(LinkedStackType* s)
{
	if (is_empty(s)) {
		fprintf(stderr, "스택이 비어있음\n");
		exit(1);
	}
	else {
		StackNode* temp = s->top;
		element data = temp->data;
		s->top = s->top->link;
		free(temp);
		return data;
	}
}
// 출력
void print_stack(LinkedStackType* s) {
	for (StackNode* p = s->top; p != NULL; p = p->link)
		printf("%d->", p->data);
	printf("NULL \n");
}
int main(void)
{
	LinkedStackType s;
	init(&s);
	push(&s, 1); print_stack(&s);
	push(&s, 2); print_stack(&s);
	push(&s, 3); print_stack(&s);
	pop(&s); print_stack(&s);
	pop(&s); print_stack(&s);
	pop(&s); print_stack(&s);
	return 0;
}
/* 실행결과
1->NULL
2->1->NULL
3->2->1->NULL
2->1->NULL
1->NULL
NULL
*/

 

 

연습문제

메인 함수에서 다음과 같은 일을 수행했을 때 스택과 힙 공간의 상태를 그려라.

int main(void)
{
	LinkedStackType s;
	init(&s);
	push(&s, 1); print_stack(&s);
	push(&s, 2); print_stack(&s);
	push(&s, 3); print_stack(&s);

	return 0;
}