数据结构与程序设计-堆栈

《数据结构与程序设计-堆栈》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、教育部高等教育司推荐国外优秀信息科学与技术系列教学用书数据结构与程序设计——C++语言描述（影印版）DataStructuresandProgramDesigninC++RobertL.KurseAlexandeerJ.Ryba主讲：中山大学计算机系高集荣E_mail:Gaojr@163.netPDF文件使用"pdfFactoryPro"试用版本创建www.fineprint.com.cn第2章堆栈2.1堆栈的说明(StackSpecications)2.2堆栈的实现(ImplementationofStacks)2.3堆栈的应用之一桌面计算器

2、(ADeskCalculator)2.4堆栈的应用之二括号匹配(BracketMatching)2.5抽象数据类型以及它们的实现(AbstractDataTypesandTheirImplementations)2004年3月11日《数据结构与算法》讲义2PDF文件使用"pdfFactoryPro"试用版本创建www.fineprint.com.cn2.1堆栈的说明n栈(Stack)是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。当表中没有元素时称为空栈。n假设栈S=(a1，a

3、2，a3，…an)，则a1称为栈底元素，an为栈顶元素。栈中元素按a1，a2，a3，…an的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈称为后进先出表（LIFO）。2004年3月11日《数据结构与算法》讲义3PDF文件使用"pdfFactoryPro"试用版本创建www.fineprint.com.cnn例如一叠书或一叠盘子。2004年3月11日《数据结构与算法》讲义4PDF文件使用"pdfFactoryPro"试用版本创建www.fineprint.com.cn出栈入栈栈顶anan-1……a2栈

4、底a1图2-1栈的后进先出示意图2004年3月11日《数据结构与算法》讲义5PDF文件使用"pdfFactoryPro"试用版本创建www.fineprint.com.cn§作为一种抽象数据类型，常用的栈运算有:运算含义MakeNull(S)使S成为一个空栈。Top(S)这是一个函数，函数值为S中的栈顶元素。Pop(S)从栈S中删除栈顶元素，简称为抛栈。Push(S,x)在S的栈顶插入元素x，简称为将元素x入栈。Empty(S)这是一个函数。当S为空栈时，函数值为true，否则函数值为false。§栈有两种存储表示方式：顺序表示和链式表示。它们

5、可以分别用数组实现和指针实现。§本章介绍顺序表示。2004年3月11日《数据结构与算法》讲义6PDF文件使用"pdfFactoryPro"试用版本创建www.fineprint.com.cnn使用C++STL(StandardTemplateLibrary)中堆栈的实现:#includen有了以上的声明就可以直接初始化一个空栈对象并且对它进行push、pop、top以及empty等操作，另外可以使用C++的模板参数(templateparameter)指定堆栈元素的不同数值类型，例如：stacknumbers;st

6、acknumbers;2004年3月11日《数据结构与算法》讲义7PDF文件使用"pdfFactoryPro"试用版本创建www.fineprint.com.cn第一个例子:表的逆置(FirstExample:ReversingaList)#includeintmain()/*Pre:Theusersuppliesanintegernandndecimalnumbers.Post:Thenumbersareprintedinreverseorder.Uses:TheSTLclasstackanditsmethods*/{

7、intn;doubleitem;stacknumbers;//declaresandinitializesastackofnumberscout<<"Typeinanintegernfollowedbyndecimalnumbers.“<>n;for(inti=0;i>item;numbers.push(item);}cout<

8、()){cout<