クイズ: データ構造とアルゴリズム

スタックはLIFOアクセスパターンに最適です。キューはFIFO（First In, First Out）アクセスパターンに最適です。

O(1) は定数時間計算量を表します。入力サイズに関係なく、アルゴリズムは常に同じ時間で実行されます。

単方向連結リストの長さを計算するには、ヘッドからテイルまで全てのノードを走査する必要があり、時間計算量は O(n) になります。

バランスの取れたBSTでは、各レベルで探索空間が半分になるため、検索の平均時間計算量は O(log n) です。

マージソートは常に最悪ケースで O(n log n) の計算量で動作します。配列を半分に分割し、ソート済みの部分配列をマージすることを繰り返すためです。

BFS はキューを使用してノードをレベルごとに探索し、幅優先（「行」単位）でノードを処理します。

深さ優先探索（DFS）は、訪問したノードを追跡するために再帰スタックを保持することで、グラフ内のサイクルを検出する際に一般的に使用されます。

ヒープソートはヒープを構築し、最大要素を繰り返し取り出すことで、最悪ケースでも O(n log n) の時間計算量を保ちます。

ハッシュテーブルは、衝突を最小限に抑える優れたハッシュ関数を前提とすれば、要素へのアクセスの平均時間計算量は O(1) です。

スタックの主要な操作は Push（要素を追加）、Pop（要素を削除）、そして Peek（要素を削除せずにトップを参照）です。

ダイクストラ法は、非負のエッジ重みを持つグラフで最短経路を求める際に頻繁に使用されます。優先度キューを利用して、最短距離を効率的に算出します。

AVL木 と 赤黒木 は自己平衡木の一種で、挿入や削除のたびに木がバランスを保つようにします。

再帰関数では、特定の条件が満たされたときに再帰呼び出しを停止させ、無限再帰を防ぐために基本ケースが必要です。

キューの主要な2つの操作はエンキュー（要素を末尾に追加する）とデキュー（要素を先頭から削除する）です。

グラフが有向非循環（DAG）である場合にトポロジカルソートを実行できます。この順序付けはタスクスケジューリング問題で役立ちます。

フィボナッチ数列の単純な再帰実装は、各フィボナッチ数に対して膨大な繰り返し計算が行われるため、時間計算量は O(2^n) です。

優先度キューは、最高または最低の優先度の要素を効率的に取り出せるため、通常ヒープを使って実装されます。

中順、前順、後順は二分木における代表的な深さ優先走査の3つの順序で、ノードの訪問順序がそれぞれ異なります。幅優先走査も一般的ですが、別の走査カテゴリです。

最小ヒープでは、根は常に最小要素であり、木の高さは O(log n) になるため、挿入と抽出が効率的です。

この比較条件では等しいキーを持つ要素同士を追い越して交換しないため、バブルソートは安定です。等しいキーも交換する実装では、その性質が失われることがあります。