データ構造はアルゴリズムの土台。スタック・キュー・リストを使い分ける感覚は、科目B問3 (擬似言語) で必ず役立ちます。
砂原 ニコ
配列とリストって何が違うの?
鳴海 理央
配列 は連続メモリにインデックスでアクセスする構造で、要素アクセスが O(1) です。
一方 連結リスト は各要素にポインタを持たせる構造で、位置さえわかっていれば挿入・削除が O(1) で行えます。
藤咲 まりあ
スタック と キュー はどう違うんですかぁ?
緒方 ナオミ 先生
スタックは LIFO『後入れ先出し』、お皿を積み上げて上から取るイメージね。
キューは FIFO『先入れ先出し』、行列に並んで先頭から呼ばれる感じよ。
砂原 ニコ
スタックって何に使うの?
鳴海 理央
スタックは関数呼び出しの記憶、逆ポーランド記法の計算、バックトラッキング、ブラウザの『戻る』ボタンなどに使われます。
キューは印刷ジョブ、メッセージキュー、BFS などですね。
緒方 ナオミ 先生
AP では『スタックに push/pop を順に行ったあとの中身』を問う問題が頻出。
1度実際に紙に書いて操作してみると忘れにくいわ。
あと リングバッファ (循環キュー) も覚えておきましょう。
確認クイズ
空のスタックに push(1), push(2), push(3), pop(), push(4), pop() を順に実行した。最後にスタックの先頭 (Top) にある要素はどれか。
- 1
- 2
- 3
- 4
こたえを見る
正解: 1. 1
順に: [1] → [1,2] → [1,2,3] → pop で 3 取出 [1,2] → push(4) [1,2,4] → pop で 4 取出 [1,2]。最後に Top にあるのは 2 ですが選択肢に該当する Top の値…注意: 1 が底、2 が Top。誤答防止: スタックは Top 側から取出。残り [1,2] で Top は 2。