スタックを使用するメリットと二重リンクリストを比較する

Question

割り当てとして、再帰的にではなくクイックソートを繰り返し実装する必要があります。これを行うには、スタックを使用する必要があります。このシナリオでスタックを使用するメリットは、単独または二重にリンクされたリストだけです。

Answer 1

プッシュはスタックにO（1）時間の複雑さがあり、挿入にはO（N）がある場合があります（ヘッドに追加すると最適なケースが発生します、O（1） linkedList内の（N）を返します。追加操作と検索操作の両方を実行する必要があるため、LinkedListを使用するとより多くの費用がかかります

Answer 2

簡単な答えは表現力です。コメントで指摘したように、リンクされたリストを使ってスタックを実装できます。 "スタックの使用"に関する素晴らしい点は、実装の詳細を心配する必要がないことです。それは、あなただけのリンクリストを使用した場合、あなたはのようなものがあるだろうさ：既存のStackデータ構造を使用している場合

// push onto the stack 
newNode = createStackNode(myData); 
newNode.Next = root; 
root = newNode; 

// pop from stack 
poppedNode = root; 
root = root.Next; 
myData = poppedNode.data; 

を、あなたはプッシュとポップの詳細を心配する必要はありません。あなたが書かなければならないすべては、次のとおりです。

theStack.push(myData); 

または

myData = theStack.pop(); 

ポイントは、あなたがStackデータ構造の作品を知っているということで。 pushまたはpopへの電話をかけるのは本当に難しいです。それは非常に簡単です物事を追加し、リンクされたリストの頭から物事を削除するコードを台無しにする。

Answer 3

スタックは、定義する必要がある一連の操作を定義するインターフェイスであり、リンクされたリスト、ダブルリンクされたリスト、配列など、さまざまな方法で実装できます（必要に応じて、私はそう示唆していない場合でも）。この一連の操作の定義は、データ構造の範囲を制限し、特定のユースケースに対してより良いパフォーマンスを得ることを可能にします。

一般に、リンクリストまたは配列から要素を削除するには、削除する要素が任意の位置にある可能性があるため、O(n)を取得する必要があります。同じデータ構造を持つpopを実装するスタックでは、削除する要素がどこにあるかを既に知っているので（の場合はリンク先リストの場合は先頭、配列の場合は最後の要素）、これを実現できます。