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

《合工大数据结构02-栈.ppt》由会员分享，可在线阅读，更多相关《合工大数据结构02-栈.ppt（29页珍藏版）》请在金锄头文库上搜索。

1、合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院1数数 据据 结结 构构（第二章第二章 栈栈） Data Structures张晶张晶计算机与信息学院计算机与信息学院 2024/8/122024/8/12合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院2第二章第二章 栈栈 第二章第二章 栈（stack） 2.1 栈的定义和运算 2.2 顺序栈 2.3 栈的应用 合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院3第二章第二章 栈栈栈是是软件件设计中最基本的数据中最基本的数据结构，构，这是本是本课程所介程所介绍的第一种数据的第一种数据结构。构。学学习栈结构构时，需要掌

2、握哪些方面的内容？，需要掌握哪些方面的内容？为此，回此，回顾一下上一章所介一下上一章所介绍的数据的数据结构的构的组成部分。成部分。由此可知，由此可知，对每一种每一种结构的学构的学习的的组成部分。成部分。逻辑结构逻辑结构分析分析 运算实现（算法）运算实现（算法） 运算定义运算定义 存储结构存储结构数据结构的组成数据结构的组成合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院42.1 栈的定义和运算2.1.1 栈的定义栈的定义o栈栈是只能在一端插入和删除元素的线性表。是只能在一端插入和删除元素的线性表。 术语术语：栈顶栈顶, 栈底栈底, 入栈（压栈）入栈（压栈）, 出栈（弹栈）出栈（弹栈）

3、 an an-1 a1入栈(PUSH) 出栈(POP) 栈顶(top)栈底(bottom)逻辑结构和运算逻辑结构和运算a1 a2 an 特性：后进先出特性：后进先出 ( LIFO )-Last in First out a1a2anana2a1合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院52.1 栈的定义和运算2.1.2 2.1.2 栈的运算的运算o1.1.栈的基本运算定的基本运算定义对栈的基本运算有如下几个：的基本运算有如下几个：(1)(1)初始化初始化 ：设置置栈为空。空。 (2)(2)判断判断栈为空空： 若若为空，空，则返回返回TRUETRUE，否，否则返回返回FALSE.

4、 FALSE. (3)(3)判断判断栈为满： 若若为满，则返回返回TRUETRUE，否，否则返回返回FALSE. FALSE. (4)(4)取取栈顶元素：元素：取出取出栈顶元素。元素。 条件：条件：栈不空。不空。 否否则，应能明确能明确给出出标识，以便程序的，以便程序的处理。理。(5)(5)入入栈：将元素入：将元素入栈，即放到，即放到栈顶。 如果如果栈满，怎，怎样处理？理？ (6)(6)出出栈：删除当前除当前栈顶的元素。的元素。 如因如因为栈空而不能空而不能进行，行，应怎怎样处理？理？ 运算定义运算定义合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院62.1.2 栈的运算2. 栈的运

5、算的的运算的C+描述描述o如何用如何用C+描述描述栈的内容和运算？的内容和运算？一种方法是：一种方法是：n将将栈的有关的有关数据数据和和运算运算封装在一起，封装在一起，n以以C+的的类的形式来的形式来封装封装描述。描述。n封装的数据和运算要便于被有关程序来封装的数据和运算要便于被有关程序来调用。用。o因此，因此，栈的的C+描述的框架如下所示： class stack ;运算描述部分运算描述部分数据描述部分数据描述部分类的名称类的名称类的框架类的框架合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院72.1.2 栈的运算o下面下面讨论栈的运算的的运算的C+描述的描述的细节，先，先给出每一

6、个运算的出每一个运算的对应描述：描述：n初始化函数的描述初始化函数的描述栈的栈的C+类描述：类描述： class stack stack(); 栈的数据成员 ;栈的运算栈的运算(1)(1)初始化初始化 ：设置栈为空：设置栈为空。 (2)(2)判断栈为空：判断栈为空： 若为空，则返回若为空，则返回TRUETRUE，否则返回，否则返回FALSE. FALSE. (3)(3)判断栈为满：判断栈为满： 若为满，则返回若为满，则返回TRUETRUE，否则返回，否则返回FALSE. FALSE. (4)(4)取栈顶元素：取出栈顶元素。取栈顶元素：取出栈顶元素。 条件：栈不空。条件：栈不空。 否则，应能明确

