FEアルゴリズムとプログラミング · データ構造

LIFO

Last In First Out

らすといんふぁーすとあうと

後から入れたデータを先に取り出す方式。「後入れ先出し」と訳す。スタックの動作原理であり、サブルーチンの戻り先の記憶や、逆ポーランド表記法の計算などに使われる。

共有:

Past Exams

過去問での出題

過去問で 9 回出題（応用情報技術者試験 5・高度試験午前Ⅰ 3・基本情報技術者試験 1）

出典: 独立行政法人情報処理推進機構（IPA）の過去問題。問題文は IPA のサイトの PDF で確認できます。「選択肢」は、問題文ではなく選択肢に出たものです。用語名で照合しているため、関係の薄い問題が含まれることがあります。

スタックにデータを積む操作。スタックポインタを進めて、その位置に新しいデータを書き込む。取り出す操作はポップで、プッシュした逆順にデータが出てくる。

スタックから最後に積んだデータを取り出す操作。取り出すと同時にスタックポインタを戻す。空のスタックに対して行うとアンダーフローとなるため、事前に空でないことを確かめる必要がある。

同じ型のデータを連続したメモリ領域に格納するデータ構造。添字（インデックス）を用いて各要素に直接アクセスできるため、参照がO(1)で高速。挿入・削除はデータの移動が必要なためO(n)。

各要素がデータとポインタ（次の要素への参照）を持ち、鎖状に連結されたデータ構造。要素の挿入・削除がポインタの変更のみで可能だが、特定要素の参照には先頭から辿る必要がある。

各要素が前方と後方の両方へのポインタを持つリスト構造。前後どちらの方向にも辿れるため、要素の削除が単方向リストより効率的。ただしポインタが2つ必要なためメモリ使用量が増える。

データの挿入と取り出しが同じ端（先頭）から行われるデータ構造。LIFO（Last In, First Out：後入れ先出し）の原則に従う。関数の呼び出し管理、括弧の対応チェック、逆ポーランド記法の計算に使用される。