[C] 단일 연결 리스트로 구현한 스택

출처 - C로 배우는 알고리즘 (이재규 지음)

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

typedef struct _node
{
	int key;
	struct _node *next;
}node;

void init_stack();	// head와 tail 메모리 할당, head가 가리키는 다음 노드 tail로 초기화, tail이 가리키는 다음 노드 자기자신으로 초기화
int push(int key);	// head 다음에 노드 추가, 메모리 부족으로 할당 실패시 -1 리턴
int pop();		// 입력된 값이 아무것도 없을 경우 -1 리턴
void clear_stack();	// 스택의 모든 노드를 메모리 해제
void print_stack();	// 스택의 모든 내용을 출력

node *head, *tail;

int main(int argc, char *argv[], char **env)
{
	int i = 0;
	init_stack();

	printf("Push 5, 4, 7, 8, 2, 1\n");
	push(5);
	push(4);
	push(7);
	push(8);
	push(2);
	push(1);
	print_stack();
	puts("");

	printf("pop\n");
	i = pop();
	print_stack();
	printf("popping value is %d\n", i);
	puts("");

	printf("Push 3, 2, 5, 7, 2\n");
	push(3);
	push(2);
	push(5);
	push(7);
	push(2);
	print_stack();
	puts("");

	printf("push 3\n");
	push(3);
	print_stack();
	puts("");

	printf("Initialize stack\n");
	clear_stack();
	print_stack();
	puts("");

	printf("Now stack is empty, pop\n");
	i = pop();
	print_stack();
	printf("popping value is %d\n", i);

	return 0;
}

void init_stack()
{
	head = (node *)calloc(sizeof(node), 1);
	tail = (node *)calloc(sizeof(node), 1);

	head->next = tail;
	tail->next = tail;
}
int push(int key)
{
	node *new_node = NULL;

	if((new_node = (node *)calloc(sizeof(node), 1)) == NULL)
	{
		printf("Out of memory...\n");
		return -1;
	}

	new_node->key = key;
	new_node->next = head->next;
	head->next = new_node;

	return key;
}

int pop()
{
	node *t = NULL;
	int i = 0;

	if(head->next == tail)
	{
		printf("Stack underflow\n");
		return -1;
	}

	t = head->next;
	i = t->key;
	head->next = t->next;

	free(t);

	return i;
}

void clear_stack()
{
	node *t = NULL, *s = NULL;

	t = head->next;

	while(t != tail)
	{
		s = t;
		t = t->next;
		free(s);
	}

	head->next = tail;
}

void print_stack()
{
	node *t = NULL;

	if(head->next == tail)
	{
		printf("Stack is empty...\n");
		return;
	}

	t = head->next;

	while(t != tail)
	{
		printf("%-6d", t->key);
		t = t->next;
	}

	puts("");
}