addbegin、addend、およびrandom accessの一定時間をサポートするデータ構造

Question

開始、終了、およびランダムアクセスに要素を追加するための一定時間のパフォーマンスをサポートするデータ構造を探しています。

私はダブルエンドキューを考えています。ダブルエンドキューはランダムアクセスの一定時間パフォーマンスをサポートしていますか？もしそうなら、それはどのように達成されますか？

ダブルリンクされたリストを使用してダブルエンドキューを構築することができます。しかし、一定の時間ランダムアクセスを達成するために、どのようにすべての要素のインデックスを作成しますか？

ありがとうございました。

ジェリー

Answer 1

あなたが探していることは、定義によって両端キューだろうが、それは単に抽象的なデータ構造です。ウィキペディアは、動的配列に関してseveral implementation strategies for dequesについて議論しています。これらを使用すると、償却されたO（1）を前置して追加することができます。一見すると、循環バッファ戦略は最も簡単に実装できるように見えます。