ブログ

Nov 14, 2023

FIFO と LIFO: 4 つの違い

FIFO e LIFO sono due tipi di strutture dati comunemente utilizzate nella programmazione.

FIFO と LIFO は、プログラミングで一般的に使用される 2 種類のデータ構造です。

プログラミングにおける LIFO と FIFO の比較

出典: LinkedIn新しいウィンドウを開く

LIFO は「後入れ先出し」の略で、スタック データ構造を使用します。 LIFO データ構造では、スタックに追加された最新の要素が最初に処理されます。 一方、FIFO は「先入れ先出し」の略で、キュー データ構造を使用します。 FIFO データ構造では、キューに追加された最初の要素が最初に処理されます。

先入れ先出しデータ構造は、コンピューティング システム内のデータ要素を管理および操作する方法としてプログラミングで一般的に使用されます。 名前が示すように、FIFO は「先入れ」プロセスに優先順位を付けます。つまり、他の要素よりも先にシステムに入力された要素に最初に対処します。

FIFO はキュー タイプのデータ構造を利用しており、最も古い要素が先頭に留まり、優先処理を待ちます。 FIFO は、プログラミング要素の「先着順」と考えてください。たとえば、スーパーマーケットのレジの列で、最初に並んだ人から先にサービスが提供されるようなものです。

FIFO で使用されるキュー タイプのデータ構造は、シンプルで直感的なデータ処理方法であり、多くのアプリケーションで使用されています。 これは、これらのリクエストを受信した順序で処理でき、ワークフローの中断を回避できるため、大量のリクエストの処理が必要なユースケースに適しています。 最も古いリクエストが最初に処理されるため、FIFO はデータ処理の「公平な」方法であると言われています。

FIFO では、「enqueue」操作を使用して要素がキューの最後に追加され、「dequeue」操作を使用して最初の要素が処理のために削除されます。 FIFO でのエンキューとデキューは、一方の端でアイテムが追加され、反対側の端からアイテムが取り出されるコンベア ベルトとして視覚化できます。

FIFO を使用する大きな利点は、そのシンプルさです。 これは、多くのプログラミング言語で使用される、単純で理解しやすいデータ構造です。 FIFO のもう 1 つの利点は、データ項目を厳密な順序で処理する必要があるアプリケーションに適していることです。 たとえば、プリンタ キューでは、受信した順序で印刷要求を処理したいとします。 FIFO により、最も古い印刷要求が最初に処理されるようになります。

続きを見る：根本原因分析とは何ですか? 作業、テンプレート、および例

後入れ先出しのデータ処理方法もプログラミングでよく使用されます。 この方法では、システムは最新の、つまり「最も若い」エントリを最初に処理します。 LIFO は、最新のデータ入力が最も重要である場合によく使用されます。元に戻す/やり直しの操作やインターネットの履歴リストを考えてください。

LIFO の基本原理は、最後に保存された要素が最初に処理されるということです。 新しい要素は古い要素の上に配置され、「最も新しい」要素が処理のために上から削除されます。 データの入口と出口が同じであるため、最初に操作が行われた最も古い要素がスタックの一番下に留まり、最後に処理されます。

LIFO スタックは、最後に一番上に追加されたプレートも最初に一番上から選択される、プレートのスタックと考えてください。 これは、キューに入る最初の要素が最初に処理される、FIFO で使用されるキュー タイプのデータ構造とは大きく対照的です。 LIFO 要素は、プッシュ操作を使用してスタックの最後に追加されます。 最新の要素はポップ操作で処理されます。

LIFO は、データの処理順序に重点を置かず、データの最新性をより重視するアプリケーションに適しています。 たとえば、Web ブラウザを使用すると、ユーザーは「戻る」ボタンと「進む」ボタンを使用して、アクセスした Web ページ間を行き来できます。 この機能は、LIFO データ構造を使用して、訪問した Web ページの履歴を保存します。 「戻る」ボタンがタップされると、ブラウザは最後にアクセスした Web ページをデータ スタックの最上部から取得し、ユーザーをそのページにリダイレクトします。

続きを見る： ETL (抽出、変換、ロード) とは何ですか? 意味、プロセス、ツール

FIFO メソッドと LIFO メソッドの主な違いをさらに詳しく理解しましょう。

このデータ構造は FIFO 原理に従っています。つまり、新しいエンティティがキューの最後尾に追加され、キューの先頭にあるエンティティが最初に処理されます。

映画館のチケット売り場やスーパーマーケットのレジカウンターに並ぶ人々の通常の列と同様、キュータイプのデータ構造には 2 つの端があります。 一方の端はフロントであり、エンティティが処理のために削除されます。 もう一方の端は背面であり、新しいエンティティが追加されます。

