使用LIFO实施FIFO

小编典典

使用LIFO实施FIFO

algorithm

通过网上的一些算法，我发现了一个有趣的例子：

您将如何使用LIFO实现FIFO？

我尝试了一下，但最终只有一个解决方案：每次我们想要FIFO 的 最前面的 元素时，将lifo复制到另一个lifo（ 不包括
最后一个元素，即最前面的元素），获取front元素并将其删除，然后复制将第二个LIFO放回第一个LIFO。

但这当然是非常慢的，它产生了一个像这样的简单循环：

for(!myfifo.empty()) {
  myfifo.pop();
}

去 O（N²） ，而不是 为O（n） 上的标准实现FIFO的。

当然，不是让LIFO做FIFO，通过使用基于LIFO的“本机”
FIFO和假FIFO，我们当然不会具有相同的复杂性，但是我认为肯定有比O做得更好的方法（n²）。有人对此有想法吗？

提前致谢。

阅读 418

2020-07-28

共1个答案

小编典典

你可以分期时间复杂度的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)复杂性[因为are pop()和push()are O(1)，这是O(n)-并且我们得到了以下的摊销时间：O(1) * 4n / n = O(1)

2020-07-28