スタック(Stack), LIFO, FILO とは

スタックとLIFO JavaScript

この記事では、スタック(Stack)と呼ばれるコンピュータでよく使用されるデータ構造について、シンプルに解説する。

スポンサーリンク

CPU内のスタック

プログラミングの学習をしていると、スタック(Stack)という用語に出会うことがしばしばある。私が最初にこの言葉に触れたのは、PICマイコンと呼ばれる小さなCPUのプログラミングについて学習しているときだったと思う。

PICマイコン(PIC16F84)
Microchip社 PICマイコン(PIC16F84)

このCPUに対する命令、つまりプログラムを作成するときは、アセンブリ言語やC言語といったCPUを直接制御するのに適した言語を利用するのだが、CPUを制御するためには、言語の命令や構文を理解するだけでなく、CPUの内部の構造も理解する必要がある。

CPUがどのようにして、我々が記述した命令を実行するのかを理解した上でプログラムを作成する必要があるのだ。CPUの種類が異なれば(たとえ同じメーカーのCPUであったとしても)内部の構造が異なるため、その都度、そのCPUの内部構造を理解しなければならない。

ということで、私は上記PICマイコンの内部構造を理解するため、CPUのマニュアルをメーカー(この場合、Microchip社)のサイトから取得して、CPUと仲良くなろうと努めた。そのときに、マニュアルの中でスタック(Stack)という用語に初めて出会った。

PICマイコンにおけるスタック
Microchip社 リファレンスマニュアル(PIC16F8X)

スタック(Stack)というものが、ハードウェア(電子回路)として組み込まれていることが何となく分かってもらえれば、それだけで良い。PICマイコンの話はこれで終わり。

JavaScript エンジンのスタック

JavaScript というプログラミング言語で記述した処理がどのように実行されるのかを理解するために、JavaScript エンジンというものについて学んでいるときにも、スタック(Stack)に出会った。

この絵は、左側の四角い枠で囲われた JavaScriptエンジンの中に、「Call Stack」と呼ばれる Stack の名を持った何かが存在していて、重要な働きをしていることを示している。

さきほどのPICマイコンにおけるスタック(Stack)はハードウェア(電子回路)で作られていたが、この JavaScript エンジンの中のスタックは、プログラムで作成されている。例えば、「V8」とよばれる Google が開発している JavaScript エンジンでは、C++ というプログラミング言語で作成されている。

この JavaScript エンジンがどの様にしてプログラムを実行するのかを理解するためには、スタック(Stack)というものにどんな働きがあるのかを理解していることが前提になることは分かってもらえるだろう。

スタック(Stack)とは何か?

前置きが長くなってしまったが、ではこのスタック(Stack)とはいったい何なのか?

プログラミングに関する色々なことを、深く知りたいと思って勉強を進めているとよく出会うスタック(Stack)。ぜひ理解しておきたいキーワードだ。とても重要な役割を持っているのだが、その働きはとてもシンプル。

下の画像を見て欲しい。これもスタック(Stack)だ。

スタック(Stack)とは「積み重なる」という意味だ。上の画像では茶碗が積み重ねられている。この積み重ねられた(スタックされた)茶碗は、後から積み重ねた茶碗が最初に取り出される、という重要な特徴を持っている。

一般的に、このように後から入れた要素が先に取り出される性質LIFO(Last In First Out)と呼ぶ。また、これは先に入れた要素が後から取り出されると表現することもできるので、FILO(First In Last Out)とも呼ばれたりする。

そしてこの LIFO(FILO)の性質をもったデータ構造をスタック(Stack)と呼んでいる。

先述のPICマイコンであれば、電子回路で LIFO の機能を実現しているし、V8(Google の JavaScriptエンジン)であれば、C++ というプログラミング言語で LIFO を実現している。どちらも LIFO の性質を有しているのでスタック(Stack)と表現されていたわけだ。

したがって、プログラミングの分野でスタック(Stack)という用語に出会ったら、上の積み重ねられた茶碗を思い出してほしい。後入れ先出し(LIFO)をイメージできれば、どのような文脈でスタック(Stack)に出会ったとしても、そこで行わている説明を理解できるようになるはずだ。

本気のプログラミングスクール【ウェブカツ】

タイトルとURLをコピーしました