7、给出标识，以便程序的处理。否则，应能明确给出标识，以便程序的处理。(5)(5)入栈：将元素入栈，即放到栈顶。入栈：将元素入栈，即放到栈顶。 如果栈满，怎样处理？如果栈满，怎样处理？ (6)(6)出栈：删除当前栈顶的元素。出栈：删除当前栈顶的元素。 如因为栈空而不能进行，应怎样处理？如因为栈空而不能进行，应怎样处理？ 采用采用C+的的构造函数构造函数合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院82.1.2 栈的运算o判断函数的判断函数的对应栈的栈的C+类描述：类描述：class stack stack(); Bool empty() Bool full() 栈的数据成员栈的数据成员

8、;栈的运算栈的运算(1)(1)初始化初始化 ：设置栈为空。：设置栈为空。 (2)(2)判断栈为空：判断栈为空： 若为空，则返回若为空，则返回TRUETRUE，否则返回，否则返回FALSE. FALSE. (3)(3)判断栈为满：判断栈为满： 若为满，则返回若为满，则返回TRUETRUE，否则返回，否则返回FALSE. FALSE. (4)(4)取栈顶元素：取出栈顶元素。取栈顶元素：取出栈顶元素。 条件：栈不空。条件：栈不空。 否则，应能明确给出标识，以便程序的处理。否则，应能明确给出标识，以便程序的处理。(5)(5)入栈：将元素入栈，即放到栈顶。入栈：将元素入栈，即放到栈顶。 如果栈满，怎样处

9、理？如果栈满，怎样处理？ (6)(6)出栈：删除当前栈顶的元素。出栈：删除当前栈顶的元素。 如因为栈空而不能进行，应怎样处理？如因为栈空而不能进行，应怎样处理？判断为空的函数判断为空的函数判断为满的函数判断为满的函数const;const;合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院92.1.2 栈的运算o其他几个函数的其他几个函数的对应描述描述分析分析：（1）几个运算的条件可能有不成立的情况，）几个运算的条件可能有不成立的情况， 因此，需要因此，需要给予明确的反映。予明确的反映。（2）设立运算是否正常的立运算是否正常的类型型error_code，正常正常时返回返回success

10、,否否则返回返回错误类型，如型，如overflow, underflow等。等。 enum error_code success, overflow, underflow;（3）可以将）可以将这几个函数的几个函数的类型型设置置为error_code；（4）如果需要返回其他的）如果需要返回其他的值，可以作，可以作为参数来返回。参数来返回。合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院102.1.2 栈的运算由上述讨论可得到由上述讨论可得到其他几个函数其他几个函数的功能描述：的功能描述：（4)4)取栈顶元素取栈顶元素的运算功能描述：的运算功能描述： 如果栈不空，则取出栈顶元素到参数如果

11、栈不空，则取出栈顶元素到参数x x中，然后返回中，然后返回successsuccess。 否则，返回否则，返回downflowdownflow。 对应的运算函数为：对应的运算函数为： error_code get_top(elementtype &x) const;(5)(5)入栈入栈的运算功能描述：的运算功能描述： 如果栈不满，则将元素入栈，并返回如果栈不满，则将元素入栈，并返回successsuccess。 否则，返回否则，返回overflowoverflow。 对应的运算函数为：对应的运算函数为： error_code push(const elementtype x); 合肥工业大学合

12、肥工业大学 计算机与信息学院计算机与信息学院112.1.2 栈的运算(6)(6)出出栈的运算功能描述：的运算功能描述： 如果如果栈不空，不空，删除当前除当前栈顶的元素，并返回的元素，并返回successsuccess。 否否则，返回，返回underflowunderflow。 对应的运算函数的运算函数为： error_code pop();合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院122.1.2 栈的运算o由此得到由此得到栈的的类stack的函数成的函数成员列表如下：列表如下：class stack stack(); / 初始化初始化 Bool empty( ) const;

