数据结构——栈（附图文讲解 | 超详细）

文章目录一、前言二、栈2.1 定义1.后进先出2.压栈和出栈2.2 栈的实现1. 创建栈2. 栈的初始化3. 栈的销毁4. 入栈5. 判断栈是否为空6. 出栈7. 取栈顶8. 有效元素个数三、完整代码Stack.hStack.ctest.c一、前言这篇博客我们来聊聊数据结构——栈二、栈2.1 定义概念⼀种特殊的线性表其只允许在固定的⼀端进⾏插⼊和删除元素操作。进⾏数据插⼊和删除操作的⼀端称为栈顶另⼀端称为栈底。栈中的数据元素遵守后进先出LIFOLast In First Out的原则。1.后进先出那么是什么是后进先出呢先进去的数据后出来而后进去的数据先出来如图2.压栈和出栈压栈栈的插⼊操作叫做进栈/压栈/⼊栈⼊数据在栈顶。出栈栈的删除操作叫做出栈。出数据也在栈顶。2.2 栈的实现对于栈的实现来说可以使⽤数组或者链表实现相对⽽⾔数组的结构实现更优⼀些。因为数组在尾上插⼊数据的代价⽐较⼩。所以我们这里用数组来实现。1. 创建栈//栈typedefintSTDataType;//自定义数据元素类型typedefstructStack{STDataType*arr;inttop;//有效数据个数intcapacity;//空间容量}ST;2. 栈的初始化//初始化voidStackInit(ST*ps){ps-arrNULL;ps-topps-capacity0;}3. 栈的销毁//栈的销毁voidStackDestroy(ST*ps){if(ps-arr)free(ps-arr);ps-arrNULL;ps-topps-capacity0;}4. 入栈先向内存申请空间再从栈顶入栈//入栈——栈顶voidStackPush(ST*ps,STDataType x){assert(ps);if(ps-topps-capacity){intnewCapacityps-capacity0?4:2*ps-capacity;STDataType*tmp(STDataType*)realloc(ps-arr,newCapacity*sizeof(STDataType));if(tmpNULL){perror(realloc fail!);exit(1);}ps-arrtmp;ps-capacitynewCapacity;}ps-arr[ps-top]x;}5. 判断栈是否为空用于之后的功能接口进行断言//判断栈是否为空boolStackEmpty(ST*ps){assert(ps);returnps-top0;}6. 出栈从栈顶出栈//出栈voidStackPop(ST*ps){assert(!StackEmpty(ps));--ps-top;}7. 取栈顶取栈顶数据//取栈顶STDataTypeStackTop(ST*ps){assert(!StackEmpty(ps));returnps-arr[ps-top-1];}8. 有效元素个数//取有效元素个数intStackSize(ST*ps){returnps-top;}三、完整代码Stack.h#pragmaonce#includestdio.h#includestdlib.h#includeassert.h#includestdbool.h//栈typedefintSTDataType;typedefstructStack{STDataType*arr;inttop;intcapacity;}ST;//初始化voidStackInit(ST*ps);//销毁voidStackDestroy(ST*ps);//入栈——栈顶voidStackPush(ST*ps,STDataType x);//boolStackEmpty(ST*ps);//出栈voidStackPop(ST*ps);//取栈顶数据STDataTypeStackTop(ST*ps);//有效元素个数intStackSize(ST*ps);Stack.c#includeStack.h//初始化voidStackInit(ST*ps){ps-arrNULL;ps-topps-capacity0;}//销毁voidStackDestroy(ST*ps){if(ps-arr)free(ps-arr);ps-arrNULL;ps-topps-capacity0;}//入栈——栈顶voidStackPush(ST*ps,STDataType x){assert(ps);if(ps-topps-capacity){intnewCapacityps-capacity0?4:2*ps-capacity;STDataType*tmp(STDataType*)realloc(ps-arr,newCapacity*sizeof(STDataType));if(tmpNULL){perror(realloc fail!);exit(1);}ps-arrtmp;ps-capacitynewCapacity;}ps-arr[ps-top]x;}//判断栈是否为空boolStackEmpty(ST*ps){assert(ps);returnps-top0;}//出栈voidStackPop(ST*ps){assert(!StackEmpty(ps));--ps-top;}//取栈顶数据STDataTypeStackTop(ST*ps){assert(!StackEmpty(ps));returnps-arr[ps-top-1];}//有效元素个数intStackSize(ST*ps){returnps-top;}test.c#includeStack.hvoidtest01(){ST st;StackInit(st);StackPush(st,1);StackPush(st,2);StackPush(st,3);StackPush(st,4);StackPush(st,5);//StackPop(st);//StackPop(st);//StackPop(st);//StackPop(st);//StackPop(st);//while (!StackEmpty(st))//{// int top StackTop(st);// printf(%d , top);// StackPop(st);//}intsizeStackSize(st);printf(size:%d\n,size);StackDestroy(st);}intmain(){test01();//测试return0;}