沈阳城市建设学院网站,珠海网站搜索引擎优化,百度网站优化软件,烟台市建设工程招标投标协会网站#x1f495;休对故人思故国#xff0c;且将新火试新茶#xff0c;诗酒趁年华#x1f495; 作者#xff1a;Mylvzi 文章主要内容#xff1a;详解链表OJ题 前言#xff1a; 前面已经学习过顺序表#xff0c;链表。他们都是线性表#xff0c;今天要学习的栈也是一种线… 休对故人思故国且将新火试新茶诗酒趁年华 作者Mylvzi 文章主要内容详解链表OJ题 前言 前面已经学习过顺序表链表。他们都是线性表今天要学习的栈也是一种线性表。那么什么是栈呢栈又是如何实现对数据的管理呢下面进行讲解。 栈的定义 栈就是一种只能在栈顶进行元素的添加删除的线性表。具有“后进先出”的特性就是后面进入的元素反而首先被删除所以栈的这种结构又被称为LIFO结构Last In First Out; 我们可以把栈理解为枪的的弹夹试想每次压子弹的时候是不是只能从一端插入先插入的子弹会被先打出去子弹装填的过程对应着数据的进入被称为“入栈”而子弹的射出对应着数据的删除被称为“出栈”
栈的结构 我们知道栈的最大特点就是只能在一端进行数据的添加和删除那栈应该使用哪种结构来实现呢是数组还是链表呢其实最常使用的应该是数组。因为数组进行尾部数据的删除更简单数组的尾部就相当于栈顶如果使用单链表我们要保存上一结点的地址如果使用双向链表其结构没有数组简单而且数组对缓存的利用率要高于链表能提高效率 栈的实现 定义栈元素
//定义栈元素
typedef int STDataType;typedef struct Stack
{STDataType* a;//存储数据int top;//栈顶int capacity;//容量
}ST; 栈的初始化与删除
//初始化栈
void STInit(ST* ps)
{assert(ps);ps-a NULL;ps-top 0;//代表栈顶下一个位置ps-capacity 0;
}//删除栈
void STDestroy(ST* ps)
{assert(ps);free(ps-a);ps-a NULL;ps-top 0;ps-capacity 0;
} 入栈和出栈
//入栈
void STPush(ST* ps, STDataType x)
{assert(ps);//栈满要扩容if (ps-top ps-capacity){//要考虑最开始top capacity为0的情况//使用了三目运算符:为0则新的容量值为4不为0新的容量值为原来的2倍int newcapacity ps-capacity 0 ? 4 : 2 * ps-capacity;STDataType* tmp (STDataType*)realloc(ps-a, sizeof(STDataType)*newcapacity);if (tmp NULL){perror(realloc);exit(-1);}//重新赋值ps-a tmp;ps-capacity newcapacity;}ps-a[ps-top] x;ps-top;
}//出栈
void STPop(ST* ps)
{assert(ps);//空assert(ps-a);ps-top--;//不需要管原来数据直接让栈顶向前移动
} 返回栈顶元素
//返回栈顶元素
STDataType STTPop(ST* ps)
{assert(ps);assert(ps-a);//设置的top位最后一个元素的下一个位置return ps-a[ps-top - 1];
} 计算元素个数和判断是否为空栈
//计算有效值个数
int STSize(ST* ps)
{assert(ps);//top就是栈内的数据个数return ps-top;
}//判断是否为空栈
bool STEmpty(ST* ps)
{assert(ps);return ps-top 0;
} 总结 大家刚接触栈可能很疑惑栈的应用场景有哪些呢举个例子在我们上网时在某个网页遇到了一个吸引人的链接你忍不住好奇心点了进去发现是不良网站你想退到你原先浏览的界面这是你就可以点击浏览器上方的后退键就自动退回到原先的浏览界面。其实在这个过程中一个一个的网页被“入栈”你进去的不良网站就是栈顶元素后退键其实是实现了“出栈”的一个过程 再比如画图软件中的“撤销”操作本质上也是进行了“出栈”的操作所以栈的应用还是很广泛的其他应用还需要大家自己摸索