13、/ 判断空判断空 Bool full( ) const; / 判断判断满 error_code get_top(elementtype &x) const; / 取取栈顶元素元素 error_code push(const elementtype x); /入入栈 error_code pop(); / 出出栈 栈的数据成的数据成员;问题：上述：上述类的描述是否的描述是否还需要需要补充什么？充什么？合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院132.2 顺序栈o2.2.1 存储结构：存储结构： n假设有一个足够大的存储空间（数组）假设有一个足够大的存储空间（数组）data,可用于

14、存储栈的元素。可用于存储栈的元素。n则可将栈中元素连续地存储到数组的各元素则可将栈中元素连续地存储到数组的各元素-顺序存储方式顺序存储方式。n如下图所示：如下图所示：o其中：为了能随时知道栈中的元素个数，设置了一个计数变量其中：为了能随时知道栈中的元素个数，设置了一个计数变量count。o将数组将数组data和和count作为类作为类stack的数据成员。的数据成员。栈的存储结构栈的存储结构a1a2an01n-1maxlen-1ndatacount顺序栈存储结构合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院142.2 顺序栈o由此而得到由此而得到类stack的完整描述。的完整描述。

15、o封装封装类: class stack public: stack(); Bool empty()const; Bool full() const; error_code get_top(elementtype &x)const; error_code push(const elementtype x); error_code pop(); private: int count; elementtype datamaxlen; /定定义其它成其它成员; 这是起什么作用的？这是起什么作用的？作用是什么？作用是什么？合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院152.2 顺序栈o2.

16、2.2 运算运算实现：即：即类class的各函数成的各函数成员的具体的具体实现。初始化函数的初始化函数的实现： stack:stack() count = 0; a1a2an01n-1maxlen-1ndatacount合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院162.2 顺序栈判断空的函数的判断空的函数的实现： Bool stack:empty()const if ( count = 0 ) return TRUE; else return FALSE; 判断判断满的函数的的函数的实现： Bool stack:full()const if ( count = maxlen )

17、 return TRUE; else return FALSE; /等价于：等价于：return count = maxlen; a1a2an01n-1maxlen-1ndatacount合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院172.2 顺序栈取取栈顶元素的元素的实现： error_code stack:get_top(elementtype &x)const if ( empty() ) return underflow; else x = datacount - 1; return success; a1a2an01n-1maxlen-1ndatacount合肥工业大学

18、合肥工业大学 计算机与信息学院计算机与信息学院182.2 顺序栈入入栈的的实现： error_code stack:push(const elementtype x) if ( full() ) return overflow; datacount = x; count +; return success; a1a2an01n-1maxlen-1ndatacount合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院192.2 顺序栈出出栈的的实现 error_code stack:pop() if ( empty() ) return underflow; count -; retur

19、n success; 算法分析：算法分析： 时间性能性能 全部是全部是O(1) 其他方面的性能：空其他方面的性能：空间的分配？。的分配？。 a1a2an01n-1maxlen-1ndatacount合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院202.3 栈栈的应用表达式的计算： 模拟表达式：12+5*(2+3)*6/2-4的求解过程。例例例例运算符运算符 操作数操作数#12+5*(2+3)*6/2-4#12+5*(2+3)*6/2-4#操作数运算符各自依次入栈。操作数运算符各自依次入栈。出出栈栈规规则则：当当前前入入栈栈的的运运算算符符比栈顶的运算符优先级低。比栈顶的运算符优先级

20、低。合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院212.3 栈的应用 o表达式的计算表达式的计算 以表达式以表达式12+5*(2+3)*6/2-4的计算过程的实现为例来讨论栈结构在的计算过程的实现为例来讨论栈结构在实现对任意输入的通用表达式的计算中的作用实现对任意输入的通用表达式的计算中的作用 #12+5*(2+3)*6/2-4# 开始时，指向第一个开始时，指向第一个位置，准备读入，位置，准备读入，此时的两个栈均为空。此时的两个栈均为空。CurrentS=# #12+5*(2+3)*6/2-4# CurrentS=12 由由于于# #是是第第一一个个算算符，因而自动进栈。符，因而

