数据结构实验二(栈和队列)

《数据结构实验二(栈和队列)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验二栈和队列的基本操作及其应用一、实验目的1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际中灵活应用。2、掌握栈和队列的特点，即后进先出和先进先出的原则。3、掌握栈和队列的基本运算，如：入栈与出栈，入队与出队等运算在顺序存储结构和链式存储结构上的实现。二、实验内容本次实验提供2个题目，每个题目都标有难度系数，*越多难度越大，学生可以根据自己的情况任选一个！题目一：回文判断（*）[问题描述]对于一个从键盘输入的字符串，判断其是否为回文。回文即正反序相同。如“abba”是回文，而“abab”不是回文。[基本要求]（1）数据从键盘读入；（2）输出要判断的

2、字符串；（3）利用栈的基本操作对给定的字符串判断其是否是回文，若是则输出“Yes”，否则输出“No”。[测试数据]由学生任意指定。题目二：栈和队列基本操作[基本要求]1、实现栈的基本操作六项基本操作的机制是：初始化栈：init_stack(S)；判断栈空：stack_empty(S)；取栈顶元素：stack_top(S,x)；入栈：push_stack(S,x)；出栈：pop_stack(S)；判断栈满：stack_full(S)2、实现队列的基本操作六项基本操作的机制是：初始化队列：init_queue(Q)；判断队列是否为空：queue_empty(Q)

3、；取队头元素：queue_front(Q,x)；入队：enqueue(Q,x)；出队：outqueue(Q,x)；判断队列是否为满：queue_full(Q)[测试数据]由学生任意指定。题目三：商品货架管理（**）[问题描述]商店货架以栈的方式摆放商品。生产日期越新的越靠近栈底，出货时从栈顶取货。一天营业结束，如果货架不满，则需上货，也就是将商品摆放到货架上，要求生产日期越近的商品越靠近栈顶。这样就需要倒货架，使生产日期越新的越靠近栈底。[基本要求]设计一个算法，保证每一次上货后保持生产日期越新的商品越靠近栈底。[实现提示]可以用一个队列和一个临时栈作为周转

4、。[测试数据]由学生任意指定。三、实验前的准备工作1、掌握栈的逻辑结构和存储结构。2、熟练掌握栈的出栈、入栈等操作。3、掌握队列的逻辑结构和存储结构。4、熟练掌握队列的出队、入队等操作四、实验报告要求1、实验报告要按照实验报告格式规范书写。*2、写出算法设计思路。3、实验上要写出多批测试数据的运行结果。4、结合运行结果，对程序进行分析。题目四：Rails（ACM训练题）DescriptionThereisafamousrailwaystationinPopPushCity.Countrythereisincrediblyhilly.Thestationwas

5、builtinlastcentury.Unfortunately,fundswereextremelylimitedthattime.Itwaspossibletoestablishonlyasurfacetrack.Moreover,itturnedoutthatthestationcouldbeonlyadead-endone(seepicture)andduetolackofavailablespaceitcouldhaveonlyonetrack.Thelocaltraditionisthateverytrainarrivingfromthedire

6、ctionAcontinuesinthedirectionBwithcoachesreorganizedinsomeway.AssumethatthetrainarrivingfromthedirectionAhasN<=1000coachesnumberedinincreasingorder1,2,...,N.ThechieffortrainreorganizationsmustknowwhetheritispossibletomarshalcoachescontinuinginthedirectionBsothattheirorderwillbea1,a

7、2,...,aN.Helphimandwriteaprogramthatdecideswhetheritispossibletogettherequiredorderofcoaches.YoucanassumethatsinglecoachescanbedisconnectedfromthetrainbeforetheyenterthestationandthattheycanmovethemselvesuntiltheyareonthetrackinthedirectionB.Youcanalsosupposethatatanytimetherecanbe

8、locatedasmanycoachesasnece