看一下网上的一些算法练习,我发现了一个有趣的:
如何使用LIFO实现FIFO？
我试过自己,但我最终只得到了一个解决方案:每次我们想要FIFO 的前面元素,将lifo复制到另一个lifo(不包括最后一个元素,即前面),获取前面元素并将其删除,然后复制将第二个LIFO带回第一个LIFO.
但这当然非常慢,它就是这样一个简单的循环:
for(!myfifo.empty()) {
myfifo.pop();
}
去O(N²) ,而不是为O(n)上的标准实现FIFO的.
当然,LIFO不会做FIFO,我们通过使用"原生"FIFO和基于LIFO的假FIFO不一定具有相同的复杂性,但我认为肯定有一种比O更好的方法. (N²).有没有人对此有所了解？
提前致谢.
我有一个抽象的数据类型,可以看作是从左到右存储的列表,具有以下可能的操作:推送:在列表的左端添加一个新项目Pop:删除列表左端的项目Pull :删除列表右端的项目
使用三个堆栈和不断的额外内存来实现它,这样任何push,pop或pull操作的分摊时间都是不变的.堆栈具有基本操作,isEmpty,Push和Pop.
摊销时间的意思是"如果我花费这么长时间,我可以花费另一块时间将其存放在一堆时间中以便以后使用." 对于每次推送操作,花费三个恒定时间块,因此对于每个按下的元素,你有2个额外的恒定时间块.