javadocによると、
ArrayDeque クラスは、スタックとして使用すると Stack よりも高速になる可能性があります
ArrayDeque がスタックよりも高速になる方法がわかりません。次のように、リンクリストを使用してスタックが実装されているとします。
Push: Insert new element at the head, teamp->next = head; head = temp
(where temp is the element to be inserted)
Pop: Remove the element from head, and make head = head->next
多数の要素の場合、ArrayDeque のサイズを変更するためのオーバーヘッドが発生しますが、これは LinkedList を使用して実装された Stack には当てはまりません。では、ArrayDeque はスタックよりも正確にどの程度高速なのでしょうか?
ArrayDeque は Java コレクション フレームワークの一部であり、本質的にスレッド セーフになるように記述されていません。
スタックは、Vector および Hashtable とともに Java 1.0 に付属し、スレッド セーフな操作で実装されました (当時は良いアイデアのように思えたため)。スレッド ロックの取得と解放は時間的に比較的コストがかかるため、これらのデータ構造は JCF の同胞よりもはるかに遅くなります。
ほとんどの操作では、特にキューが安定したサイズに達し、それ以上大きくならない場合は、配列のサイズを変更する必要がないためです。
アイテムを追加するたびに、Stack新しいオブジェクトを割り当ててリンクを更新する必要があります。
ArrayDequeオブジェクトを配列に入れてインデックスを更新するだけです。
私の経験では、1 回のパスでリスト内のランダムなポイントから複数の要素を頻繁に追加または削除する場合にのみ、連結リストは配列リストよりも効率的です。それ以外の場合は、通常、配列リストの方が優れています。検索が高速で、ランダム アクセスが速く、メモリが少なくて済みます。ArrayDeque が配列に基づいている場合、その中に格納されている各アイテムに追加のノード オブジェクトを割り当てる必要はほとんどありません。
スタックには通常、リストの最後に追加/削除されたアイテムがあるため、配列ベースのソリューションがより効率的である可能性があります
キーワードは「ありそう」。サイズ変更が発生した場合は遅くなる可能性がありますが、スタックがそれほど大きくなることはありません。
主な操作が「含む」検索や「一括挿入」などでない限り、配列は他のデータ構造に比べて高速に動作します。「速い」部分は常に使用法に依存します。平均して、つまり平均時間をとれば、ArrayDeque は Stack よりも高速になります。