使用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

你可以分期时间复杂度的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)[未摊销],它要复杂得多,需要更多堆栈,看看这篇文章中的一些答案

编辑:复杂性分析:

1. 每个insert()都是平凡的O(1)[只是推动它stack1]
2. 请注意,每个元素都被push()ED和pop()从ED最多两次,一次是stack1从一次stack2.由于没有更多的OPS那么这些为n元素,我们在大多数2n push()S和2n pop()S,这让我们在最4n * O(1)复杂[因为这两个pop()和push()是O(1)],这是O(n)- ,我们得到的分期时间:O(1) * 4n / n = O(1)