Ricewoods Lab

EXPERIMENT 09 / 図解と操作

途中で取り出すと「逆順」では説明できない。スタックとキューを7手で比較

スタックは逆順、キューは入れた順。全部入れてから取り出す例では分かりやすい覚え方ですが、追加と取り出しが混ざると、残っているデータを毎回追う必要があります。7手の操作を同じ条件で比べました。

検証条件

2026年11月16日。後入れ先出し・先入れ先出しの定義に従って7手を独立計算し、状態表を作成。うごく図解の操作演習で同じ手順を再現できます。

同じ7手を、両方へ実行する

操作ごとの出力と残り・左から底または先頭
手操作スタックから出る値スタックの残りキューから出る値キューの残り
1Aを入れる—A—A
2Bを入れる—A・B—A・B
3取り出すBAAB
4Cを入れる—A・C—B・C
5取り出すCABC
6Dを入れる—A・D—C・D
7取り出すDACD

スタックでは、取り出すたびに一番新しく残っているデータを選びます。キューでは、一番早く入ってまだ残っているデータを選びます。「新しい」「早い」は全履歴のことではなく、その時点で残っている中で比べます。

全部入れてから取り出す例と、何が違うか

A・B・Cを全部入れてから取り出せば、スタックはC→B→Aです。しかし今回の例では、Cを入れる前にBを取り出しています。途中で消えたBを、後からもう一度取り出すことはありません。

「スタックは入力列の逆順」という覚え方だけで全体のA・B・C・Dを逆転すると、D→C→B→Aと考えてしまいます。これは今回の実行順と違います。追加と取り出しを一つずつ状態に反映させることが大切です。

操作演習で確かめる

  1. うごく図解のスタック・キュー比較を開き、「空にして最初から」で始めます。
  2. Aを入れる、Bを入れる、取り出す、Cを入れる、取り出す、Dを入れる、取り出す、の順に操作します。
  3. 出た順と残りを上の表と照合します。「1手戻す」で最後の取り出しを戻し、A・DとC・Dの状態も確認できます。

文字を入れる前に、次の操作で何が出るか予想してみてください。結果だけを眺めるより、予想が外れた手でどのデータを見落としたか分かります。

一手増やすとどうなる?

この後さらに1回取り出すと、スタックはA、キューはDを返し、両方とも空になります。その次には、取り出せるデータがありません。空の状態をどう扱うかは実装により、エラーや特別な値などが使われます。

今回は単純なスタックとキューの順序だけを扱います。優先度付きキュー、複数処理の同時実行、容量制限などは別の条件です。学習画面にある操作回数・個数の上限は、定義そのものの上限ではありません。

サンプルと確認資料

資料は検証用のサンプルや計算記録です。入力条件と結果を見比べて確認できます。掲載の結果は各記事に記した条件での観察・計算です。

参考資料と、数値の記録

数値と比較結果のJSONも公開しています。公開日と元の操作記録日が異なる場合は、検証条件に区別して記載しています。