JavaScriptで配列を扱う「Array」と「スタック」「LIFO」「FIFO」の基本：JavaScript標準ライブラリの使い方超入門（3）（4/6 ページ）

[金城俊哉，著]

配列要素の取り出し（LIFO）

　コンピューターにおけるデータの取り扱い方法に、後入れ先出し法（LIFO：Last In First Out）と呼ばれる方法があります。LIFOは「スタック」というデータ構造で使わることから、変数の値を格納するメモリ上のスタック領域でも使われています。なお、「データ構造」とはスタックのように、あるデータのまとまりをコンピュータープログラムで扱いやすいように、一定の形式で格納したものを指します。

　前置きはこのくらいにして、LIFOでは、順番にデータを格納したあと、データを取り出すときは最後に格納したデータから順に取り出していきます。このようなことから「後入れ先出し」と呼ばれているわけです。これを配列に置き換えてみると、次のようになります。

「LIFOの使い道として代表的なものに、Webブラウザーにおける『履歴の管理』があります」

「[戻る]ボタンをクリックすると、最後に追加された履歴のページから順に表示されますが、これがまさしくLIFOなのですね」

Onepoint

[進む]ボタンの機能は、[戻る]ボタンで戻ったページのURLを順にpushで追加し、[進む]がクリックされたタイミングで、最後に追加されたURLから順にpopすることで実現できます。

JavaScriptでLIFOを実現

「ではJavaScriptでLIFOを再現してみましょう」

「LIFOなんて理屈のうえのことだと思ってたのですが、実際にできるんです?」

「Arrayオブジェクトには、配列末尾に要素を追加するpush（）、配列末尾から要素を取り出すpop（）というメソッドがあるんです。この2つのメソッドで『後入れ先出し』が実現できるんです」

「では、定義済の配列の末尾にpush（）で要素を追加し、このあと2回続けてpop（）で取り出して、最後にもう一度要素を追加する流れでプログラムを作ってみますね」

「確かに『後入れ先出し』になりましたね」

「どうです?　push（）とpop（）は常に配列の最後の要素に対して処理を行うので、配列の末尾に次々とデータを追加し、データを取り出すときは配列の末尾から順に取り出す処理が実現できるというわけです」

配列要素の取り出し（FIFO）

　コンピューターでデータを扱う方法には、LIFOのほかに先入れ先出し法（FIFO：First In FirstOut）があります。名前のとおり、先に入れたデータを先に取り出す、つまり古いデータから順に取り出す方式です。これを配列に置き換えてみると、次のようになります。

「FIFOはキューと呼ばれるデータ構造で使われます。キューの構造は、先に格納したデータから順番を待つかのように並んでいることから、待ち行列と呼ばれることもあります」

「そういえば、プリンターの印刷待ちってありますよね」

「プリンターの印刷待ちは、まさしくキュー構造を利用している代表的なものです。先に追加された印刷命令から順に処理していくためにキューが使われているというわけですね。このほかにCPUの計算待ちもキュー構造で処理されているんですよ」

JavaScriptでFIFOを実現

「例のごとくJavaScriptでFIFOを実現できるんですか?」

「JavaScriptでFIFOを実現するには、pop（）とshift（）メソッドを使います。shift（）は配列の先頭の要素を取り出すので、pop（）で追加した要素の最も古いデータから順に取り出していく処理が行えるというわけです」

「ということは、pop（）メソッドで配列の末尾に次々とデータを追加し、データを取り出すときはshift（）メソッドで配列の先頭の要素から取り出せば『先入れ先出し方式』のFIFOの処理が再現できますね。じゃデータの追加と取り出しをそれぞれ2回ずつ行ってみますね」

「push（）とshift（）を組み合わせることで、キュー構造におけるFIFOを実現することができたというわけです」