data-structures - さまざまなデータ構造の最悪のケース

Question

さまざまなデータ構造での操作を効率化するためのリストの作成に取り組んでいます。これまでのところ、私はこれを持っています：

リンクリストとしてのキューとリンクリストとしてのスタックについて、ここに何があるのか​​よくわかりません。誰かがこの問題に洞察を貸すことができますか？

Answer 1

唯一のエラーは、PopforがでQueue as Linked List with pointer to frontある必要があるということO(1)です。

完全を期すために、任意の要素の検索、任意の要素の削除、インデックスによる取得、インデックスによる削除などの操作の複雑さをリストすることは価値があるかもしれません。

リンクリストとしてキューに入れる（ポインタからフロントへ）：

プッシュ：最後に要素を挿入する必要がありますが、最初へのポインターしかないため、最後に到達するためにすべての要素を反復処理する必要があります。

current = head
while (current.next != null)
  current = current.next
current.next = newItem

ポップ：最初の要素を削除する必要があるため、最初の要素へのポインターを2番目の要素に再割り当てするだけでこれを行うことができます。

removedItem = head
head = head.next

リンクリストとしてキューに入れる（前面と背面へのポインタ）：

プッシュ：最後に要素を挿入する必要があり、最後へのポインターがあるので、一定時間で追加することができます。

tail.next = newItem
tail = newItem

ポップ：単一のリンクリストのポップと同じです。

removedItem = head
head = head.next

リンクリストとしてスタック：

プッシュ：最初にアイテムを挿入します。一定時間で簡単に実行できます。

newItem.next = head
head = newItem

ポップ：最初のアイテムを削除します。一定時間で簡単に実行できます。

removedItem = head
head = head.next

配列としてスタック：

プッシュ：最後のインデックスにアイテムを挿入します。一定時間で簡単に実行できます。

last = last+1
array[last] = newItem

ポップ：最後のインデックスでアイテムを削除します。一定時間で簡単に実行できます。

removedItem = array[last]
last = last-1