IT資格用語解説基本情報技術者試験・データ構造の種類
スタックとキュー
更新日:
用語解説
スタックは最後に入れた要素を最初に取り出すLIFO、キューは最初に入れた要素を最初に取り出すFIFOのデータ構造です。
■ 試験で押さえるポイント
スタックはPUSHで最上部へ追加し、POPで最上部から取り出し、関数呼出し、式評価、深さ優先探索、元に戻す処理等に使います。
キューはENQUEUEで末尾へ追加し、DEQUEUEで先頭から取り出し、待ち行列、バッファ、幅優先探索等に使います。
循環キューは配列の末尾の次を先頭として再利用し、要素移動なしで有限バッファを効率よく使います。
優先度付きキューは到着順でなく優先度が高い要素を先に取り出すため、通常のFIFOキューとは異なります。
■ 選択肢での判断ポイント
後入れ先出しはスタック、先入れ先出しはキューです。深さ優先はスタック、幅優先はキューを対応付けます。
例: A、B、Cの順に入れると、スタックはC、B、A、キューはA、B、Cの順に取り出します。