用LIFO实现FIFO

Question

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

如何使用LIFO实现FIFO？

我自己尝试了一下，但最后只有一个解决方案:每次我们想要FIFO的前端元素时，将LIFO复制到另一个lifo中(不包括最后一个元素，也就是前面的元素)，获取前端元素并删除它，然后将第二个lifo复制回第一个LIFO。

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

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

使用O(n平方)代替O(n)进行FIFO的标准实现。

当然，LIFO不是用来做FIFO的，我们使用“本地”FIFO和基于LIFO的假FIFO肯定不会有同样的复杂性，但是我认为肯定有一种方法比O(n平方)做得更好。有没有人知道这件事？

提前谢谢。

Answer 1

您可以使用2个LIFO堆栈获得每个OP FIFO队列的摊销时间复杂度 of 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都可以用数组实现，它们之间唯一的区别是尾指针和头指针的工作方式。如果您从LIFO开始，您可以添加两个额外的指针来反映FIFO的尾和头，然后添加使用FIFO指针添加、删除so的方法。

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