数据结构实战

        栈的特点是先进后出，后进先出，在内存中的结构如下：

        下面来看一下栈的数据结构：

typedef struct
{
	//栈大小，以元素个数为单位
	int stack_size;
	//元素个数
	int ele_count;
	//栈地址
	void *stack_addr;
	//栈顶地址
	void *p;
	//回调函数，在销毁栈时释放未出栈元素的内存
	void (*destructor)(void *);
} s_stack;

        接下来实现相关功能函数：

//构建一个栈
bool stack_init(s_stack *stack, void (*destructor)(void *))
{
	if (stack == null)
	{
		return false;
	}

	//初始大小为2
	stack->stack_size = 2;
	//当前元素个数为0
	stack->ele_count = 0;
	//申请栈空间
	stack->stack_addr = malloc(4 * stack->stack_size);
	//将指针p设置为栈顶元素
	stack->p = stack->stack_addr + stack->stack_size * 4;
	//设置回调函数，在栈销毁时用于释放未出栈元素的内存
	stack->destructor = destructor;

	return true;
}

//销毁栈
bool stack_destroy(s_stack *stack)
{
	if (stack == null)
	{
		return false;
	}

	//循环释放未出栈元素所占用的内存
	for (int i = 0; i < stack->ele_count; i++)
	{
		//回调函数，释放内存
		stack->destructor((void*) (*(unsigned int *) stack->p));
		//p向下移动
		stack->p += 4;
	}
	//释放栈内存
	free(stack->stack_addr);

	return true;
}

//压栈
bool stack_push(s_stack *stack, void *p_ele)
{
	if (stack == null || p_ele == null)
	{
		return false;
	}

	//p向上移动4byte
	stack->p -= 4;
	//将元素入栈，入栈的是一个地址
	*(unsigned int *) stack->p = (unsigned int) p_ele;
	//元素个数加1
	stack->ele_count++;
	//如果栈满
	if (stack->stack_size == stack->ele_count)
	{
		//申请2倍大小的内存空间
		stack->stack_addr = realloc(stack->stack_addr, stack->stack_size * 2 * 4);
		//设定指针p的新值
		stack->p = stack->stack_addr + stack->stack_size * 2 * 4 - stack->ele_count * 4;
		//复制原数据到新的栈底
		memcpy(stack->stack_addr + stack->stack_size * 4, stack->stack_addr, stack->stack_size * 4);
		//栈大小变为2倍
		stack->stack_size *= 2;
	}

	return true;
}

//出栈
bool stack_pop(s_stack *stack, void *p_ele)
{
	if (stack == null || p_ele == null)
	{
		return false;
	}

	//如果栈空，出栈失败
	if (stack->ele_count == 0)
	{
		return false;
	}
	//出栈
	*(unsigned int *) p_ele = *(unsigned int *) stack->p;
	//p向下移动4byte
	stack->p += 4;
	//元素个数减1
	stack->ele_count--;

	return true;
}

        编写一个main函数来测试栈操作：

//释放int类型
void free_int(void *data)
{
	free(data);
}

//学生结构体
typedef struct
{
	int no;
	int age;
	char *name;
} student;

//创建学生
student *create_stu(int no, int age, const char* name)
{
	student *stu = (student *) malloc(sizeof(student));
	stu->no = no;
	stu->age = age;
	stu->name = (char *)malloc(20);
	memcpy(stu->name, name, 20);
	return stu;
}

//释放学生
void free_stu(void *data)
{
	student *stu = (student *) data;
	free(stu->name);
	free(stu);
}

//显示学生信息
void print_stu(student *stu)
{
	printf("no:%d age:%d name:%s\n", stu->no, stu->age, stu->name);
}

int main(int argc, char **args)
{
	//用于int类型的栈，回调函数为free_int
	s_stack s;
	stack_init(&s, free_int);
	//压栈5个元素
	for (int i = 0; i < 5; i++)
	{
		int *val = malloc(sizeof(int));
		*val = i;
		stack_push(&s, val);
	}
	//出栈3个元素
	for (int i = 0; i < 5; i++)
	{
		int *val;
		stack_pop(&s, &val);
		printf("%d\n", *val);
		free_int(val);
	}
	//销毁栈
	stack_destroy(&s);

	//用于存放human类型的栈，回调函数为destructor_human
	s_stack s_stu;
	stack_init(&s_stu, free_stu);
	//插入数据
	student *stu1 = create_stu(15100101, 21, "lidq");
	stack_push(&s_stu, stu1);
	student *stu2 = create_stu(15100102, 22, "zhuwj");
	stack_push(&s_stu, stu2);
	student *stu3 = create_stu(15100103, 23, "baiy");
	stack_push(&s_stu, stu3);

	//循环出栈，出栈3个元素
	for (int i = 0; i < 3; i++)
	{
		student *stu;
		stack_pop(&s_stu, &stu);
		print_stu(stu);
		free_stu(stu);
	}
	//销毁栈
	stack_destroy(&s_stu);

	return 0;
}

        运行结果，先进后出：

4
3
2
1
0
no:15100103 age:23 name:baiy
no:15100102 age:22 name:zhuwj
no:15100101 age:21 name:lidq

        本例代码：

code path   chapter.02/e.g.2.1/

https       https://github.com/magicworldos/datastructure.git
git         git@github.com:magicworldos/datastructure.git
subverion   https://github.com/magicworldos/datastructure