数组栈（顺序栈）与链表栈(C语言入门)

栈一.核心定义栈是一种特殊的线性表其数据元素的插入和删除操作只能在线性表的同一端进行。这个特性通常被形象地概括为后进先出​ 或 先进后出。二.关键术语栈顶允许进行插入和删除操作的一端。栈底不允许进行操作的另一端它是固定的。空栈不包含任何数据元素的栈。入栈 / 压栈向栈顶插入一个新元素。出栈 / 弹栈从栈顶删除一个元素三. 栈的分类1.按存储结构分类数组栈顺序栈和链表栈也是我们这篇文章主要讲述的方面2.按容量是否可变分类静态栈和动态栈3.按功能用途分类了解即可通用栈、双端栈、受限栈、特殊功能栈数组栈顺序栈一.核心思想用一个数组存数据用一个变量top表示栈顶下标。空栈top-1入栈top再放数据出栈取arr[top]再top–。二. 优缺点优点:1.访问速度极快通过下标top直接定位栈顶入栈(Push)、出栈(Pop)、取栈顶(GetTop)操作​快。2.实现极其简单结构清晰代码简洁。缺点:1.容量固定最大的问题。2.难以扩容扩容难度大不如动态栈方便。三.完整代码C语言#includestdio.h// 初始最大容量可自定义#defineMAXSIZE10// 数组栈结构体typedefstruct{intdata[MAXSIZE];inttop;// 栈顶指针}Stack;// 初始化栈voidinitStack(Stack*s){s-top-1;}// 判断栈空intisEmpty(Stack*s){returns-top-1;}// 判断栈满intisFull(Stack*s){returns-topMAXSIZE-1;}// 入栈intpush(Stack*s,intval){if(isFull(s)){printf(栈满无法入栈\n);return0;}s-data[s-top]val;return1;}// 出栈intpop(Stack*s,int*val){if(isEmpty(s)){printf(栈空无法出栈\n);return0;}*vals-data[s-top--];return1;}// 取栈顶intgetTop(Stack*s,int*val){if(isEmpty(s))return0;*vals-data[s-top];return1;}// 遍历栈voidshowStack(Stack*s){if(isEmpty(s)){printf(栈空\n);return;}printf(栈内容栈底→栈顶);for(inti0;is-top;i){printf(%d ,s-data[i]);}printf(\n);}// 测试intmain(){Stack s;initStack(s);push(s,10);push(s,20);push(s,30);showStack(s);intval;pop(s,val);printf(出栈元素%d\n,val);showStack(s);getTop(s,val);printf(当前栈顶%d\n,val);return0;}代码运行结果链表栈一.核心思想用单链表实现的栈,关于单链表的知识可以参考其他文章二.优缺点优点1.没有容量限制2.不用扩容缺点1.代码较复杂2.速度稍慢3.占用空间较大三.完整代码#includestdio.h#includestdlib.h// 链表结点结构typedefstructNode{intdata;structNode*next;}Node;// 栈结构只需要栈顶指针typedefstruct{Node*top;}LinkStack;// 初始化栈voidInitStack(LinkStack*s){s-topNULL;}// 判断栈是否为空intIsEmpty(LinkStack*s){returns-topNULL;}// 入栈intPush(LinkStack*s,intvalue){Node*p(Node*)malloc(sizeof(Node));if(pNULL){printf(内存分配失败\n);return0;}p-datavalue;p-nexts-top;s-topp;return1;}// 出栈intPop(LinkStack*s,int*value){if(IsEmpty(s)){printf(栈空无法出栈\n);return0;}Node*ps-top;*valuep-data;s-topp-next;free(p);return1;}// 取栈顶元素不删除intGetTop(LinkStack*s,int*value){if(IsEmpty(s))return0;*values-top-data;return1;}// 遍历栈从栈顶到栈底voidShowStack(LinkStack*s){if(IsEmpty(s)){printf(栈空\n);return;}Node*ps-top;printf(栈元素(顶→底));while(p!NULL){printf(%d ,p-data);pp-next;}printf(\n);}// 销毁栈释放所有结点voidDestroyStack(LinkStack*s){Node*ps-top,*q;while(p!NULL){qp-next;free(p);pq;}s-topNULL;}// 主函数测试intmain(){LinkStack s;InitStack(s);Push(s,10);Push(s,20);Push(s,30);Push(s,40);ShowStack(s);intval;Pop(s,val);printf(出栈元素%d\n,val);GetTop(s,val);printf(当前栈顶%d\n,val);ShowStack(s);DestroyStack(s);return0;}代码运行结果总结数组栈快、简单、省空间但大小受限链表栈大小不限、灵活但慢一点、占空间