使用LIFO实施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)

   复杂性[因为are

   pop()

   和

   push()

   are

   O(1)

   ，这是

   O(n)

   -并且我们得到了以下的摊销时间：

   O(1) * 4n / n = O(1)