使用LIFO实施FIFO [英] Implementing FIFO using LIFO

问题描述

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

Looking at some algorithm exercices on the net, I found an interesting one :

您将如何使用LIFO实现FIFO？

How would you implement a FIFO using a LIFO ?

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

I tried myself but I ended up with only one solution : each time we want the front element of the FIFO, copy the lifo into another lifo (excluding last element, which is the front), get the front element and remove it, then copy back the second LIFO into the first LIFO.

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

But this is of course horribly slow, it makes a simple loop like this :

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

要 O（n²）而不是 O（n）关于FIFO的标准实现。

going O(n²) instead of O(n) on a standard implementation of the FIFO.

当然，LIFO并不是做FIFO的，我们当然不会拥有通过使用基于LIFO的本机 FIFO和伪FIFO可以实现相同的复杂性，但是我认为肯定有比O（n²）更好的方法。有人知道吗？

Of course, LIFO are not made to do FIFO and we won't certainly have the same complexity by using a "native" FIFO and a fake-FIFO based on a LIFO, but I think there is certainly a way of doing better than O(n²). Has anyone an idea about that ?

预先感谢。

推荐答案

您可以获得 O（1）的摊销时间复杂度 每个OP FIFO [队列]，使用2个LIFO [堆栈]。

You can get amortized time complexity of O(1) per OP FIFO [queue] using 2 LIFOs [stacks].

假设您有 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） [未摊销]，它要复杂得多，需要更多堆栈，请查看此帖子

To get real O(1) [not amortized], it is much more complicated and requires more stacks, have a look at some of the answers in this post

编辑：复杂度分析：

1. 每个 insert（）都是 O（1） [只是将其推入 stack1 ]


2. 请注意，每个元素都是 push（） ed和 pop（）最多两次，一次来自 stack1 ，一次来自 stack2 。由于没有其他操作，对于 n 元素，我们最多只有 2n push（） s和 2n pop（） s，最多可以给我们 4n * O（1）复杂度[因为 pop（）和 push（）是 O（1）]，即 O（n）-我们得到了摊销时间of： O（1）* 4n / n = O（1）

1. each insert() is trivaially O(1) [just pushing it to stack1]
2. Note that each element is push()ed and pop()ed at most twice, once from stack1 and once from stack2. Since there is no more ops then these, for n elements, we have at most 2n push()s and 2n pop()s, which gives us at most 4n * O(1) complexity [since both pop() and push() are O(1)], which is O(n) - and we get amortized time of: O(1) * 4n / n = O(1)

这篇关于使用LIFO实施FIFO的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！