从零开始的敲代码生活--数据结构篇（栈）

一、栈基础概念栈结构只允许从一端进行插入和删除数据的线性存储结构称为栈结构。 数据插入和删除的这端称为栈顶另一端称为栈底。 数据的插入称为入栈/压栈数据的删除称为出栈/弹栈。特点 先进后出(FILO)栈的应用解决回溯问题撤销功能、网页撤销功能缓存判断回文字符串判断成对出现的符号有没有丢失栈的分类顺序栈使用顺序存储结构(数组)实现的栈根据栈顶位置与栈的生长方向分为四种满栈、空栈根据所在位置是否存有元素确定栈顶所在位置一直存有元素称为满栈栈顶所在位置一直没有元素称为空栈增栈、减栈根据栈的生长方向确定入栈数据时栈顶向内存高地址移动称为增栈入栈数据时栈顶向内存低地址移动称为减栈组合满增栈、空增栈、满减栈、空减栈链式栈使用链式存储结构(链表结点)实现的栈入栈采用头插法出栈删除头结点不存在栈满问题。链式栈的 API创建栈入栈出栈判栈空获取栈顶元素清空栈(删除栈中的所有结点)销毁栈文件说明文件说明stack.h头文件栈结构体定义 函数声明stack.c源文件栈所有功能实现main.c测试 main 函数二、头文件 stack.h#ifndef _STACK_H #define _STACK_H #include stdio.h #include stdlib.h typedef int Data_t; /* 栈结点结构体:数据域 指针域 */ typedef struct node { Data_t data; // 数据域:保存的数据 struct node *pnext; // 指针域:下一个结点的地址 }Node_t; /* 栈对象结构体:栈顶指针 结点计数 */ typedef struct stack { Node_t *ptop; // 栈顶指针 int clen; // 栈当前结点个数 }Stack_t; extern Stack_t *create_stack(); extern int is_empty_stack(Stack_t *pstack); extern int en_stack(Stack_t *pstack,Data_t data); extern int de_stack(Stack_t *pstack,Data_t *data); extern int show_stack(Stack_t *pstack); extern int get_stack_top(Stack_t *pstack,Data_t *data); extern int free_stack_node(Stack_t *pstack); extern void free_stack(Stack_t *pstack); #endif三、功能实现 stack.ccreate_stack 创建栈功能分配栈管理结构体初始化栈顶指针 ptop 置 NULL、结点计数 clen 为 0。返回栈指针malloc 失败返回 NULL。Stack_t *create_stack() { Stack_t *pstack malloc(sizeof(Stack_t)); if(pstack NULL) { printf(malloc fail\n); return NULL; } pstack-clen 0; pstack-ptop NULL; return pstack; }is_empty_stack 判栈空功能判断栈是否为空。返回1 空0 非空-1 入参为 NULL。int is_empty_stack(Stack_t *pstack) { if(pstack NULL) { return -1; } else { return pstack-clen 0; } }en_stack 入栈(压栈)功能头插法在栈顶插入新结点新结点指针域指向原栈顶结点更新栈顶指针计数自增。返回0 成功-1 失败(入参为 NULL 或者 malloc 失败)。int en_stack(Stack_t *pstack,Data_t data) { if(pstack NULL) { return -1; } Node_t *ptemp malloc(sizeof(Node_t)); if(ptemp NULL) { printf(malloc fail\n); return -1; } ptemp-data data; ptemp-pnext pstack-ptop; pstack-ptop ptemp; pstack-clen; return 0; }de_stack 出栈(弹栈)功能删除栈顶结点并带回其数据栈顶指针后移一位释放原栈顶结点计数减一。返回0 成功-1 失败(栈空或入参为 NULL)。int de_stack(Stack_t *pstack,Data_t *data) { if(is_empty_stack(pstack) ! 0) { return -1; } Node_t *ptemp pstack-ptop; *data ptemp-data; pstack-ptop ptemp-pnext; free(ptemp); return 0; }get_stack_top 获取栈顶元素功能读取栈顶结点的 data 数据不删除结点。返回0 成功-1 失败(栈空或入参为 NULL)。int get_stack_top(Stack_t *pstack,Data_t *data) { if(is_empty_stack(pstack) ! 0) { return -1; } *data pstack-ptop-data; return 0; }show_stack 遍历打印栈功能从栈顶开始循环遍历打印栈中所有 data 数据。返回0 成功-1 失败(栈空或入参为 NULL)。int show_stack(Stack_t *pstack) { if(pstack NULL) { return -1; } Node_t *ptemp pstack-ptop; if(pstack-clen ! 0) { while(ptemp ! NULL) { printf(%d ,ptemp-data); ptemp ptemp-pnext; } printf(\n); return 0; } return -1; }free_stack_node 清空栈功能循环释放栈中所有数据结点清空后栈顶指针置 NULL、计数置 0。返回0 成功-1 入参为 NULL。int free_stack_node(Stack_t *pstack) { if(pstack NULL) return -1; Node_t *ptemp pstack-ptop; if(pstack-clen ! 0) { while(ptemp! NULL) { pstack-ptop ptemp-pnext; free(ptemp); ptemp pstack-ptop; } pstack-ptop NULL; pstack-clen 0; } return 0; }free_stack 销毁栈功能先调用 free_stack_node 释放全部数据结点最后释放栈管理结构体。void free_stack(Stack_t *pstack) { free_stack_node(pstack); free(pstack); }四、测试 main 函数 main.c#include stack.h int main(void) { Data_t data; Stack_t *pstack create_stack(); en_stack(pstack,1); en_stack(pstack,2); en_stack(pstack,3); en_stack(pstack,4); en_stack(pstack,5); show_stack(pstack); printf(---------\n); de_stack(pstack,data); printf(%d\n,data); printf(---------\n); get_stack_top(pstack,data); printf(top_stack %d\n,data); printf(---------\n); free_stack(pstack); return 0; }五、编译运行 内存检测编译gcc main.c stack.c -o stack_demo运行程序./stack_demovalgrind 检测内存泄漏写栈务必检测内存泄漏保证每一块 malloc 都有对应的 freevalgrind --leak-checkfull ./stack_demo运行输出结果5 4 3 2 1 5 top_stack 4