数据结构与算法分析(第3章 栈与队列)ppt课件.ppt

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

1、数据结构与算法廊坊师范学院数学与信息科学学院授课教师：崔业勤第三章栈与队列本章重点难点重点：栈和队列的逻辑结构定义以及在两种(顺序,链式)存储结构上如何实现栈和队列的基本运算.难点：循环队列的边界处理.3.1栈●栈：是一种特殊的线性结构，只能在一端进行插入和删除的线性表。●栈的相关概念：（1）栈顶：线性表中进行插入删除的一端（2）栈底：与栈顶对应的一端（3）入栈：插入元素（push,压栈）（4）出栈：删除元素（pop,弹出）123栈的结构模拟特点:后进先出栈顶栈底3.1.1栈的基本运算入栈出栈读取栈顶元素栈是否为空等栈的抽象数据

2、类型定义TempateClassStack{boolPush(constTvalue);boolPop(T&value);boolTop(T&value);boolEmpty();..};3.1.2栈的物理实现—顺序栈●相关变量：（1）栈的最大长度：intmaxsize（2）栈顶的位置：inttop（3）栈的指针变量：T*sttemplateclassarrStack{private:intmaxsize;//栈的最大长度inttop;//栈顶下标T*st;//指向栈的指针public:arrSt

3、ack(intsize){maxsize=size;top=-1;st=newT[maxsize];}arrStack(){top=-1;}~arrStack(){delete[]st;}voidClear(){//清空栈的内容top=-1;}//显示栈元素栈的顺序实现boolPush(constTitem){//入栈if(top==maxsize-1){cout<<"stackisfull!"<

4、ntrue;}}//出栈boolPop(T&item){if(top==-1){cout<<"thestackisempty,can'tpop!"<Topp{if(top==-1){cout<<"thestackise

5、mpty,can'tread!"<*top（2）栈中元素的个数：intsize注意：栈的结构中top了代替头指针4321top栈顶栈底templateclassLink{public:Tdata;//结点的数据域Link*next;//结点的指针域Link(Tinfo,Link*nextValue=NULL)//具有两个参数的

6、List构造函数{data=info;next=nextValue;}Link(Link*nextValue=NULL)//具有一个参数的List构造函数{next=nextValue;}};栈的链式实现#include"link.h"templateclasslinkstack{private:Link*top;//指向栈顶的指针intsize;//存放元素的个数public:linkstack(){top=NULL;size=0;}~linkstack(){clear();}voidclear()

7、{while(top!=NULL){Link*tmp=top;top=top->next;deletetmp;}size=0;}//入栈boolpush(constTitem){Link*tmp=newLink(item,top);top=tmp;size++;returntrue;}//出栈boolpop(T&item){Link*tmp;if(size==0){cout<<"thestackisempty,can'tpop!"<data;tmp

8、=top->next;deletetop;top=tmp;size--;returnfalse;}//取栈顶元素booltopp(T&item){if(size==0){cout<<"thestackisempty,can'tread!"<