我有一个抽象的数据类型,可以看作是从左到右存储的列表,具有以下可能的操作:推送:在列表的左端添加一个新项目Pop:删除列表左端的项目Pull :删除列表右端的项目
使用三个堆栈和不断的额外内存来实现它,这样任何push,pop或pull操作的分摊时间都是不变的.堆栈具有基本操作,isEmpty,Push和Pop.
摊销时间的意思是"如果我花费这么长时间,我可以花费另一块时间将其存放在一堆时间中以便以后使用." 对于每次推送操作,花费三个恒定时间块,因此对于每个按下的元素,你有2个额外的恒定时间块.
做一些假设:
这是功课
该段是作业的一部分
使用三个堆栈和不断的额外内存来实现它,这样任何push,pop或pull操作的分摊时间都是不变的.堆栈具有基本操作,isEmpty,Push和Pop.
然后我的第一个建议是忽略那些与你谈论链接列表的人.没错,这就是任何合理的人在没有三个堆栈要求的情况下实现它的方式,但是家庭作业的关键因素不是按照合理的人的方式来做,而是你的教练要你的方式.
我的第二点建议是获得一些积木,一副纸牌或一堆发泡胶杯并指定三个堆叠(例如带杯垫或其他东西).开始讨论将一个堆栈的内容传输到另一个堆栈时会发生什么,这应该会给你一个想法.
京公网安备 11010802040832号 | 京ICP备19059560号-6 