Q

如何使用堆棧（LIFO）實現等同於複雜度的先進先出（FIFO）推送和彈出操作的FIFO

2017-02-11 95 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

相關問題