堆棧ADT（抽象數據類型）實現 - Array vs linked

Question

基於array vs linked實現Stack的優點和缺點是什麼？從我有限的知識，我覺得鏈接將總是是一個更好的方式來實現堆棧，因爲：

1）不需要隨機訪問。

2）陣列是低效的，因爲他們有被調整的時間（浪費），還他們使用的存儲效率低下（一些空間會被浪費）

我敢肯定，我在想念的東西在這裏是因爲：

1 ）java.util.Stack是基於數組（它是java.util.Vector的一個子類，它是創建java集合接口之前的遺留類，並且與ArrayList幾乎相似）。所以Java的創建者選擇了基於數組的實現。

2）香港專業教育學院的計算器說，「在另一方面，一個基於陣列的實現可能有更好的運行時行爲」讀答案here。這是什麼意思，雖然我不知道。

比較即時尋找應包括以下參數：

1）理論時間和存儲要求。

2）運行時的性能（如果從理論比較不同）。

請包括我都沒有提及，由於我缺乏知識的任何其他重要參數。即時通訊使用Java，如果這使得任何差異在結論。

P.S-I找不到在這個網站的任何其他答案在這個問題中提出的所有要點，所以請只將這個問題標記爲重複只有在我的所有問題都已被正確回答，並在其他問題中足夠詳細。

PPS-我知道這是一個非常長的問題，所以TIA對你的努力:)如果你覺得它太寬泛，那麼請評論如何分解它之前，你把它標記爲「太寬」，所以我可能根據需要編輯它。

Answer 1

首先，你應該知道，java.util.Stack是一個「遺留的collection」，可追溯到Java 1.0中的所有道路。它擴展了java.util.Vector，這確實是基於陣列的。但是，這通常被認爲是不好的對象設計。這並不意味着基於數組的堆棧是一件壞事，但您應該意識到，僅僅因爲JDK中的某些東西並不意味着這是個好主意。對於較舊的API尤其如此。

一個更現代的類棧的數據結構是java.util.ArrayDeque。它也是基於數組的。它還包含了許多其他功能，但如果你堅持自己的push和pop方法（相當於addFirst和removeFirst），它基本上是一個堆棧。請注意，在其文檔中提到，

當用作堆棧時，該類可能會比Stack更快。

如果你看一下實現，Stack，像Vector，是同步的，這樣可以有點慢下來。Stack的push和pop方法按照Vector方法實施，其也同步。這意味着額外的方法調用加嵌套同步。 （儘管JIT可能會優化大部分。）相比之下，ArrayDeque未同步，其類似堆棧的方法使用直接在其內部陣列上操作的簡單操作。請注意，我在這裏沒有做任何基準驗證文檔的索賠。

在任何情況下，ArrayDeque是用於需要類似堆棧行爲的問題的首選Java集合。

但是你問的是鏈接的數據結構，而不是基於數組的數據結構。我們將ArrayDeque與另一個Java鏈接的數據結構LinkedList進行比較。這實現了Deque，所以它也可以用作堆棧。你說，

1）不需要隨機訪問。

是的。請注意，ArrayDeque不提供隨機訪問，即使它是基於數組的。沒有任何優勢。

2）陣列是低效的，因爲它們必須被調整大小（浪費時間），並且還它們使用存儲低效（一些空間會被浪費）

的任何數據結構會產生一定的低效率。不過，不同的數據結構會有不同的折衷。如果ArrayDeque的數組大小不符合堆棧的典型容量，則必須調整其大小。但是一旦數組足夠大，就不需要不斷調整大小。如果堆棧收縮，則數組仍將佔用空的空間。這可以被看作是浪費，或者它可以被看作是保留內存，以便在堆棧再次增長時不必調整大小和複製。

將情況與LinkedList進行比較。在內部，每個列表元素都需要一個Node實例。 （請參閱源here。）每個實例包含三個引用：一個指向數據元素，一個指向下一個Node，另一個指向之前的Node。假設帶有壓縮指針的64位JVM，即每個引用32位。每個對象都有一個包含64位標記字和32位類指針的標題。這總共給出了六個32位字，或每個列表元素24字節。這六個單詞中只有一個是「有效載荷」 - 元素本身 - 因此每個元素有20個字節或83％的開銷！

相比之下，數組中的每個附加元素僅消耗引用該元素的空間或32位。

例如，在LinkedList中存儲1,000個元素會消耗大約24K的內存，但將它們存儲在ArrayDeque中僅消耗大約4K的內存。即使陣列的大小是容納1,000個元素的兩倍，那也只有8K - 仍然只是LinkedList大小的一小部分。

「另一方面一個基於陣列的實現可能有更好的運行時行爲」

這可能指的是遍歷鏈表比遍歷數組慢。有兩個原因。首先，鏈接節點佔用更多的內存，因此必須讀取更多的內存才能獲得相同的信息。每節點24字節，2.67個節點可以放入典型的64字節緩存行。其次，鏈接節點可能會隨機分佈在內存周圍，因此平均而言，每個緩存行的節點數量可能會少於此數量。結果是遍歷一個鏈表將導致很多緩存未命中，因爲這個引用的局部性很差。另一方面，由於數組中的引用密集堆積而沒有開銷，所以16個數組元素可以放入單個64字節緩存行中。遍歷數組會導致更少的緩存未命中。此外，內存子系統針對順序訪問進行了優化，因此它們可能能夠預取下一個高速緩存行，進一步降低內存開銷。

考慮到內存消耗和內存訪問的性能成本，基於陣列的結構通常是優選的。可能有些情況下，鏈接結構表現更好，但似乎比大多數人認爲的要少。

除了設置性能外，鏈接結構對於堆棧的數組結構還有一個明顯的優點：不可變的持久性。在基於陣列的堆棧上推送和彈出元素會固有地改變數組，因此以前的版本不再存在。在鏈接結構上推送和彈出節點不需要改變任何鏈接節點，因此即使其他人在此堆棧上推送和彈出元素，對堆棧過去狀態的引用也可以保持不變，並保持不變。實際上它們是不同的堆棧，共同的部分是共享的。這在函數式編程環境中非常有用。