つみかさねと れつ、スタックと キュー

おさらの ように つむ、スタック

まえに データを れつに
ならべる ほうほうを まなびました。
こんかいは ならべる かわりに
うえへ かさねて みましょう。
おさらを つむ ようすを おもいうかべて。
あたらしい おさらは いつも うえに のせ、
とるときも うえから とります。
だから さいごに のせた おさらが
いちばん さきに てに とどきます。

おさらを おして うえに つみ、とりだすを おして。いつも いちばん うえ、さいごに のせた ものから でます。

とりだす たびに
いま のせた ものが さきに でましたね。
あとに いれた ものが さきに でる、
これが スタックの ひとつの やくそくです。
いれる ところも だす ところも
ただ いちばん うえの ひとつだけ なので
きまりが とても かんたんです。
この かんたんさが どこで やくに たつかは
すこし あとで また あいましょう。

れつに ならぶ、キュー

こんかいは つむ かわりに
よこに れつを つくりましょう。
バスを まつ れつを おもいうかべて。
あたらしく きた ひとは いちばん うしろに ならび、
バスが きたら まえから のります。
だから さきに きた ひとが
さきに はいれます。
つみかさねとは せいはんたいですね。
この れつを キューと いいます。

ひとを おして れつの うしろに ならべ、だすを おして。いつも いちばん まえ、さきに きた ひとから でます。

だす たびに
いちばん ながく まった ひとが さきに でましたね。
さきに いれた ものが さきに でる、
これが キューの やくそくです。
うしろから はいり まえから でるので
きた じゅんが そのまま まもられます。
だから わりこみ なしに
こうへいな じゅんばんが ほしょうされます。
つみかさねは あとさき、れつは さきさきです。

スタックは もとに もどすのに つかう

ぶんを かいていて しっぱいしたとき
もとに もどすを おすと
いま やった ことが さきに とりけされます。
その まえに やった ことは つぎに とりけされます。
どうさを じゅんに つみあげて おき、
いちばん うえ、つまり さいごの どうさから
ひとつずつ とりだして とりけすのです。
まさに スタックですね。
もどる ボタンも おなじ しくみです。

どうさを おして つみ、もとに もどすを おして。さいごに した どうさから じゅんに とりけされます。

もとに もどすを おす たびに
いちばん あたらしい どうさから きえましたね。
じゅんばんを ぎゃくに まきもどすときは
スタックほど よく あう ものは ありません。
さいごに いれた ものを さきに だすという
その やくそくが まきもどしだからです。
では じゅんばんを ぎゃくでなく
はいった とおりに まもるときは
なにを つかえば いい?

キューは まちぎょうれつに つかう

なんにんもが ひとつの プリンタに
いんさつを たのむと どうなる?
さきに おくった ぶんしょが さきに いんさつされ
あとの ものは うしろで まちます。
これが いんさつ まちぎょうれつです。
ぎんこうの ばんごうふだも おなじ。
さきに ひいた ばんごうが さきに よばれます。
きた じゅんに こうへいに。
まさに キューが する しごとです。

ぶんしょを おして まちぎょうれつに いれ、いんさつを おして。さきに たのんだ ものから じゅんに しょりされます。

いんさつを おす たびに
いちばん さきに たのんだ ぶんしょが でましたね。
じゅんばんを そのまま まもるときは
キューに かなう ものは ありません。
さきに いれた ものを さきに だすという
その やくそくが こうへいさだからです。
おなじ データでも だす きまり ひとつで
つかいみちが こんなに かわります。
では ふたつを ならべて まとめましょう。

まとめて みましょう

ひとことに まとめると こうです。
スタックは おさらの つみかさね、あとに いれた ものが さきに でます。
キューは れつ、さきに いれた ものが さきに でます。
もとに もどすと もどるは スタック、
まちぎょうれつと ばんごうふだは キューです。
いれて だす きまり ひとつが
つかいみちを きめるのです。
つみかさねは あとさき、れつは さきさき、
この いちぎょうだけ おさえれば いい。

かなめを じゅんに おして ふりかえって。(スタック = つみかさね → キュー = れつ → スタックは もとに もどす → キューは まちぎょうれつ)

これで データを つみ れつに する
ふたつの ほうほうを しりました。
いれる ところと だす ところを きめるだけで
まったく ちがう どうぐに なりました。
つぎは れつでも つみかさねでもない
また べつの ほうほうに あいます。
データが えだの ように わかれ
うえから したへ のびる かたち、
その はなしを つぎの かいで つづけましょう。