使用后进先出法实现先进先出

Question

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

您将如何使用后进先出法实现先进先出？

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

但这当然非常慢，它形成了这样一个简单的循环：

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

在FIFO的标准实现上执行O（n²），而不是O（n）

当然，后进先出法并不是为了先出先出，使用"原生"FIFO和基于后进先出的伪FIFO也不会有同样的复杂性，但我认为肯定有一种方法比O（n²）做得更好。有人知道吗？

提前谢谢。

Answer 1

您可以使用2个后进先出法[堆栈]获得每个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)（未摊销），它要复杂得多，需要更多的堆栈，请查看此后中的一些答案

编辑：复杂性分析：

1. 每个insert()是三次O(1)[只是将其推到stack1]
2. 注意，每个元素最多为push()ed和pop()ed两次，一次来自stack1，一次源自stack2。由于没有比这些更多的操作，对于n元素，我们最多有2n push() s和2n pop() s，这给了我们最多4n * O(1)的复杂性[因为pop()和push()都是O(1)]，这就是O(n)-，我们得到的摊销时间为：O(1) * 4n / n = O(1)

Answer 2

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

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