연결 리스트로 구현한 스택

연결된 스택

- 연결 리스트를 이용하여 구현한 스택을 연결된 스택(linked stack)이라 함

- 제공되는 외부 인터페이스는 배열 스택과 연결된 스택이 동일

- 스택의 내부 구현이 다름

- 연결 리스트를 이용하여 스택을 구현하면 스택에 새로운 요소가 삽입될 때마다 동적 할당으로 메모리를 할당하므로 스택 크기가 제한되지 않음(pros)

- 동적 메모리 할당이나 해제가 필요하므로 삽입이나 삭제 시간이 더 소요(cons)

typedef int element;
typedef struct StackNode {
	element data;
	struct StackNode* link;
}StackNode;
typedef struct {
	StackNode* top;
}LinkedStackType;

- 데이터를 저장하는 데이터 필드와 다음 노드를 가리키는 포인터가 들어 있는 링크 필드로 구성

- top은 정수가 아닌 포인터로 선언

- LinkedStactType 구조체 타입으로 top 포인터를 정의

- 모든 함수들은 이 구조체의 포인터를 매게 변수로 사용

 

삽입&삭제 연산

- 삽입 연산: 단순 연결 리스트의 삽입 연산과 개념적으로 동일

- 동적 메모리 할당으로 삽입될 노드를 생성

- top의 값을 temp->link에 복사

- temp를 top에 복사

StackNode* temp = (StackNode*)malloc(sizeof(StackNode));
temp->data = item;
temp->link = s->top;
s->top = temp;

 

- 삭제 연산

- top의 값을 top->link로 바꾸고 기존의 top이 가리키는 노드를 동적 메모리 해제

StackNode* temp = s->top;	//top이 가리키는 노드를 temp가 함께 가리킴(=삭제할 노드)
element data = temp->data;	//temp가 가리키는 노드의 데이터를 data에 저장
s->top = s->top->link;	//top이 temp의 후행 노드를 가리키도록 변경
free(temp);	//temp의 메모리 할당 해제
return data;

---

전체 프로그램

#include <stdio.h>
#include <stdlib.h>

typedef int element;
typedef struct StackNode {
	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;	//top이 가리키는 노드를 temp가 함께 가리킴(=삭제할 노드)
		element data = temp->data;	//temp가 가리키는 노드의 데이터를 data에 저장
		s->top = s->top->link;	//top이 temp의 후행 노드를 가리키도록 변경
		free(temp);	//temp의 메모리 할당 해제
		return data;
	}
}
//피크 함수
element peek(LinkedStackType* s) {
	if (is_empty(s)) {
		fprintf(stderr, "스택이 비어 있음\n");
		exit(1);
	}
	else {
		return s->top->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;
}

>>