[C] 단일연결리스트 기반 스택 (single linked list stack)

 C로 스택을 구현할 때 가장 많이 쓰는 자료구조중 하나가 연결리스트이다. 크기에 제한없이 스택을 사용할 수 있다는 장점이 있으나 메모리 측면에서 배열을 이용했을 때보다 비효율적이다. 연결리스트에 있는 모든 노드에는 항상 자기 이외의 노드를 가리키는 포인터 변수가 1개 이상 존재하기 때문이다.

 본 프로그램 코드는 단일 연결리스트 기반으로 만든 스택을 사용자가 직접 이용할 수 있게 만든 것이다. 스택에 들어갈 수 있는 값은 하나의 정수이다.

 명령어

 push N -> 정수 N을 push한다

 pop -> 스택을 pop하고 그 값을 출력한다. 스택이 비어있으면 Stack Empty 출력

 size -> 스택의 크기를 출력한다.

 top -> top에 위치한 값을 출력한다. 스택이 비어있으면 Stack Empty 출력

 print -> 스택 내 모든 값들을 출력한다. 스택이 비어있으면 Stack Empty 출력

 exit -> 프로그램 종료

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

typedef struct Node {

	int n;

	struct Node *next;

}NODE;

typedef struct {

	NODE *top;

	int size;

}STACK;

void init(STACK *);
void push(STACK *, int);
void pop(STACK *);
void printAll(STACK *);
int getSize(STACK *);
int isEmpty(STACK *);
void top(STACK *);

int main(){

	STACK *s = (STACK *)malloc(sizeof(STACK));

	int n;
	char order[10];

	init(s);

	while(1){

		scanf("%s", order);

		if (strcmp(order, "push") == 0) {
			scanf("%d", &n);
			getchar();
			push(s, n);
		}
		else if (strcmp(order, "pop") == 0) {
			pop(s);
		}
		else if (strcmp(order, "size") == 0) {
			printf("size : %d\n", getSize(s));
		}
		else if (strcmp(order, "top") == 0) {
			top(s);
		}
		else if (strcmp(order, "print") == 0) {
			printAll(s);
		}
		else if (strcmp(order, "exit") == 0) {
			break;
		}

	}

	return 0;

}

void init(STACK *s) {
	s->top = NULL;
	s->size = 0;
}

void push(STACK *s, int n) {

	NODE *new_node = (NODE*)malloc(sizeof(NODE));

	new_node->n = n;
	new_node->next = s->top;

	s->top = new_node;

	s->size++;

	printf("Push Success\n");

}

void pop(STACK *s) {

	int result;
	NODE *tmp;

	if (isEmpty(s)) {
		printf("Stack Empty\n");
		return;
	}

	tmp = s->top;
	result = tmp->n;

	s->top = tmp->next;
	s->size--;

	free(tmp);

	printf("pop : %d\n", result);

}

void printAll(STACK *s) {

	NODE *i;

	i = s->top;

	if (i == NULL) {
		printf("Stack Empty\n");
		return;
	}

	while (i != NULL) {
		printf("%d\n", i->n);
		i = i->next;
	}

}

int getSize(STACK *s) {
	return s->size;
}

int isEmpty(STACK *s) {
	return s->top == NULL;
}

void top(STACK *s) {

	if (isEmpty(s)) {
		printf("Stack Empty\n");
		return;
	}

	printf("top : %d\n", s->top);

}