4

多くの場合、スタックはリンクされたリストとして実装されます。配列表現は十分ではありません。配列では簡単にプッシュ ポップを実行できます。また、配列に対するリンク リストはコードを複雑にし、配列の実装よりも利点がありません。

リンクされたリストの実装がより有益である例を挙げていただけますか、それなしではできません。

4

5 に答える 5

2

スタックの実用的な実装の多くは、配列を使用して記述されていると言えます。たとえば、.NET スタックの実装では、バッキング ストアとして配列が使用されます。

通常、配列はより効率的です。これは、プロセッサの高速キャッシュ ラインにうまく収まる連続したメモリ内にすべてのスタック ノードを近くに保持できるためです。

リンクされたリストを使用するスタックの教科書的な実装を見ていると思います。それらの方が簡単に記述でき、バッキング配列ストアを管理し、成長/コピー/を考え出すために少し余分なコードを書く必要がないからです。予約領域ヒューリスティック。

さらに、メモリをほとんど使用しないように迫られている場合は、現在使用されていないスペースを「無駄」にしないため、リンク リストの実装が理にかなっている可能性があります。ただし、十分なメモリを備えた最新のプロセッサでは、通常、リンク リスト アプローチでページ フォールトを心配するよりも、配列を使用してキャッシュの利点を得る方が適切です。

于 2012-08-21T14:25:40.907 に答える
1

配列のサイズは制限されており、あらかじめ定義されています。それらの数がわからない場合は、リンクされたリストが最適なオプションです。

詳細な比較:-(+ リンク リストを支配するため、および - 配列の場合)

Size and type constraint:-

  1. (+) 配列のその他のメンバーは等距離に配置され、連続したメモリが必要ですが、反対側のリンク リストでは非連続メモリ ソリューションを提供できるため、巨大なデータの場合にメモリにも適している場合があります (リソースの CPU ポーリングを回避します)。 ）。

  2. (+) 配列をスタックとして使用していて、その配列が int 型であると仮定します。

Portability

  1. (+) 配列は、範囲外のインデックスの例外などの例外を引き起こす可能性がありますが、リンクされたリストではいつでもチェーンを増やすことができます。

Speed and performance

  1. (-) パフォーマンスに関するものであれば、明らかに複雑さのほとんどは配列の O(1) あたりになります。リンクされたリストの場合、トレースを開始するために開始ノードを選択する必要があり、これによりパフォーマンスが低下します。
于 2012-08-21T14:20:48.147 に答える
0

スタックのサイズが大きく変わる可能性がある場合、常に巨大な配列を割り当てる一般化されたルーチンがあると、スペースが無駄になります。

于 2012-08-21T14:18:51.520 に答える
0

明らかに、固定サイズの配列には、事前に最大サイズを知るという制限があります。
考慮すればdynamic array、Linked List vs. Arraysは、操作を実行するための複雑さを含む詳細をカバーしています。

于 2012-08-21T14:24:57.050 に答える
0

配列の O(n) と比較して、Push 操作と Pop 操作は O(1) 時間の複雑さであるため、スタックは Linked List を使用して実装されます。(Linked List での柔軟なサイズの利点は別として)

于 2012-12-26T22:58:34.987 に答える