[Data Structure] 연결리스트 응용 : 스택

연결리스트 스택

- 장점 : 크기 제한 X

- 단점 : 구현이 복잡, 삽입/삭제 시간이 오래 걸린다

- 크기에 제한이 없기 때문에 스택이 포화인지 확인할 필요가 없다

 

 

[코드 - C]

#include <stdio.h>
#include <stdlib.h>
// 연결리스트를 이용한 스택

typedef int element;

typedef struct {
	element data;
	struct stacknode* link; // 각 노드들을 연결
}stacknode;

stacknode* top; // 스택의 top을 가리키는 top 포인터

void init() {
	top = NULL;
}

int is_empty() {
	return top == NULL;
}

void push(element item) {
	stacknode* new_node = (stacknode*)malloc(sizeof(stacknode));
	if (new_node == NULL) {
		fprintf(stderr, "메모리 할당 에러\n\n");
		return;
	}
	else {
		new_node->data = item;
		new_node->link = top;
		top = new_node;
	}
}

element pop() {
	if (is_empty(top)) {
		fprintf(stderr, "Error : Stack is empty\n\n");
		return;
	}
	else {
		stacknode* removed = top;
		element item = removed->data;
		top = removed->link;
		free(removed);
		return item;
	}
}

element peek() {
	if (is_empty(top)) {
		fprintf(stderr, "Error : Stack is empty\n\n");
		return;
	}
	else
		return top->data;
}

void clear() {
	stacknode* p = top;
	stacknode* removed;
	while (p) {
		removed = p;
		p = p->link;
		free(removed);
	}
	top = p;
}

void print_stack() {
	if (is_empty(top)) {
		fprintf(stderr, "Stack is empty\n\n");
		return;
	}
	else {
		stacknode* p = top;
		while (p) {
			printf("%d -> ", p->data);
			p = p->link;
		}
		printf("NULL\n\n");
	}
}

int main(void) {
	init();
	print_stack();
	printf(">>> push(10)\n"); push(10);
	print_stack();
	printf(">>> push(20)\n"); push(20);
	print_stack();
	printf(">>> push(30)\n"); push(30);
	print_stack();
	printf(">>> push(40)\n"); push(40);
	print_stack();
	printf(">>> push(50)\n"); push(50);
	print_stack();
	printf(">>> pop()\n>>> pop된 data : %d\n", pop()); 
	print_stack();
	printf(">>> peek()\n>>> peek된 data : %d\n", peek());
	print_stack();
	printf(">>> pop()\n>>> pop된 data : %d\n", pop()); 
	print_stack();
	printf(">>> clear()\n"); clear();
	print_stack();
}