1.栈的概念及结构
栈:一种特殊的线性表,只允许在固定的一端插入删除数据,进行插入删除的一端叫做栈顶,另一端叫做栈底。遵循后进先出(LIFO)(从栈顶进去栈顶出去)的原则。
讯享网
静态结构:
#define N 10//栈的容量 typedef int STDataType; typedef struct Stack { STDataType a[N]; int top;//栈顶 }ST;
讯享网
动态结构:(最好)
讯享网typedef int STDataType; typedef struct Stack { STDataType* a; int top;//栈顶 int capacity;//容量 }ST;
2.栈的实现
栈的实现用数组最合适,从两个方面来说:尾插尾删效率很高,cpu的高速缓存也很高。注意这里的栈和操作系统中的栈不一样(容易混淆),只是开创一块空间然后数据的储存方式和内存中的栈结构相似,后进先出。
// 下面是定长的静态栈的结构,实际中一般不实用,所以我们主要实现下面的支持动态增长的栈 typedef int STDataType; #define N 10 typedef struct Stack { STDataType _a[N]; int _top; // 栈顶 }Stack; // 支持动态增长的栈 typedef int STDataType; typedef struct Stack { STDataType* _a; int _top; // 栈顶 int _capacity; // 容量 }Stack; // 初始化栈 void StackInit(Stack* ps); // 入栈 void StackPush(Stack* ps, STDataType data); // 出栈 void StackPop(Stack* ps); // 获取栈顶元素 STDataType StackTop(Stack* ps); // 获取栈中有效元素个数 int StackSize(Stack* ps); // 检测栈是否为空,如果为空返回非零结果,如果不为空返回0 int StackEmpty(Stack* ps); // 销毁栈 void StackDestroy(Stack* ps)
2.1初始化
初始化很简单,初始容量和栈顶都置为0即可,栈顶元素值为空。
讯享网//初始化 void StackInit(ST* ps) { assert(ps); ps->val = NULL; ps->top = 0; ps->capacity = 0; }
2.2入栈
相当于顺序表的尾插,只有尾插,实现起来也很简单,需要注意扩容。

//插入数据 void StackPush(ST* ps, STDataType x) { assert(ps); //先看空间够不够 if (ps->top == ps->capacity) { int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; STDataType* tmp = (STDataType*)realloc(ps->val,sizeof(STDataType) * newCapacity); if (tmp == NULL) { perror(realloc); return; } ps->val = tmp; ps->capacity = newCapacity; } //栈顶的数据元素给值 ps->val[ps->top] = x; ps->top++; }
2.3出栈
栈遵循先进后出的原则,所以出栈也只能从栈顶出,相当于尾删。
讯享网//删除数据 void StackPop(ST* ps) { assert(&ps); //判断栈是否为空 assert(!StackEmpty(ps)); ps->top--; }
2.4获取栈顶元素
返回栈顶的元素,就是找到尾的数也就是top所对应的值。
//拿出栈顶的数据 STDataType StackTop(ST* ps) { assert(ps); assert(!StackEmpty(ps)); return ps->val[ps->top-1]; }
2.5获取栈中元素个数
也就是返回top的值。
讯享网//计算栈的长度 int StackSize(ST* ps) { assert(ps); return ps->top; }
2.6检查栈是否为空
判断top是否为零即可判断出栈是否为空
//判断栈是否为空 bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; }
2.7销毁栈
程序结束时需要销毁栈,释放内存,避免造成内存泄漏。
讯享网//销毁栈空间 void StackDestroy(ST* ps) { assert(ps); free(ps->val); ps->val = NULL; ps->top = ps->capacity = 0; }
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/76547.html