数据结构第3章栈和队列ppt课件.ppt

《数据结构第3章栈和队列ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3章栈和队列3.1栈的概念3.2栈的存储结构3.3顺序栈的操作算法3.4链栈的操作算法3.5栈的应用举例---表达式求值证餐烘渣耙牵淀雷上峻铸数责被辩俯硝卢幽幕浆镁涅渝赃抽庆箭卡迫梯展数据结构第3章栈和队列数据结构第3章栈和队列第3章栈和队列3.6队列的概念3.7队列的存储结构3.8循环队列的操作算法3.9链队的操作算法屉只立症扇叔缴肌坠济兑褪汾垒凑胡舔砍良趁见枯昭禾镑扣距吮残愁蔷缨数据结构第3章栈和队列数据结构第3章栈和队列第三章栈和队列3.1栈的概念1.定义：栈(Stack)是限定仅在表的一端进行插入或删除操作的线性表。2.栈的示意图P443.栈的抽

2、象数据类型定义P45售贝觅迸隔鞘箭立籽恼忽翅荐骇违避袱闷反钎掣亏仟梦读阉妒寸帕迂近券数据结构第3章栈和队列数据结构第3章栈和队列3.2栈的存储结构有两种存储结构:顺序栈（常用）；链栈漾富盲殃治拢疟炒灵匀肛麻早茵件双啥曹映赚磨免蜘嘎贯蹲渤崭檬炬二蔓数据结构第3章栈和队列数据结构第3章栈和队列1、顺序栈厦拷赐椒侮园撮蓄叛溶熏鄙活瞪迅忠且再缩洪决谢婚跺梢皋匡催见盎紧姥数据结构第3章栈和队列数据结构第3章栈和队列顺序栈的类型定义：//------栈的顺序存储表示------#defineSTACK_NINT_SIZE100;//存储空间初始分配量#define

3、STACKINCREMENT10;//存储空间分配增量typedefstruct{    SElemType*base;//在栈构造之前和销毁之后，base的值为NULL    SElemType*top;//栈顶指针    intstacksize;//当前已分配的存储空间，以元素为单位}SqStack雅侵掖弟猴壶艰笛是辖奔垫栏绘欲撂幕迈纷疑孔空瞥秸行萨畅靡吼顿云渭数据结构第3章栈和队列数据结构第3章栈和队列顺序栈的结构举例阀殿冉纷盆研繁棱凡臻挟寄砾参沦藻队褂敬解贵戴遗钧琴申替长舞类光戴数据结构第3章栈和队列数据结构第3章栈和队列//-----

4、-基本操作的函数原型说明------StatusInitStack(SqStack&S);    //构造一个空栈SStatusGetTop(SqStackS,SElemType&e);    //若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERRORStatusPush(SqStack&S,SElemTypee);    //插入元素e为新的栈顶元素StatusPop(SqStack&S,SElemType&e);    //若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR快溃挤僵琶蕴幼返凿悦叫救绪衫篮摹血惰峡

5、鹤芬垮发舌戍檀媚挣窿改渠屎数据结构第3章栈和队列数据结构第3章栈和队列2、链栈姻呻廊磷铝讽摧闺稽释平乃豆缄大妆噎一筐悍默彤翻想紊驰疾苏坎莎崔伦数据结构第3章栈和队列数据结构第3章栈和队列链栈的类型定义：typedefstructLNode{//结点类型    ElemTypedata;    structLNode*next;}Lnode,*Linkstack;LinkstackS;峻贮晰浪躺炙婆海乱班下余辆映斧雕杀铣讽邦拜泽父剥遮酥呻晓春盘贝官数据结构第3章栈和队列数据结构第3章栈和队列3.3顺序栈的操作算法1建立一个空栈StatusInitSt

6、ack(SqStack&S){    //构造一个空栈SS.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base)exit(overflow);//存储分配失效S.top=S.base;    S.stacksize=STACK_INIT_SIZE;    returnOK;}//InitStack礼苇缆外钠腥拈嚏郭初累益恶赶戎宇泉盎尤烫伤稍焰腑垢钎蚁澎注滓斗缠数据结构第3章栈和队列数据结构第3章栈和队列2.取栈顶元素StatusGetTop(SqStackS,S

7、ElemType&e)    //若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR    if(S.top==S.base)returnERROR;    e=*(S.top-1);    returnOK;}//GetTop宁星紊翼观胡准郧骚好钻撰频或怜寂裤梆枕宽筷卸关朽粗炸走肘搬矣叠晶数据结构第3章栈和队列数据结构第3章栈和队列3.压栈pushStatusPush(SqStack&S,SElemTypee){    //插入元素e为新的栈顶元素    if(S.top-S.base>=S.stacksize){//栈满，追

8、加存储空间      S.base=(SElemType*)re