データ構造 (全29問中9問目)

No.9

配列を用いてスタックを実現する場合の構成要素として,最低限必要なものはどれか。
  • スタックに最後に入った要素を示す添字の変数
  • スタックに最初に入った要素と最後に入った要素を示す添字の変数
  • スタックに一つ前に入った要素を示す添字の変数を格納する配列
  • スタックの途中に入っている要素を示す添字の変数

分類

テクノロジ系 » アルゴリズムとプログラミング » データ構造

正解

解説

スタックは、データ挿入の時はデータの最後に追加し、データ取り出し(削除)の時はデータの最後から取り出す(削除)後入れ先出し(LIFO:Last-in First-out)の構造をもっています。スタックにおけるデータ操作は、データを挿入するPUSH命令、データを取り出すPOP命令を使用して行います。

配列Mを用いて、
 PUSH 1→PUSH 5→POP→PUSH 7 PUSH 6→PUSH 4→POP→POP→PUSH 3
という操作を行う場合、

PUSH 1
M(1)
PUSH 5
M(1,5)
POP
M(1)
PUSH 7
M(1,7)
PUSH 6
M(1,7,6)
PUSH 4
M(1,7,6,4)
POP
M(1,7,6)
POP
M(1,7)
PUSH 3
M(1,7,3)
という流れになり、PUSH操作では配列の最終要素の添え字+1の位置に新要素を追加、POP操作では配列の最終要素の添え字に位置する要素を削除することを行います。

つまり最低限「スタックに最後に入った要素を示す添字の変数」を保持していればスタック構造が実現できることになります。
© 2010-2018 応用情報技術者試験ドットコム All Rights Reserved.

Pagetop