使用動態數組實現的堆棧

假設我們使用動態分配的數組實現堆棧。如果數組填滿，我們面臨着一個兩難的局面。從以下選項中，選擇最能描述我們的處理填充數組的策略的那一個。使用動態數組實現的堆棧

（一）我們宣佈一個新的數組，兩倍大的原稿，中的數據複製到新的空間 O（n）的總成本，一個序列的n個推動。

（b）我們聲明另一個陣列和保持軌道其中兩個（或更多）陣列的包含堆棧的當前頂部的堆棧類的私有成員。這使我們每次推O O（1）。

（c）對於一些固定的K，我們創建了一個新的陣列大小爲n + 2^k的和數據複製到新的空間，每按壓操作（1）O的平均成本。（d）我們避免使用動態分配數組來實現棧，因爲重新分配內存效率不高。

（e）這些答案都不是合理的回答。

我敢肯定，正確的答案是，但我不明白爲什麼這將是最好的比其他人？其他人是否更實際？他們對我來說似乎沒問題。例如，c與「a，no？」幾乎相同。爲什麼倍增更有利，然後增加一個常數？其他選項呢？爲什麼他們不工作？

來源

2011-04-05 Snowman

爲什麼加倍更有利：http://stackoverflow.com/questions/5232198/why-does-an-stl-vectors-capacity-grow-exponentially/5232342#5232342 – Cubbi 2011-04-05 03:09:27

呃... homeowrk？回家測試？ – Alex 2011-04-05 03:09:40

@亞歷山大 - 作業是允許的，但答案的方式是不同的（至少對我而言）。 – tvanfosson 2011-04-05 03:10:52

說你的堆棧是128個元素，你最終不得不存儲4096個元素。在加倍的時候你有多少次需要調整數組的大小，而每次增加128個項目呢？

來源

2011-04-05 03:08:42 tvanfosson

這看起來像家庭作業，可能是一個回家測試，所以我會故意留下我的答案。

a）嘗試提供O(n)索賠的證據。與你對b）的證明進行比較。

b）你如何存儲使用中的一組子陣列？（這是烏龜的一路下降。）

c）嘗試提供O(1)斷言的證據。比較你的a）證明。

d）所有替代品都有其自身的低效率。比較它們。請注意，在實時編程中，您不能使用動態重新分配的數組，並且必須使用類似鏈接列表的東西。爲什麼？ e）如果上述任何一種情況都是合理的，則這是非常普遍的錯誤。反之亦然。

來源

2011-04-05 03:13:37 btilly

使用動態數組實現的堆棧

回答

相關問題