スタックとキュー―LIFOとFIFOのデータ構造

トップ情報処理の知識体系テクノロジ系基礎理論アルゴリズムとプログラミングアルゴリズムとデータ構造データ構造の種類 スタックとキュー

スタックはLIFO（Last-In First-Out：後入れ先出し）、キューはFIFO（先入れ先だし：First In First Out）のデータ構造です。スタックとキューの考え方、その操作について解説していきます。

1. スタック

再帰的な処理を実現するためには、再帰的に呼び出したときのレジスタ及びメモリの内容を保存しておく必要あります。これを実現する記憶管理にはスタックが用いられます。

スタックとは、1次元配列に格納された後から入れたデータを先に取り出すデータ構造のことをいいます。このようなデータの出し入れをLIFO（Last-In First-Out：後入れ先出し）と呼びます。

複数のデータが格納されているスタックからのデータの取り出す場合は最後に格納されたデータを最初に取り出します。

キューとは、英語でqueueといい、1次元配列に格納されたデータの一方からデータを格納し、他方の端からデータを取り出すデータ構造のことです。先に入力したデータが先に出力されるFIFO（先入れ先だし：First In First Out）という特徴をもつデータ構造です。

片方向リンクで実現したキューの場合、片方向でしかデータの挿入・取り外しが行えないため、途中への挿入・取り外しを行う場合一旦全てを取り外してから挿入しなければいけません。

一方、双方向リンクの場合、双方向の走査や指定されたノードの前に挿入したり、指定されたノードが削除できるので片方向に比べて途中への挿入・取り外しが容易です。

補足）双方向リンクで実現されるキューは、例えば最初のデータが後で実行したいけど、一番最後に回すのはちょっと問題がある場合に、通常はキューの最後に追加しますが、キューの最初に追加すれば、１回分だけ後回しができるといった使い方が可能になります。

以下ではスタックとキューに関連したIPA情報処理試験の過去問とその解説をまとめています。

もっと知識を広げるための参考です。

アルゴリズムとデータ構造について、基本情報や応用情報など情報処理試験対策用の解説をまとめています。

情報処理試験対策用のサイトオリジナル教科書をテーマにテクノロジ系の知識をまとめています。

スポンサーリンク

情報処理の知識体系

各試験の問題と解説

ランダム出題・採点アプリ

スポンサーリンク