応用情報技術者 試験情報＆徹底解説

スタックは、データ挿入の時はデータの最後に追加し、データ取り出し(削除)の時はデータの最後から取り出す(削除)後入れ先出し(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操作では配列の最終要素の添え字に位置する要素を削除することを行います。

つまり最低限「スタックに最後に入った要素を示す添字の変数」を保持していればスタック構造が実現できることになります。