21、自动进栈。读读到到操操作作数数（1212）自自动动进栈。进栈。12#合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院222.3 栈的应用 栈栈顶顶算算符符# #比比当当前前运运算算符符优优先先级级低，低，故算符故算符要入栈要入栈#12+5*(2+3)*6/2-4# # 12+#12+5*(2+3)*6/2-4# CurrentS= 依次读入依次读入5 5、（、（、2 2和后，和后，栈栈顶顶算算符符（比比当当前前算算符符优先级低，故优先级低，故要入栈要入栈+#12CurrentS= 52X(3+合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院232.3 栈的应用 #12+5*

22、(2+3)*6/2-4# CurrentS= ) (X+#512栈栈顶顶算算符符比比当当前前运运算算符符）优优先先级级高高，故故要要执执行行其其运运算算2+32+3并入栈并入栈#12+5*(2+3)*6/2-4# CurrentS= ) X+#512栈栈顶顶算算符符（与与当当前前运运算算符符）相相对对应应，故故要要出出栈栈，一一同同释放释放32+5(合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院242.3 栈的应用 #12+5*(2+3)*6/2-4# CurrentS=X +#12栈栈顶顶算算符符比比当当前前运运算算符符优优先先运运算算，故故要要执执行行运运算算5*55*5并入栈

23、并入栈#12+5*(2+3)*6/2-4# CurrentS=X +#12栈栈顶顶算算符符比比当当前前运运算算符符优优 先先 级级 低低 ， 故故要入栈要入栈X5525X6合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院252.3 栈的应用 #12+5*(2+3)*6/2-4# CurrentS=/ +#12栈栈顶顶算算符符比比当当前前运运算算符符/ /优优先先运运算算，故故 要要 执执 行行 运运 算算25*625*6并入栈并入栈#12+5*(2+3)*6/2-4# CurrentS=- +#12栈栈顶顶算算符符/ /比比当当前前运运算算符符优优先先级级高高，故故 要要 执执 行行

24、 / /运运 算算150/2150/2并入栈并入栈X625/1502#12+5*(2+3)*6/2-4# CurrentS=- #12栈栈顶顶算算符符比比当当前前运运算算符符优优先先，故故执执行行运算运算12+7512+75并入栈并入栈75+合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院262.3 栈的应用 #12+5*(2+3)*6/2-4# CurrentS=# #87栈栈顶顶算算符符比比当当前前运运算算符符优优先先级级高高，故故要要执执行行运运算算87-487-4并入栈并入栈#12+5*(2+3)*6/2-4# CurrentS=# #83栈栈顶顶算算符符与与当当前前运运算算

25、符符相相对对应应，故故要要一一同同释释放放，8383出出栈栈为最后结果为最后结果4-合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院27顺序栈本章习题(1)o2.1 对一个栈的输入序列a1,a2,a3, ,an，称由此栈依次出栈后所得到的元素序列为栈的合法输出序列。例如，假设栈S的一个输入序列为1,2,3,4,5，则可得到多个输出序列。例如，1,2,3,4,5就是一个合法的输出序列，同理，5,4,3,2,1和3,2,1,4,5也分别是其合法的输出序列。分别求解下列问题：（1）判断序列1,3,4,5,2是否是合法的输出序列。（2）对输入序列1,2,3,4,5，求出其所有的合法的输出序列

26、。（3*）设计算法以判断对输入序列1,2,3, ,n，序列a1,a2, a3, ,an是否是该栈的合法的输出序列（假设输出序列在数组A中）。o2.2 如果顺序栈中的第二个分量是记录元素个数的变量而不是栈顶指针，应如何实现各算法？合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院28顺序栈本章习题(2)o2.3 对一个合法的数学表达式来说，其中的各大小括号“”，“”，“”，“”，“(”和“)”应是相互匹配的。设计算法对以字符串形式读入的表达式S，判断其中的各括号是否是匹配的。o2.4 对表达式5+3*(12+4)/4-8，依次画出在求解过程中的各步骤中的栈的状态。o2.5 *设计算法以求解所读入的表达式的值。假设数据类型为整型，并且仅包含加减乘除四则运算。o2.6 *设计算法以求解所读入的表达式的值。假设数据类型为浮点型，并且仅包含加减乘除四则运算。合肥工业大学合肥工业大学 计算机与信息学院计算机与信息学院29结束o本章内容回顾o谢谢