スタックとキューを理解する
スタックとキューは要素を取り出す順序が異なる基本データ構造である。スタックはLIFO、キューはFIFOとして操作列を追えることが重要。
この単元で学ぶこと
- スタックの意味と役割を説明できる
- pushの意味と役割を説明できる
- popの意味と役割を説明できる
- push/pop/enqueue/dequeueの操作列から要素の並びと取出し順を求められる
本文解説
スタックではpushで末尾側へ積みpopで最後に積んだ要素を取り出す。キューではenqueueで後端へ追加しdequeueで先頭から取り出す。
スタック 最後に追加した要素を最初に取り出すLIFO構造。 関数呼出しや式評価などに使われる。
push スタックへ要素を追加する操作。 top側へ積む。
pop スタックのtop要素を取り出して削除する操作。 空スタックでは扱いに注意。
キュー 最初に追加した要素を最初に取り出すFIFO構造。 待ち行列や幅優先探索などに使われる。
enqueue/dequeue キュー後端への追加と先頭からの取出し操作。 追加側と取出し側が異なる。
スタックはtop、キューはfront/rearを書き、操作ごとに図を更新する。
スタックへ1,2,3をpushし2回popすると3,2の順。キューへ1,2,3をenqueueし2回dequeueすると1,2の順。
図解
重要ポイント
- スタック: 最後に追加した要素を最初に取り出すLIFO構造。
- push: スタックへ要素を追加する操作。
- pop: スタックのtop要素を取り出して削除する操作。
- キュー: 最初に追加した要素を最初に取り出すFIFO構造。
- LIFOとFIFOを言葉だけでなく操作列で追えるようにする。
間違えやすい点
- スタックのpopを先頭要素取出しと考えない。
- キューのdequeueを最後に追加した要素から行わない。
- 空構造からの取出しを通常操作として扱わない。
用語解説
- スタック
- 最後に追加した要素を最初に取り出すLIFO構造。
- push
- スタックへ要素を追加する操作。
- pop
- スタックのtop要素を取り出して削除する操作。
- キュー
- 最初に追加した要素を最初に取り出すFIFO構造。
- enqueue/dequeue
- キュー後端への追加と先頭からの取出し操作。
関連教材
参考資料
教材データに登録された参考リンクです。リンク先の内容や更新日は提供元でご確認ください。
確認問題の出題・採点や学習履歴の保存にはログインが必要です。