松江新城建设发展有限公司网站,wordpress上传录音,企业服务云,商标每年要交多少钱文章目录 前言概述栈的初始化销毁压栈出栈判断栈为不为空栈的有效个数 前言
栈相对于链表#xff0c;稍微简单一点#xff0c;但是栈的难点在于通过栈去理解递归算法。
概述
**栈#xff1a;**一种特殊的线性表#xff0c;其只允许在固定的一端进行插入和删除元素操作。… 文章目录 前言概述栈的初始化销毁压栈出栈判断栈为不为空栈的有效个数 前言
栈相对于链表稍微简单一点但是栈的难点在于通过栈去理解递归算法。
概述
**栈**一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶另一端称为栈底。栈中的数据元素遵守 后进先出 LIFOLast In First Out的原则。
**压栈**栈的插入操作叫做进栈/压栈/入栈入数据在栈顶。
**出栈**栈的删除操作叫做出栈。出数据也在栈顶。 栈的实现一般可以使用数组或者链表实现相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。 栈的初始化
初始化在c语言中需要动态开辟内存
top是栈顶记录当前数据个数但是需要注意的是
如果初始化成0那么这个 top 就指的是栈顶的下一个位置 如果初始化成-1那么这个 top 就指的是栈顶的位置 初始化的容量和顺序表操作一样
void STInit(ST* pst)
{assert(pst);pst-a NULL;pst-capacity 0;// 表示top指向栈顶元素的下一个位置pst-top 0;// 表示top指向栈顶元素//pst-top -1;
}销毁
void STDestroy(ST* pst)
{assert(pst);free(pst-a);pst-a NULL;pst-top pst-capacity 0;
}压栈
压栈的时候需要先判断栈满不满判断条件pst-top pst-capacity
如果满了则需要开辟空间
不满则直接压入栈顶即可。
需要注意的是 如果初始化成0先将栈顶top往后移动top再将x压入栈中a[top]x 如果初始化成-1,先将c压入栈中a[top]x再移动栈顶top
void STPush(ST* pst, STDataType x)
{assert(pst);if (pst-top pst-capacity){int newcapacity pst-capacity 0 ? 4 : pst-capacity * 2;STDataType* tmp (STDataType*)realloc(pst-a, sizeof(STDataType) * newcapacity);if (tmp NULL){perror(realloc fail);return;}pst-a tmp;pst-capacity newcapacity;}pst-a[pst-top] x;pst-top;
}出栈
栈的操作都是在栈顶完成的出站时直接将top--即可
void STPop(ST* pst)
{assert(pst);// 不为空assert(pst-top 0);pst-top--;
}判断栈为不为空
如果栈顶不存在为0,则栈为空返回true
如果栈顶存在不为0则栈不为空返回false
bool STEmpty(ST* pst)
{assert(pst);/*if (pst-top 0){return true;}else{return false;}*/return pst-top 0;
}
栈的有效个数
若初始化的 top 是0则 top 就是栈的有效元素个数
若初始化的 top 是-1则 top1 为栈的有效元素个数。
int STSize(ST* pst)
{assert(pst);return pst-top;
}
