━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
データ構造・アルゴリズム論 確認問題４
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

●問 (スタックとキューの基本操作)

(1) 空のスタックに対して，次の基本操作を順に実行する．
    0をプッシュ，3をプッシュ，ポップ，6をプッシュ．
    スタックを (最上段が最右の) 列で表し，
    その変化を ([1,2,3] → [1,3] の形式で) 示せ．

(2) 空のキューに対して，次の基本操作を順に実行する．
    0を追加，3を追加，削除，6を追加．
    キューを (先頭が最左の) 列で表し，その変化を示せ．

──────────────────────────────────────

●答 (スタックとキューの基本操作)

(1) [] → [０] → [０,３] → [０] → [０,６]

(2) [] → [０] → [０,３] → [３] → [３,６]

[解説]

(1) スタックでは，要素の 追加・削除 の位置が最上段に固定されている．
この問題では，スタックの最上段を列の末尾（最右要素）として表すので，
プッシュでは列の末尾に要素を追加し，ポップでは列の末尾から要素を取り出す．

(2) キューでは，列の末尾に要素を追加し，列の先頭から要素を取り出す．

どちらも「0の追加，3の追加，削除，6の追加」という基本操作の系列を実行している．
データ構造が違えば，同じ操作系列を実行しても結果が異なる，という点に注意する．

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
授業のホームページ

山田 俊行
https://www.cs.info.mie-u.ac.jp/~toshi/