复习课件-栈队列数组跳表15级.pdf

《复习课件-栈队列数组跳表15级.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、•2016/10/30课程内容框架II栈、队列、数组•概念、原理、方法•栈(Stack)•队列(Queue)–逻辑结构–基本概念–基本概念–存储结构–顺序存储结构–顺序存储结构–基本操作–链式存储结构–链式存储结构•设计、分析–应用–应用–时间复杂度–空间复杂度•问题求解•特殊矩阵(Matrix)的压缩存储–选择：数据->结构->方法/操作–选择：语言->设计->实现ComputerScienceandEngineeringSoutheastUniv.,WangWei.ComputerScienceandEngineeringSoutheastUniv.,WangWei.栈

2、(Stack)栈的抽象数据类型•只允许在一端插入和删除的线性表templateclassStack{//栈的类定义•允许插入和删除的一端称为栈顶(top)，另一端public:称为栈底(bottom)退栈进栈Stack(){};//构造函数virtualvoidvirtualvoidPush(Ex)(Ex)=0;//进栈•特点topvirtualboolPop(E&x)=0;//出栈an-1后进先出(LIFO)virtualboolgetTop(E&x)=0;//取栈顶an-2virtualboolIsEmpty()=0;//判栈空virtualboolIsF

3、ull()=0;//判栈满a0}；bottomComputerScienceandEngineeringSoutheastUniv.,WangWei.ComputerScienceandEngineeringSoutheastUniv.,WangWei.顺序栈类的定义#include#include#include“stack.h”栈的数组存储表示—顺序栈templateclassSeqStack:publicStack01234567890123456789maxSSiize-1{//顺序栈类定义eleme

4、ntsprivate:E*elements;//栈元素存放数组top(栈空)inttop;//栈顶指针intmaxSize;//栈最大容量voidoverflowProcess();//栈的溢出处理ComputerScienceandEngineeringSoutheastUniv.,WangWei.ComputerScienceandEngineeringSoutheastUniv.,WangWei.•1•2016/10/30public:SeqStack(intsz=50);//构造函数～SeqStack(){delete[]elements;}//析构函数topbvo

5、idPush(Ex);//进栈topaaboolPop(E&x);//出栈top空栈a进栈b进栈boolgetTop(E&x);//取栈顶内容boolIsEmpty()const{returntop==-1;}topetopeeboolIsFull()const{returntop==maxSize-1;}ddtopd};cccbbbaaae进栈f进栈溢出e退栈ComputerScienceandEngineeringSoutheastUniv.,WangWei.ComputerScienceandEngineeringSoutheastUniv.,WangWei.temp

6、latevoidSeqStack::Push(Ex){dtopcc//若栈不满,则将元素x插入该栈栈顶,否则溢出处理btopbbif(IsFull()==true)overflowProcess;//栈满aatopaelements[++top]=x;//栈顶指针先加1,再进栈};d退栈c退栈b退栈templateboolSeqStack::Pop(E&x){//函数退出栈顶元素并返回栈顶元素的值if(IsEmpty()==true)returnfalse;x=elements[top--];//栈顶指针退1areturntrue;/

7、/退栈成功topa退栈top空栈};ComputerScienceandEngineeringSoutheastUniv.,WangWei.ComputerScienceandEngineeringSoutheastUniv.,WangWei.栈满操作templatetemplateboolSeqstack::getTop(E&x){voidSeqStack::overflowProcess(){//若栈不空则函数返回该栈栈顶元素的地址//私有