合工大数据结构02-栈.ppt

合肥工业大学计算机与信息学院合肥工业大学计算机与信息学院*如何写出来该函数头？？？**中缀表达式，前缀表达式，后缀表达式？？？分别怎么求？？*输出序列有多少/ray_seu/article/details/8454347种可能性？？**数据结构（第二章栈）DataStructures张晶计算机与信息学院**第二章栈第二章栈（stack）2.1栈的定义和运算2.2顺序栈2.3栈的应用第二章栈*栈是软件设计中最基本的数据结构，这是本课程所介绍的第一种数据结构。学习栈结构时，需要掌握哪些方面的内容？为此，回顾一下上一章所介绍的数据结构的组成部分。由此可知，对每一种结构的学习的组成部分。逻辑结构分析运算实现（算法）运算定义存储结构数据结构的组成2.1栈的定义和运算*2.1.1栈的定义栈是只能在一端插入和删除元素的线性表。术语：栈顶,栈底,入栈（压栈）,出栈（弹栈）anan-1……a1入栈(PUSH)出栈(POP)栈顶(top)栈底(bottom)逻辑结构和运算a1a2…an特性：后进先出(LIFO)----LastinFirstout…a1a2anan…a2a12.1栈的定义和运算*2.1.2栈的运算1.栈的基本运算定义对栈的基本运算有如下几个：(1)初始化：设置栈为空。(2)判断栈为空：若为空，则返回TRUE，否则返回FALSE.(3)判断栈为满：若为满，则返回TRUE，否则返回FALSE.(4)取栈顶元素：取出栈顶元素。条件：栈不空。否则，应能明确给出标识，以便程序的处理。(5)入栈：将元素入栈，即放到栈顶。如果栈满，怎样处理？(6)出栈：删除当前栈顶的元素。如因为栈空而不能进行，应怎样处理？运算定义2.1.2栈的运算*2.栈的运算的C++描述如何用C++描述栈的内容和运算？一种方法是：将栈的有关数据和运算封装在一起，以C++的类的形式来封装描述。封装的数据和运算要便于被有关程序来调用。因此，栈的C++描述的框架如下所示：classstack{};运算描述部分数据描述部分类的名称类的框架2.1.2栈的运算*下面讨论栈的运算的C++描述的细节，先给出每一个运算的对应描述：初始化函数的描述栈的C++类描述：classstack{stack();…栈的数据成员};栈的运算(1)初始化：设置栈为空。(2)判断栈为空：若为空，则返回TRUE，否则返回FALSE.(3)判断栈为满：若为满，则返回TRUE，否则返回FALSE.(4)取栈顶元素：取出栈顶元素。条件：栈不空。否则，应能明确给出标识，以便程序的处理。(5)入栈：将元素入栈，即放到栈顶。如果栈满，怎样处理？(6)出栈：删除当前栈顶的元素。如因为栈空而不能进行，应怎样处理？采用C++的构造函数2.1.2栈的运算*判断函数的对应栈的C++类描述：classstack{stack();Boolempty()Boolfull()