使用LIFO实施FIFO_随笔

使用LIFO实施FIFO

你可以分期时间复杂度的

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)

[未摊销]，它是更为复杂，需要更多的堆栈，在看一些答案的这个职位

编辑： 复杂度分析：

每个
```
insert()
```
都很简单
```
O(1)
```
[只需将其推入
```
stack1
```
]
请注意，每个元素的
```
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)
```

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/zaji/5623044.html

使用LIFO实施FIFO

发表评论

评论列表（0条）