使用LIFO实施FIFO
通过网上的一些算法,我发现了一个有趣的例子:
您将如何使用LIFO实现FIFO?
我尝试了一下,但最终只有一个解决方案:每次我们想要FIFO 的 元素时,将lifo复制到另一个lifo(
最后一个元素,即最前面的元素),获取front元素并将其删除,然后复制将第二个LIFO放回第一个LIFO。
但这当然是非常慢的,它产生了一个像这样的简单循环:
for(!myfifo.empty()) { myfifo.pop();
}
去 ,而不是 上的标准实现FIFO的。
当然,不是让LIFO做FIFO,通过使用基于LIFO的“本机”
FIFO和假FIFO,我们当然不会具有相同的复杂性,但是我认为肯定有比O做得更好的方法(n²)。有人对此有想法吗?
提前致谢。
回答:
你可以分期时间复杂度的O(1)
每个操作FIFO
[队列]使用2个LIFOs [堆栈。
假设你有stack1
,stack2
:
insert(e): stack1.push(e)
take():
if (stack2.empty()):
while (stack1.empty() == false):
stack2.push(stack1.pop())
return stack2.pop() //assume stack2.pop() handles empty stack already
push(1)|1| | |
|-| |-|
push(2)
|2| | |
|1| | |
|-| |-|
pop()
push 2 to stack2 and pop it from stack1:
|1| |2|
|-| |-|
push 1 to stack2 and pop it from stack2:
| | |1|
| | |2|
|-| |-|
pop1 from stack2 and return it:
| | |2|
|-| |-|
要获得真正的O(1)
[未摊销],它是更为复杂,需要更多的堆栈,在看一些答案的这个职位
复杂度分析:
- 每个
insert()
都很简单O(1)
[只需将其推入stack1
] - 请注意,每个元素的
push()
ed和pop()
ed最多两次,一次来自stack1
,一次来自stack2
。由于没有其他操作,因此对于n
元素来说,我们最多具有2n
push()
s和2n
pop()
s,这给我们带来了最大的4n * O(1)
复杂性[因为arepop()
和push()
areO(1)
,这是O(n)
-并且我们得到了以下的摊销时间:O(1) * 4n / n = O(1)
以上是 使用LIFO实施FIFO 的全部内容, 来源链接: utcz.com/qa/401794.html