新しいエンティティをキューの最後尾に追加する必要がある場合、「エンキュー」プロセスが実行されます。 一方、処理のためにエンティティをキューの先頭から削除する必要がある場合、「デキュー」プロセスが実行されます。

キュータイプのデータ構造で実行されるもう 1 つの操作は「ピーク」として知られており、キューの先頭にあるエンティティが削除されずに表示されます。

このデータ構造は、データを保存および処理するために多くのコンピューティング システムで使用されます。 たとえば、ネットワーク スイッチ、ブリッジ、ルーターは、宛先に転送されるデータ パケットを保持するために FIFO を使用します。

キューの実装は、配列やリンク リストなどのさまざまなデータ構造を使用して行われます。 キューには理論上の容量制限はありません。 ただし、実際には、「制限付きキュー」の容量は固定である可能性があります。

FIFO キューの効率的な実装が多数存在します。 エンティティの追加と削除の処理を一定時間 (O(1)) で実行できます。 一部のプログラミング言語は、組み込みのキュー サポートを提供します。 たとえば、Java ライブラリの「queue」インターフェイスや、C++ 標準テンプレート ライブラリの「queue」テンプレート クラスです。

前者の操作ではコレクションに要素が追加されますが、後者の操作では、最後に追加されたまだ削除されていない要素が削除されます。 スタック内では要素の LIFO 順序に従います。

実際の物理的なアイテムの積み重ね (皿の積み重ねなど) と同様に、一番上のデータ要素は、スタックの奥にあるデータ要素よりも前に削除する必要があります。

キュータイプのデータ構造と同様に、スタックも線形です。 より抽象的には、プッシュ操作とポップ操作が構造の一端、つまりスタックの「最上部」でのみ発生する順次コレクションとみなすことができます。

このデータ構造により、単一リンクされたリストおよび最上位要素へのポインターとしてスタックを実装できます。

いくつかの実装では、スタックには単純な「プッシュ」や「ポップ」よりも多くの操作があります。 たとえば、キュ​​ーの「ピーク」操作と同様の「スタックの最上位」操作を使用すると、スタックから削除せずに最上位の要素を観察できます。

空のスタックが見つかった場合、「スタックのトップ」または「ポップ」操作の実行時にアンダーフロー状態が発生します。 さらに、スタックが空かどうかとスタックのサイズをチェックできる実装が存在します。

スタックの実装は、リンク リストまたは配列を通じて実行できます。 スタックはリストの特殊なケースとして見なすことができ、実装ではなくインターフェイスによって識別されます。ユーザーは、他のいくつかのヘルパー操作を使用して、リンクされたリストまたは配列に要素をプッシュまたはポップすることしかできません。

FIFO の主な用途は次のとおりです。ディスク スケジューリング アルゴリズムここで、ディスク コントローラは FIFO を使用してプロセスの実行順序を設定します。

これに加えて、多くのデータ構造ではデータ処理に FIFO が使用されます。 FIFO を使用する主な構造は次のとおりです。列 ; ただし、他のバリアントでも FIFO 技術が使用されます。

FIFO は次のような場合にも使用されます。通信とネットワーキング , データ パケットは、FIFO を利用して必要な順序でルーター間に留まります。 この技術を使用すると、ルーターはパケットを転送する必要がある順序を指定できます。

最後に、FIFO が使用されるのは、オペレーティングシステムのアルゴリズム 。 プロセスは、CPU 時間の到着順に選択されます。 たとえば、複数のプロセスが CPU アクセスを待っている場合、オペレーティング システムによって、先に到着したプロセスが優先されます。 これにより、すべてのプロセスが CPU 時間を公平に受け取ることができます。

LIFO はデータ構造でよく使用されます。 のスタックは、LIFO アプローチに従った主要なデータ構造です。 データの保存と管理のためにいくつかのプログラミング言語で使用されます。 スタック データ構造には、式の評価、メモリ管理、関数呼び出しなど、いくつかの用途があります。

LIFO は次のような用途にも使用されています。メモリ管理 。 たとえば、スタック メモリ割り当てアルゴリズムは LIFO を利用します。 ここでは、メモリの割り当てと割り当て解除がスタックのような構造で行われます。 呼び出されると、関数のデータはスタックに格納され、戻ったときに削除されます。

LIFO の一般的な用途は次のとおりです。'歴史'ウェブブラウザの機能。 ユーザーが Web ページにアクセスすると、その URL がキャプチャされ、訪問した他の URL とともにスタックの「最上位」に追加されます。 「戻る」ボタンを押すと、最後にアクセスした Web ページがスタックの一番上から削除され、ユーザーに表示されます。

