十分な大きさの配列Aと初期値が0の変数pに対して，関数f(x)とg()が次のとおり定義されている。
配列Aと変数pは，関数f(x)とg()だけでアクセス可能である。
これらの関数が操作するデータ構造はどれか。
function f(x) {
p = p+1;
A[p] = x;
return None;
}
function g() {
x = A[p];
p = p-1;
return x;
}
正答2
解説
正解は2です。
配列とポインタ変数を使った関数の動きから、データ構造を判定する問題です。
f(x)はpを1増やしてからA[p]にxを格納します。
g()はA[p]を取り出してからpを1減らします。
つまり、追加も取出しも同じ端（pが指す位置）で行われます。
【処理のたどり】
f(10)を呼ぶと、p＝1でA[1]＝10になります。
f(20)を呼ぶと、p＝2でA[2]＝20になります。
g()を呼ぶと、A[2]の20が返り、pは1に戻ります。
最後に入れた20が最初に取り出されるので、後入れ先出しです。
【選択肢別解説】
1：× キューは先入れ先出し（FIFO：First In First Out）のデータ構造です。
末尾に追加し先頭から取り出すため、先頭と末尾の2つの位置を管理する必要があります。
2：○ スタックは後入れ先出し（LIFO：Last In First Out）のデータ構造です。
f(x)がプッシュ、g()がポップに当たり、pがスタックの頂上を指しています。
3：× ハッシュは、キーからハッシュ関数で格納位置を計算してデータを置く方式です。
本問の関数はキーから位置を計算していません。
4：× ヒープは、親が子以上（または以下）という条件を満たす完全2分木です。
値の大小比較による並べ替えを行っていないので該当しません。
【ポイント】
スタックは頂上を指す変数1つで管理でき、関数呼出しや後置記法の計算に使われます。
キューは先頭と末尾の2つの位置を管理し、待ち行列やバッファに使われます。