HOME»基本情報技術者試験掲示板»スタックの問題について
投稿する
スタックの問題について [5789]
はやしさん(No.1)
すみません。スタックの問題について分からないところがあります。
整数型:pop()
整数型:ret
if (pointが1より大きい)
point ←point−1 ①
ret←stack[point] ②
else
ret←(−1)
endif
return ret
※pop() スタックからデータを取り出してその値を返す。スタックが空で取り出すデータが無いときは−1を返す
stack スタックのデータを格納する配列
point スタックポインタ
①と②が反対なら意味がわかる気がするのですが、あり得ないので有識者方よろしくお願いいたします
整数型:pop()
整数型:ret
if (pointが1より大きい)
point ←point−1 ①
ret←stack[point] ②
else
ret←(−1)
endif
return ret
※pop() スタックからデータを取り出してその値を返す。スタックが空で取り出すデータが無いときは−1を返す
stack スタックのデータを格納する配列
point スタックポインタ
①と②が反対なら意味がわかる気がするのですが、あり得ないので有識者方よろしくお願いいたします
2025.02.06 22:43
pop太郎さん(No.2)
たとえば、
stack={1, 2, 3}
point=4
を初期値として考えると、
pop()実行。
pointが1より大きいので、
①point=4−1
②ret=stack[3](インデックスが1からはじまるとするなら、3がretに代入されます)
returnで3が返ります。
次は、
stack={1, 2}
point=3
であり、
pop()実行。
pointが1より大きいので、
①point=3−1
②ret=stack[2](インデックスが1からはじまるとするなら、2がretに代入されます)
returnで2が返ります。
次は、
stack={1}
point=2
であり、
pop()実行。
pointが1より大きいので、
①point=2−1
②ret=stack[1](インデックスが1からはじまるとするなら、1がretに代入されます)
returnで1が返ります。
次は、
stack={}
point=1
であり、
pop()実行。
pointは1であり、1より大きくないので、
elseにはいり、
ret=−1
returnで−1が返ります。
なんら矛盾してるようには思いませんが。。。かりにpush()するなら、この流れを遡ることになるのではないでしょうか。
初期値を考えることとか、インデックスが0はじまりか1はじまりかを考えるのがミソとちがいますかね。
ちがってたらごめんなさいね!
stack={1, 2, 3}
point=4
を初期値として考えると、
pop()実行。
pointが1より大きいので、
①point=4−1
②ret=stack[3](インデックスが1からはじまるとするなら、3がretに代入されます)
returnで3が返ります。
次は、
stack={1, 2}
point=3
であり、
pop()実行。
pointが1より大きいので、
①point=3−1
②ret=stack[2](インデックスが1からはじまるとするなら、2がretに代入されます)
returnで2が返ります。
次は、
stack={1}
point=2
であり、
pop()実行。
pointが1より大きいので、
①point=2−1
②ret=stack[1](インデックスが1からはじまるとするなら、1がretに代入されます)
returnで1が返ります。
次は、
stack={}
point=1
であり、
pop()実行。
pointは1であり、1より大きくないので、
elseにはいり、
ret=−1
returnで−1が返ります。
なんら矛盾してるようには思いませんが。。。かりにpush()するなら、この流れを遡ることになるのではないでしょうか。
初期値を考えることとか、インデックスが0はじまりか1はじまりかを考えるのがミソとちがいますかね。
ちがってたらごめんなさいね!
2025.02.07 00:46
はやしさん(No.3)
親切に解答ありがとうございます。
しかし、初期値を適切に設定しないと成り立たないのでしょうか
自分はstack={1, 2, 3}
point=3でやってしまいました
しかし、初期値を適切に設定しないと成り立たないのでしょうか
自分はstack={1, 2, 3}
point=3でやってしまいました
2025.02.07 09:19
yukiさん(No.4)
スタックが空で取り出すデータが無いときは−1を返すということは、if文より、pointが1より大きい時にはスタックにデータがあるということです。
逆に言うと、pointが1以下の時、スタックは空になります。
ということは、スタックにひとつデータがpush()されるとpoint=2、ふたつめのデータがpush()されるとpoint=3、みっつめのデータがpush()されるとpoint=4、という風に、pointは常にスタックの最後のデータの次、つまり次にデータがpush()されるべき場所を指しています。
pop()する時には、問題文のとおり、まずpoint−1を先にしないと、空の部分を取り出してしまことになりますよね。
スタックの問題は、このようにpointの位置が最後のデータの次を指している時と、最後のデータの位置を指している時、ふたつのパターンがありますので、その見極めが重要だと思います。
逆に言うと、pointが1以下の時、スタックは空になります。
ということは、スタックにひとつデータがpush()されるとpoint=2、ふたつめのデータがpush()されるとpoint=3、みっつめのデータがpush()されるとpoint=4、という風に、pointは常にスタックの最後のデータの次、つまり次にデータがpush()されるべき場所を指しています。
pop()する時には、問題文のとおり、まずpoint−1を先にしないと、空の部分を取り出してしまことになりますよね。
スタックの問題は、このようにpointの位置が最後のデータの次を指している時と、最後のデータの位置を指している時、ふたつのパターンがありますので、その見極めが重要だと思います。
2025.02.07 11:06
はやしさん(No.5)
お二方ありがとうございます
よくわかりました
よくわかりました
2025.02.07 11:57