アレイベースのリストベースのスタックとキュー

Question

対両方の配列として、リンクリストとして実装されたときに、私は、スタックとキューの操作のために（両方の実行時間と空間を）成長率を比較しようとしています。これまでのところ、私はキューpop()の平均実行時間を見つけることしかできませんでしたが、これら2つのデータ構造を包括的に調査し、実行時間/空間動作を比較するものは何もありません。

具体的に、私は両方配列とリンクされたリスト（従って2操作×2つの構造×2つの実装、又は8つの値）として実装キューとスタックの両方についてpush()とpop()を、比較していますよ。

また、私はこれらの両方のために最高の平均と最悪の場合の値をいただければと思いますし、何が彼らが消費するスペースの量に関係します。

私が見つけた最も近いことは、明らかに高度なアルゴリズムと離散関数のマスターレベルまたは博士レベルのチートシートである「すべてのcsチートシート」のpdfです。

私は、配列ベースの実装と、スタックとキューの両方のリストベースの実装をいつ、どこで使うべきかを判断する方法を探しています。私はあなたの質問を誤解し、私はしなかった場合、私は信じているよりも、これはあなたが探している答えがある場合

Answer 1

は、リンクされたリストと配列とキューとスタックを実装するための複数の異なる方法があります、と私はあなたが探しているどれかわかりません。これらの構造を分析する前に、上記のデータ構造に関する重要なランタイムの考慮事項を見てみましょう。

ヘッドポインタだけの単一リンクリストでは、値を前に追加するコストはO（1）です。新しい要素を作成し、そのポインタをリストの古いヘッドを指すように配線してから、更新しますヘッドポインタ。最初の要素を削除するコストもO（1）です。これは、現在のヘッドの後ろの要素を指すようにヘッドポインタを更新してから（古いメモリ管理が実行されている場合）古いヘッドのメモリを解放します。しかしながら、これらのO（1）項の定数因子は、動的割当の費用のために高くなる可能性がある。リンクされたリストのメモリオーバーヘッドは、各要素に余分なポインタを格納するため、通常はO（n）の余分なメモリです。

ダイナミックアレイでは、O（1）時間内の任意の要素にアクセスできます。 amortized O(1)に要素を追加することもできます。つまり、n個の挿入時間の合計がO（n）であることを意味しますが、実際の挿入時間は非常に悪い可能性があります。一般的に、動的配列は、あらかじめ割り当てられたスペースに追加することで大部分の挿入がO（1）になるように実装されていますが、配列の容量を2倍にして要素をコピーすることにより、小さな数の挿入をΘ（n）余分なスペースを割り当て、要素を遅延コピーすることで、これを減らそうとするテクニックがあります（例えば、this data structure参照）。通常、ダイナミックアレイのメモリ使用量はかなり良いです。たとえば、アレイが完全にいっぱいになると、O（1）余分なオーバーヘッドしかありません。アレイのサイズが2倍になった直後にO（n）配列に割り当てられた要素。割り当ては頻繁ではなく、アクセスは高速であるため、動的配列は通常、リンクされたリストより高速です。

ここで、リンクリストまたは動的配列を使用してスタックとキューを実装する方法について考えてみましょう。そこにこれを行うには多くの方法があるので、私はあなたが以下の実装を使用していることを前提としています：

• スタック：
  • リンクリスト：先頭ポインタとsingly-linked listとして。
  • 配列：dynamic array
• キューとして：
  • リンクされたリスト：頭部および尾ポインタで単独リンクリストとして。
  • アレイ：配列に裏打ちされたcircular buffer。

それぞれを順番に考えてみましょう。

スタックは単一リンクリストに基づいています。単一リンクリストはO（1）時間の前置と最初の削除をサポートするため、リンクリストバックアップスタックにプッシュまたはポップするコストはO（1）最悪ケースです。ただし、追加される新しい要素ごとに新しい割り当てが必要であり、割り当ては他の操作に比べて高価になる可能性があります。

スタックはダイナミックアレイに裏打ちされています。スタックへのプッシュは、償却されたO（1）時間と最悪の場合のO（n）時間を取る新しい要素を動的配列に追加することで実装できます。スタックからのポップアップは、最悪の場合に実行される最後の要素（1）（または未使用領域を再利用しようとする場合は償却されたO（1））を削除するだけで実装できます。言い換えれば、最も一般的な実装では、最良のケースO（1）プッシュアンドポップ、最悪ケースO（n）プッシュとO（1）ポップ、および償却O（1）プッシュとO（1）ポップがあります。

キューは単一リンクリストによってバックアップされています。リンクされたリストへのエンキューは、最悪の場合の時間O（1）をとる単一リンクリストの後ろに追加することで実装できます。デキューは、最悪の場合の時間O（1）をとる最初の要素を削除することで実装できます。これにはエンキュー毎に新しい割り当てが必要ですが、遅くなる可能性があります。

キューは、増加する循環バッファによってバックアップされます。循環バッファへのエンキューは、循環バッファ内の次の空き位置に何かを挿入することによって機能します。これは、必要に応じて配列を拡張し、新しい要素を挿入することによって機能します。ダイナミックアレイに対して同様の解析を使用すると、これは最良ケース時間O（1）、最悪ケース時間O（n）、および償却時間O（1）をとる。バッファからのデキューは、最悪の場合に時間O（1）を要する循環バッファの最初の要素を削除することによって機能します。要約すれば、すべての構造は、O（n）時間にn個の要素をプッシュしてポップすることをサポートする。別ウィンドウ（タブ）の大きな表示で見るリンクされたリストのバージョンは、より良いワーストケースの動作をしますが、実行された割り当ての数のために全体的なランタイムが悪化する可能性があります。アレイのバージョンは最悪の場合は遅くなりますが、1回の操作時間があまり重要でない場合は、全体的なパフォーマンスが向上します。

スタックを実装するための別の方法として、VListがあります。最近のデータ構造はリンクリストと動的配列のハイブリッドです。それはリンクリストよりも割り当てが少なくなり、ポインターが少なくなりますが、最悪の場合にはスペース使用量が少し高くなります。スタックとキューの両方に使用できる配列とリンクされたリストの別のハイブリッドであるチャンクリストを調べることもできます。

希望すると便利です。

Answer 2

申し訳ありません。ベクターで

、あなただけ効率的にコンテナの最後に要素を追加/削除することができます。 両端キューを使用すると、コンテナの最初/最後に要素を効率的に追加/削除できます。 リストを使用すると、コンテナ内の任意の場所に要素を効率的に挿入/削除できます。

vector/dequeはランダムアクセスイテレータを許可します。 リストは順次アクセスのみを許可します。あなたがデータを使用して保存する必要がどのように

は、あなたが最も適切であるかを決定する方法です。

EDIT：

これまで多くのがあり、私の答えは非常に一般化されます。私はあなたの質問が何であるかを追跡していても、もっと深く掘り下げることができます。