スタックと再帰

午前試験免除制度対応!基本情報技術者試験のeラーニング【独習ゼミ】
嶋田さん  
(No.1)
大滝本  応用問題4.7 スタックと再帰の問題を解いているのですが、いつも解くたびにどっちからポップするか分からなくなります。例えば
A{1.2.3}
B{1.2.3}
として
Bの値をAにプッシュする  とあったとき
1から抜くか3から抜くか分からなくなります。後入れ先出しなのはわかっているのですが、、
回答としては3から抜くことになっています。
一番最後にプッシュしたのが1だと思い、実際は3だった、という話です。
どうやって判断したらいいでしょうか。
末尾の3から抜く?それとも「一番右が最後にプッシュされたから3から?
区別する方法を教えてください
2024.10.05 17:29
対象oさん 
(No.2)
LIFOに右からとか左からとかはないです。
もし本にそのように書いてあるならその本が悪いと思います。
普通、AとB両方に1,2,3の順番でpushした、BをpopしてAにpushしたらどうなるか、みたいな問題になります。
2024.10.05 18:01
まーぼさん 
FE シルバーマイスター
(No.3)
スタックは積み上げた本を取り出すイメージです。

例として、配列を使ってスタックを実現した場合をみ挙げます。以下ではpushやpopで内部的に配列が使われていると思ってください。配列のメモリは十分に確保されています。配列の要素番号は1から始めます。()の中は現実でのイメージです。

push(“国語”)
>textbooks[1] ← “国語”
>(机の上に国語の教科書を置いた)

push(“数学”)
>textbooks[2] ← “数学”
>(国語の教科書の上に数学の教科書を置いた)

push(“理科”)
>textbooks[3] ← “理科”
>(数学の教科書の上に理科の教科書を置いた)

push(“社会”)
>textbooks[4] ← “社会”
>(理科の教科書の上に社会の教科書を置いた)

ここまでで以下のようなイメージです。

社会
——
理科
——
数学
——
国語

ここで、本を一冊取り出すとなると、普通は一番上から取り出しますよね?

ということで、
pop()をすると
“社会”が取り出せるイメージです。

ちなみにキュー(FIFO)はお店の行列のイメージです。Aさん、Bさん、Cさんの順に入店してきて、Cさんから先に通されたらクレーム待ったなしですよねw
2024.10.05 18:10
pixさん 
(No.4)
多分スレ主様は、表記のデフォルトがわからなかったのだと思われます。

スタックのPUSH&POPなので、以下のように下から上へデータを積む図が一番正確に
スタックを表現しています。
上:3
  :2
下:1
しかし、テキストにいちいち図を付けていられないので、簡易的な記法があります。
それが以下のように、下から上を右に90度回転し、一行で左から右へスタックを表現します。
{1,2,3}
そのため、この表記法の場合は暗黙的に左が下を意味し、右が上を意味します。
この表記法の場合はPUSH&POPともに一番右のデータ(末尾)に対して行います。
2024.10.05 18:23
pixさん 
(No.5)
一応専門的に補足します。
縦の表記は純粋なスタックです。
横の表記は厳密にはリストになります。
この2つは厳密には別物ですが、どちらもPUSH&POPという操作が存在します。
リストに対しての特定の使用方法がスタックです。
ですが、FEの段階では2つの違いについてはそれほど意識しなくてもよいと思われます。
2024.10.05 18:29
嶋田さん  
(No.6)
みなさんありがとうございます。pixさんの解説が一番わかりやすく助かりました。
2024.10.05 20:04

返信投稿用フォーム

※CBT試験では出題内容の公開が禁止されているため、直接的・間接的を問わず、出題内容や難易度を尋ねる質問は厳禁です。
※宣伝や迷惑行為を防止するため、当サイト、姉妹サイト、IPAサイト以外のURLを含む記事の投稿はできません。

投稿記事削除用フォーム

投稿番号:
パスワード:

その他のスレッド


Pagetop