使用LIFO实现FIFO

Question

在网上查看一些算法练习时，我发现了一个有趣的问题：

如何使用LIFO实现FIFO？

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

但这显然非常慢，它生成了一个简单的循环，如下所示：

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

在标准FIFO实现中，时间复杂度为O(n²)而非O(n)。

当然，LIFO不是用来执行FIFO的，使用原生FIFO和基于LIFO的伪造FIFO肯定不会有相同的复杂度，但我认为肯定有比O(n²)更好的方法。有人有什么想法吗？

提前感谢。

- Undo

---

请参考以下链接：http://stackoverflow.com/questions/4906050/how-can-i-use-two-stackslifo-so-that-it-can-work-like-a-queuefifo - Alex Florescu

可能是重复的问题：如何使用三个栈实现队列？ - Marcin

Answer 1

您可以使用两个LIFO（后进先出）[堆栈]，每个OP FIFO [队列]的摊销时间复杂度为O(1)。

假设您有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) [非平摊]，需要更复杂的操作和更多的堆栈，请查看this post中的一些答案。

编辑：复杂度分析：

1. 每个insert()都是简单的O(1)[只需将其推到stack1中]
2. 请注意，每个元素最多只被push()和pop()两次，一次来自stack1，一次来自stack2。由于没有更多的操作，对于n个元素，我们最多有2npush()和2npop()，这给出了最多4n * O(1)的复杂度[因为pop()和push()都是O(1)]，这是O(n) - 我们得到摊销时间：O(1) * 4n / n = O(1)

- amit

---

是的，事实上这似乎是答案。我没有考虑到在弹出FIFO直到给定深度之前，您不必担心FIFO中正在输入什么...非常感谢。我会查看关于超过2个堆栈的链接。 - Undo

我在你编辑帖子之前就已经理解了，但现在这是一种非常专业的回答，非常感谢！ - Undo

@Undo：不客气，我还添加了一些简短的复杂度分析来证明这些解决方案确实具有O(1)摊销时间复杂度。 - amit

这行代码 stack1.push(stack2.pop()) 不应该是 stack2.push(stack1.pop()) 吗？你想要将所有元素从 stack1 移到 stack2 中... - Lawrence Benson

Answer 2

使用数组可以实现LIFO和FIFO，它们之间唯一的区别在于tail和head指针的工作方式。如果你从LIFO开始，可以添加两个额外的指针来反映FIFO的tail和head，然后添加Add、Remove等方法，使用FIFO指针。

输出类型将与专用的FIFO或LIFO类型一样快，但它将支持两者。您需要使用不同的类型成员，如AddToStack/AddToQueue，RemoveFromStack/RemoveFromQueue等。

- oleksii

---

实际上，指针并不能解决所有问题。在这里，我们考虑一个简单的LIFO，比如一个栈。你只能对它使用push()和pop()方法。既不能访问LIFO内部的内容，也不能使用指针，因为当弹出FIFO包装器的前端时，你如何将所有东西移动到LIFO的前端？ - Undo

这个答案假设你可以直接访问该结构并对其进行修改。通过这种方式，你将能够添加额外的指针和额外的方法。你的问题中没有任何内容表明不能修改LIFO结构。 - oleksii

我明白了。实际上问题不是“如何将LIFO转换为FIFO”，而是“如何使用LIFO实现FIFO”。看来我的表述不够清晰。但如果我能够访问内部内容，我基本上只需要将LIFO改变为FIFO即可...！ - Undo