スタック、キュー、リスト、2分木の使い道は？

質問

主な定番データ構造として

(1)スタック
(2)キュー
(3)リスト
(4)2分木

これらのデータ構造がありますが、特に「スタック」と「キュー」は一体何に使えるのでしょうか？
「スタック」や「キュー」は使い道が思いつかないのですが、一体何に使えるのですか？

データ構造である「スタック」「キュー」「リスト」「2分木」の使い道を教えてください。

よろしくお願いいたします。

回答No.1

ubku

スタックは戻り先を覚えておくのに向いています。
return で元の処理に戻れるのは、ジャンプ（CALL）の時に自動的に戻り先をスタックに積んであったからです。ジャンプ先でさらにジャンプした場合でもスタックなら一番上からひとつずづ取り出すだけで、キレイに元の処理に戻れます。
また、プログラム処理中にもCPUには絶えず割り込みが入ります。キーが入力されたとか、マウスが動いたとか、ユーザーが気付かないバックグラウンドの処理とか、OSが処理する割り込みは膨大です。それらは全て、戻り先をスタックに積んでから行い、割り込み処理が終わったら、スタックから取り出した戻り先に戻る、ということが自動的に行われています。

キューは順番待ちの処理に向いています。プリンターの印刷待ちがわかりやすい例です。簡単ですね。

リストはデータの途中への追加・削除が高速に出来るので、HDDのデータ保存に使われています。

二分木は検索が高速に出来るので、大規模なデータの検索を行うような場面で使われます。