栈（C语言）

目录1. 栈的定义2. 代码实现1. 栈的定义栈属于线性表具有后进先出的特点存储结构类似羽毛球桶可以依次取出最后放入栈中的数据。实现栈一般采用数组 / 链表实现但是推荐程度数组 单链表 双链表。因为存取在栈顶实现因此中间元素不需要提供直接访问的功能单链表在双链表的基础上减少了指针占用的内存而数组这种顺序表结构更是比链表减少了插入数据的代价无需遍历至尾部。2. 代码实现//stack.h文件#pragma once typedef int STDataType; typedef struct Stack { STDataType* a; //指向动态数组的指针 int top; //动态数组中最后一个有效元素的下一位 int capacity; //动态数组的总容量 }ST; //栈的初始化和销毁 void STInit(ST* pst); void STDestroy(ST* pst); //入栈和出栈 void STPush(ST* pst, STDataType x); void STPop(ST* pst); //查询栈顶元素 STDataType STTop(ST* pst); //判空 bool STEmpty(ST* pst); //查询数据个数 int STSize(ST* pst);//stack.c文件#includestdio.h #includestdlib.h #includeassert.h #includestdbool.h #include stack.h //栈的初始化 void STInit(ST* pst) { assert(pst); pst-a NULL; pst-top 0; //指向数组末尾有效元素的下一位 pst-capacity 0; } //销毁 void STDestroy(ST* pst) { assert(pst); free(pst-a); pst-a NULL; pst-top pst-capacity 0; } //入栈 void STPush(ST* pst, STDataType x) { assert(pst); //需要扩容的情况 if(pst-top pst-capacity) { int newcapacity pst-capacity 0 ? 4 : 2*pst-capacity; STDataType* tmp (STDataType*)realloc(pst-a, sizeof(STDataType) * newcapacity); if(tmp NULL) { perror(realloc fail); exit(1); } pst-a tmp; pst-capacity newcapacity; } pst-a[pst-top] x; pst-top; } //出栈 void STPop(ST* pst) { assert(pst pst-top ! 0); pst-top--; } //查询栈顶元素 STDataType STTop(ST* pst) { assert(pst pst-top0); return pst-a[pst-top-1]; } //判空 bool STEmpty(ST* pst) { assert(pst); return pst-top 0; } //查询数据个数 int STSize(ST* pst) { assert(pst); return pst-top; }