【数据结构】栈

【数据结构】栈1 栈的概念及结构 栈 一种特殊的线性表 只允许在固定的一端插入删除数据 进行插入删除的一端叫做栈顶 另一端叫做栈底 遵循后进先出 LIFO 从栈顶进去栈顶出去 的原则 静态结构 define N 10 栈的容量 typedef

大家好,我是讯享网,很高兴认识大家。

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; }

小讯
上一篇 2025-02-08 14:05
下一篇 2025-03-04 11:10

相关推荐

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/76547.html