Q

如何使用堆栈（LIFO）实现等同于复杂度的先进先出（FIFO）推送和弹出操作的FIFO

2017-02-11 77 views 0 likes

0

我理解传统的使Push操作昂贵或流行操作昂贵的方法。如何使用堆栈（LIFO）实现等同于复杂度的先进先出（FIFO）推送和弹出操作的FIFO

如何使push和pop具有相同的复杂性？

2017-02-11 Krishna Karthick

+0

有2个堆栈指针，一个用于插入，另一个用于弹出 – Spektre

+0

我只能使用堆栈的push（），pop（），isempty（）函数。不允许指针（指针会使问题变得非常简单）。 –

+0

@PaulHankin：我试图平衡链接的顶级答案的Insert（）和take（）函数的复杂性。 –

A

回答

2

这是标准的面试问题。常见的想法：minus x minus = plus。您可以使用2层测序堆栈：

PUT部署数据到堆栈栈2
如果stack2中是空的1
GET提取数据 - 从堆栈中复制所有数据堆栈2，从顶部1到顶部2.

2017-02-11 18:47:22 maxihatop

+0

+1。但是请注意，这会导致*摊销*固定时间：每隔一段时间，'流行'操作将会很昂贵（因为它必须立即复制所有内容），但是这会平均持续时间，因为一个昂贵的'流行'与随后的便宜'流行'的数量成正比。 – ruakh

相关问题