LIFO の別の例は次のとおりです。操作を元に戻すおよびやり直すコンピューティングにおいて。 たとえば、ワード プロセッサを使用していて、書式設定の変更を元に戻したい場合は、Control (または Command) キーと Z キーを一緒に使用します。 書式設定の以前の状態は、ワード プロセッサ ソフトウェアによって LIFO データ構造を使用して取得され、再適用されます。 同様に、ユーザーがファイルをデバイスのビンに送信したばかりで、削除を元に戻したい場合は、「元に戻す」ボタンをタップするだけで、アプリケーションが削除されたファイルの先頭から最後に削除されたファイルを取得して復元します。データスタック。

最後に、コンピュータ ネットワークは、「後入れ先出しキュー」で LIFO を使用します。 これは、ルーターがシステム間でデータ パケットを送信する必要がある順序を指定するのに役立ちます。 ここで、LIFO は、データ パケットが論理的な順序で目的の受信者に確実に到達するのに役立ちます。

FIFO 方式のもう 1 つの利点は、プロセス全体にわたる公平なアプローチ 。 先着順 (FCFS) の原則に従って、最初に受信したプロセスが最初に実行されます。 これにより、すべてのプロセスの CPU 使用率が平等に確保され、適時終了や誤動作の可能性が最小限に抑えられます。

に関しては年表 , FIFO により、キュー内の最も古い要素が優先処理を受けます。 これは、キューの先頭に最も古い要素を保持し、迅速なアクセスを可能にすることで実現されます。

最も古い要素を検索する必要がなくなるため、取得プロセスより効率的になります。 また、FIFO 方式では「待機」基準が不要になり、データ処理時間が短縮されます。

最後に、FIFO アプローチの特徴固定メモリ消費量 。 これは、実行される操作の数に関係なくメモリ使用率を一定に保つことができるため、注目に値する利点です。 この利点は、FIFO がその要素を管理するために追加のデータ構造を必要としないという事実の副産物です。

LIFO アプローチでは、最後に入力した要素が優先的に処理されます。 これは、次の場合に特に便利です。新しく追加されたアイテムのほとんどは迅速に処理する必要があります残りの操作を完了する必要はありません。

最後に、LIFO は、ユーザーが最新の情報にアクセスする必要があるアプリケーションにとって有益です。年表、株式市場の追跡や財務データ分析など。

さらに、FIFO要素にランダムにアクセスすることはできません 。 これにより、CPU は最初の要素以外のキュー要素にアクセスできなくなり、CPU がキューの途中にある特定の要素にアクセスする必要がある特定のプロセスで非効率が生じる可能性があります。

最後に、FIFO はプロセス実行中の公平性で知られていますが、プロセスの優先順位付けをサポートできない 。 これにより、重要なプロセスが通常のプロセスまたは優先度の低いプロセスが完了するまで待機することになり、システムの効率に影響を与える可能性があります。

LIFO のもう 1 つの欠点は、柔軟性のなさ ; より高度なアルゴリズムを必要とするアプリケーションには効率的な選択ではない可能性があります。

最後に、LIFO はメモリ管理が効率的ではない 。 これは、FIFO (メモリ消費量が固定) とは異なり、LIFO ではメモリ使用量が操作ごとに変化し、消費されるメモリのサイズを固定することができないためです。 LIFO のメモリ消費量は事前に決定されていないため、効率的なリソース割り当てを確保することは困難です。

続きを見る： BDD (行動駆動開発) とは何ですか? 意味、プロセス、例

プログラミングにおける先入れ先出し (FIFO) と後入れ先出し (LIFO) の主な違いは、処理される要素の順序にあります。 FIFO は最初の要素を先出し順に処理し、LIFO は最後の要素を先出し順に処理します。

FIFO は、データ パケット転送など、到着順序が重要で時間的に最も古いデータがより重要なアプリケーションに適しています。 逆に、LIFO は、関数呼び出しや元に戻す/やり直し操作など、到着順序がそれほど重要ではなく、時間的に新しいデータが重要なアプリケーションに適しています。

データ構造に関しては、FIFO はキューとして実装され、LIFO はスタックとして実装されます。 どちらの方法にも長所と短所があり、どちらを選択するかは、最終的には開発中のプログラミング アプリケーションの特定の要件によって決まります。

この記事は、プログラミングにおける FIFO と LIFO の主な違いを理解するのに役立ちましたか? FacebookOpens a new window、TwitterOpens a new window、または LinkedInOpens a new window でご意見を共有してください。

画像出典: Shutterstock

テクニカルライター