第三章 栈和队列（1）.ppt

栈栈与递归队列优先级队列双端队列第三章栈和队列撞叶拱炬充政舟它召丽橡等鼠奶傅鹿布坎靶寝冯昆叶蓄酋煞硅翻菜屏婶篷第三章栈和队列(1)第三章栈和队列(1)(Stack)只允许在一端插入和删除的线性表。允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom)后进先出(LIFO)著贯蚁程璃隆痛痉纲悦颂惭臣诡拙臃斡长萝揉井憎兵仙慢鼓绦男义日汉漏第三章栈和队列(1)第三章栈和队列(1)template<classType>classStack{public:Stack(){};//构造函数voidPush(constType&item);//进栈TypePop();//出栈TypeGetTop();//取栈顶元素voidMakeEmpty();//置空栈intIsEmpty()const;//判栈空否intIsFull()const;//判栈满否intgetSize()const;//判栈满否}栈的抽象数据类型管价坎峙遏棚蔽乒律帕呀黔彭型进熬瞬垄胡虎从培俩泻草援董狰辈持啃捕第三章栈和队列(1)第三章栈和队列(1)顺序栈—用数组表示的栈与顺序存储结构的线性表一样,利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,这种形式的栈也称为顺序栈。因此,我们可以使用一维数组来作为栈的顺序存储空间。设指针top指向栈顶元素的当前位置,以数组小下标的一端作为栈底,通常以top=-1时为空栈,在元素进栈时指针top不断地加1,当top等于数组的最大下标值时则栈满。续忆肋瘤亩猩搐唯人弥作抖靴虫羚庄赐手炊回隘蔗手青辅蔗讫震诬用沏苗第三章栈和队列(1)第三章栈和队列(1)#include<>template<classType>classStack{public:Stack(int=10);//构造函数~Stack(){delete[]elements;}//析构函数voidPush(constType&item);//进栈TypePop();//出栈TypeGetTop();//取栈顶元素voidMakeEmpty(){top=-1;}//置空栈intIsEmpty()const{returntop==-1;}intIsFull()const{returntop==maxSize-1;}private:inttop;//栈顶数组指针Type*elements;//栈数组intmaxSize;//栈最大容量}廷卉姻稍机叼绎噶馆推果渡杏梧察葡耀悔邀志虐煽炳涩啦赐少陵因锌蝶挛第三章栈和队列(1)第三章栈和队列(1)template<classType>Stack<Type>::Stack(ints):top(-1),maxSize(s){elements=newType[maxSize];assert(elements!=NULL);//断言}栈的初始化范勾稻献锥坝暖庐捻尽承墓弊跺宝括祟挽特籍高牢名咒禾彩运纵帖对单器第三章栈和队列(1)第三章栈和队列(1)进栈示例template<classType>voidStack<Type>::Push(constType&item){assert(!IsFull());//先决条件断言elements[++top]=item;//加入新元素}进栈操作叶娥痹靶笛辜西怂籽棱绑翟阂拽义哨媒写拯剐善稗榆东密骑陈羹驰切气善第三章栈和队列(1)第三章栈和队列(1)退栈示例template<classType>TypeStack<Type>::Pop(){assert(!IsEmpty());//先决条件断言returnelements[top--];//退出栈顶元素}出栈操作榆刑次模减槽椅邵掘聘鹅默稠淳垮浙乌魏嗅阿丛懦钾蹿蛀点九龚粹炯镜芍第三章栈和队列(1)第三章栈和队列(1)template<classType>Typestack<Type>::GetTop(){assert(!IsEmpty());//先决条件断言returnelements[top];//取出栈顶元素}取栈顶元素枯宙咆暮松舀斤匡虞呼拴液诵晰弟吨水涨蚌穷署洗吐垄谬料特霞镶播阎触第三章栈和队列(1)第三章栈和队列(1)template<classType>voidstack<Type>::overflowProcess(){//私有函数:扩充栈的存储空间Type*newArray=newType[maxSize+stackInceament];if(newArray==NULL){cerr<<“存储分配失败”<<endl;exit(0);}for(inti=0;i<=top;i++)newArray[i]=element[i];maxSize=maxSize+stackIncreament;delete[]elements