スタックとキューの試験問題への適用
スタックとキューの問題では、操作名だけでなく現在の格納順を一手ずつ更新する。スタックはLIFO、キューはFIFOで、途中に追加と取出しが混ざっても原則は変わらない。
この単元で学ぶこと
- スタックトレースの意味と役割を説明できる
- キュートレースの意味と役割を説明できる
- 混合操作の意味と役割を説明できる
- 複数のpush/pop/enqueue/dequeue操作から途中状態と取出し順を正確に求められる
本文解説
push/pop、enqueue/dequeueのたびに構造の中身を書き換える。スタックはtop、キューはfront/rearを明記すると、複数操作でも取り違えにくい。
スタックトレース push/popごとにtop側を更新して状態を記録する。 最後に積んだ要素から取り出す。
キュートレース enqueue/dequeueごとにfrontとrearを更新する。 最初に入れた要素から取り出す。
混合操作 追加と取出しが交互に現れる操作列。 各操作直後の状態を残す。
空構造判定 要素数0で取り出し操作を行わないよう確認する。 underflow相当の扱いは設問定義に従う。
利用場面 LIFO/FIFOの性質から適用先を判断する。 再帰・逆ポーランド式はスタック、待ち行列や幅優先探索はキューが典型。
操作ごとに構造を書き直し、取り出した値と残った値を別々に記録する。
空スタックに1,2をpushしpop、3をpushすると残りは[1,3]でtopは3。空キューなら同操作相当で先頭が2になる。
図解
重要ポイント
- スタックトレース: push/popごとにtop側を更新して状態を記録する。
- キュートレース: enqueue/dequeueごとにfrontとrearを更新する。
- 混合操作: 追加と取出しが交互に現れる操作列。
- 空構造判定: 要素数0で取り出し操作を行わないよう確認する。
- LIFO/FIFOを暗記するだけでなく、操作列を状態遷移として追う。
間違えやすい点
- pop/dequeueした要素を構造内に残さない。
- 追加位置をスタックとキューで混同しない。
- 空構造からの取出し条件を無視しない。
用語解説
- スタックトレース
- push/popごとにtop側を更新して状態を記録する。
- キュートレース
- enqueue/dequeueごとにfrontとrearを更新する。
- 混合操作
- 追加と取出しが交互に現れる操作列。
- 空構造判定
- 要素数0で取り出し操作を行わないよう確認する。
- 利用場面
- LIFO/FIFOの性質から適用先を判断する。
関連教材
参考資料
教材データに登録された参考リンクです。リンク先の内容や更新日は提供元でご確認ください。
確認問題の出題・採点や学習履歴の保存にはログインが必要です。