この記事での学習内容 基本情報 応用情報

スタックとキューの考え方、その操作を理解する。

用語例：FIFO、LIFO、プッシュ、ポップ

スタック（LIFO）

スタックは、最後に入れたものを最初に取り出すデータ構造で、LIFO（Last In, First Out：後入れ先出し）ともいいます。

スタックにデータを追加する動作をプッシュ（push）、データを取り出す動作を（pop）といいます。

スタック構造は、逆ポーランド記法の計算やプログラムにおける提携処理の呼び出しと戻りなどに応用されています。

逆ポーランド記法の説明で「コンピュータと相性が良い」と述べていますが、その特徴とスタックというデータ構造は密接に関連しています。

逆ポーランド記法で記述された式を処理する場合、以下のルールでスタックを使った処理を行っています。

• 数値が来たら、その数値をスタックにPUSHする。
• 演算子が来たら・・・
  • スタックからデータをPOPする。（データ1）
  • スタックからデータをPOPする。（データ2）
  • データ1とデータ2を演算し、その結果をスタックにPUSHする。

この処理を行うと、最終的にスタックの一番上に一連の式の結果が保存されています。

キュー（FIFO）

キュートは、最初に入れたデータを最初に取り出すデータ構造で、FIFO（First In, First Out：先入れ先出し）ともいいます。

キューにデータを追加する動作をエンキュー（ENQ）、データを取り出す動作をデキュー（DEQ）といいます。

キューは通信において、タイミング調整に使われることがあります。代表的な例として、送信バッファや受信バッファがあります。バッファとは、一時的にデータを入れる場所のことです。

例えば、コンピュータでのデータ受信の際に、インターネット等伝送路からのデータ量が一定していない場合、そのまま受信してしまうとデータ受信ペースの遅れや、瞬間的に大量のデータを受信した場合などで不都合が生じます。このような場合に受信バッファが用いられ、受信したデータを一時的に格納しておき、できるだけコンピュータが受信するデータ量を一定にするようにします。

スタックやキューをプログラムで実現する場合の違い

スタックやキューをプログラムで実装する場合、データ量や用途に応じて配列構造とリスト構造を使い分けます。

	配列で実現	リストで実現
キュー	先頭を指すポインタと最後尾を指すポインタが必要 処理が単純で速い	単方向リストで可能 データあふれの心配がない
スタック	最新のデータを示すポインタが必要 処理が単純で速い	単方向リストで可能 データあふれの心配がない