令和7年度 科目B 問3
データ構造
スタックに関する問題
次のプログラム中の［a］と［b］に入れる正しい答えの組合せを，解答群の中から選べ。ここで，配列の要素番号は1から始まる。
関数pushは，引数で与えられた整数をスタックに格納する。格納できた場合はtrueを返し，格納できなかった場合はfalseを返す。
関数popは，スタックから値を取り出して返す。スタックが空のときは未定義の値を返す。
スタックを，要素数が4である大域の整数型の配列stack，及び次に値を格納する位置を示す大域の変数stackPosで表現する。スタックの初期状態を図に示す。
プログラムでは，配列の領域外を参照してはならないものとする。
図 スタックの初期状態:
| 要素番号 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| stack | 4 | 3 | （網掛け） | （網掛け） |
- stackPosは，要素番号3の要素を下から↑で指している。
- 注記 網掛けはその要素が未定義であることを示す。
〔プログラム〕
大域: 整数型: stackPos ← 3
大域: 整数型の配列: stack ← {4, 3, 未定義の値, 未定義の値}
○論理型: push(整数型: inputData)
if (stackPos ≦ stackの要素数)
stack[［a］] ← inputData
stackPos ← stackPos ＋ 1
return true
else
return false
endif
○整数型: pop()
整数型: popData ← 未定義の値
if (stackPos ＞ 1)
stackPos ← ［b］
popData ← stack[stackPos]
stack[stackPos] ← 未定義の値
endif
return popData
解答群は原典では a・b の組合せの表。
- アa：stackPos ／ b：stackPos ＋ 1
- イa：stackPos ／ b：stackPos － 1
- ウa：stackPos － 1 ／ b：stackPos ＋ 1
- エa：stackPos － 1 ／ b：stackPos － 1
答えと解説を見る
✓ これが正解イa：stackPos ／ b：stackPos － 1
解説
stackPosは空きを指すので、pushはそこへ、popは1戻して読みます。
スタックは、最後に入れた値を最初に取り出すデータ構造で、LIFOとも呼ばれます。この問では、配列stackと、次に値を格納する位置を示すstackPosで表しています。軸は、stackPosが指すのは空いている場所であって、最後に入れた値のある場所ではない、という一点です。初期状態でも、値の入っている要素番号は1と2で、stackPosは空きの3を指しています。
pushは、空きの位置であるstack[stackPos]にそのまま値を書き、その後でstackPosに1を足して次の空きを指させます。例えばpush(5)を呼ぶと、stackPos＝3は要素数4以下なのでstack[3]に5が入り、stackPosは4になります。続けてpush(6)でstack[4]に6が入りstackPosは5、さらにpush(7)では5が4を超えるのでfalseを返し、配列の外には書きません。
popは逆に、まずstackPosから1を引いて最後に値が入った位置へ戻し、そこから値を読み出します。stackPos＝5の状態でpopを呼ぶと、stackPosは4になり、stack[4]の6が返って、その要素は未定義の値に戻ります。直前に入れた6が最初に出てくるので、スタックとして正しく動いています。よって、aはstackPos、bはstackPos － 1の組合せです。
見分け方は、位置を示す変数が次の空きを指すのか最後の値を指すのかを初期状態の図から読み取り、書く前に動かすか後に動かすかを決めることです。
ほかの選択肢はなぜ違うのか
- 項番a：aにはstackPosがそのまま入ります。stackPos － 1を添字にすると、初期状態のpush(5)でstack[2]の3が5で上書きされ、まだ取り出していない値が消えます。stackPosは空きを指しているので、1を引く必要はありません。
- 項番b：bにはstackPos － 1が入ります。stackPos ＋ 1にすると、初期状態のpopでstackPosが4になり、値の入っていない未定義のstack[4]を読んでしまいます。満杯でstackPos＝5のときは6になり、要素数4の配列の領域外を参照します。
出典：令和7年度 基本情報技術者試験 科目B 問3
この解説に誤りを見つけたら教えてください。直して、直した記録を残します。誤りを報告する（メールが開きます）