栈的特点是先进后出,后进先出,在内存中的结构如下:
下面来看一下栈的数据结构:
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
Copyright © 2015-2023 问渠网 辽ICP备15013245号