はじめに: スタックは「最後に入れたものを先に取り出す」データ構造
これまでの記事では、線形探索や二分探索のように「データの中から目的の値を探す方法」を見てきました。次に押さえておきたいのが、データをどのように持つかという考え方です。
その代表例のひとつが、スタックです。
スタックは、最後に入れたデータを最初に取り出すデータ構造です。基本情報処理技術者試験では、アルゴリズムやデータ構造の分野でよく出てくる考え方です。
Web開発でも、Undo機能、ブラウザの履歴、関数呼び出し、エラーのスタックトレースなど、スタックの考え方に触れる場面があります。この記事では、JavaScriptの配列を使ってスタックを実装しながら、試験に出る知識を実務につなげて理解していきます。
スタックとは何か
スタックは、データを積み重ねるように扱うデータ構造です。
たとえば、本を机の上に1冊ずつ積んでいく場面を考えてみます。最後に置いた本は、一番上にあります。取り出すときも、一番上にある最後の本から取り出すことになります。
このように、最後に入れたものを最初に取り出す仕組みを LIFO と呼びます。LIFO は Last In, First Out の略で、日本語では「後入れ先出し」と説明されます。
スタックでは、途中にあるデータを直接取り出すのではなく、基本的には一番上のデータから順に取り出します。この制約があることで、処理の順番をシンプルに管理できます。
スタックの基本操作: push と pop
スタックの基本操作は、主に push と pop です。
push は、スタックにデータを追加する操作です。積み重ねた本の一番上に、新しい本を置くイメージです。
pop は、スタックからデータを取り出す操作です。一番上にあるデータを取り出します。つまり、最後に push したデータが、最初に pop されます。
また、一番上のデータを見るだけの操作を peek と呼ぶことがあります。peek は確認するだけなので、データを取り出しません。
空のスタックから pop しようとした場合は、取り出すものがありません。実装によっては undefined が返ったり、エラーとして扱ったりします。
JavaScriptの配列でスタックを実装する
JavaScriptの配列には、最初から push() と pop() があります。そのため、配列を使うとスタックの動きを簡単に確認できます。
const stack = [];
stack.push('A');
stack.push('B');
stack.push('C');
console.log(stack);
console.log(stack.pop());
console.log(stack.pop());
console.log(stack.pop());このコードでは、A、B、C の順にデータを追加しています。
取り出すときは、最後に追加した C から取り出されます。続いて B、最後に A が取り出されます。
追加した順番: A -> B -> C
取り出す順番: C -> B -> Aこの順番が、スタックの大事な特徴です。配列に入れた順番と、取り出される順番が逆になることを確認しておきましょう。
スタックをクラスとしてまとめる
配列をそのまま使うだけでもスタックの動きは確認できます。ただ、操作の意味を分かりやすくするために、Stack クラスとしてまとめてみます。
class Stack {
constructor() {
this.items = [];
}
push(item) {
this.items.push(item);
}
pop() {
return this.items.pop();
}
peek() {
return this.items[this.items.length - 1];
}
isEmpty() {
return this.items.length === 0;
}
}
const stack = new Stack();
stack.push('page1');
stack.push('page2');
stack.push('page3');
console.log(stack.peek());
console.log(stack.pop());
console.log(stack.pop());
console.log(stack.isEmpty());push() はデータを追加し、pop() は一番上のデータを取り出します。peek() は一番上のデータを見るだけです。isEmpty() は、スタックが空かどうかを確認します。
基本情報の学習では、クラスの書き方そのものよりも、それぞれの操作でスタックの中身がどう変わるかを追うことが大切です。
スタックはどこで使われるか
スタックの考え方は、実務のいろいろな場面に出てきます。
分かりやすい例は Undo 機能です。操作を順番にスタックへ積んでおけば、戻すときには直前の操作から取り出せます。最後に行った操作を最初に戻すので、スタックの考え方と相性がよいです。
ブラウザの「戻る」操作も、履歴を積んでおき、直前のページへ戻るという意味でスタックに近いイメージです。
また、JavaScriptでエラーが出たときに見るスタックトレースや、関数呼び出しのコールスタックにも、スタックの考え方が関係します。関数が呼ばれるたびに処理が積まれ、終わったものから順に戻っていきます。
ほかにも、括弧の対応チェックのようなアルゴリズムでもスタックが使われます。開き括弧を積み、閉じ括弧が来たら取り出して対応を確認する、という考え方です。
キューとの違いを軽く押さえる
スタックとセットでよく出てくるデータ構造に、キューがあります。
スタックは後入れ先出しです。最後に入れたものを先に取り出します。
一方、キューは先入れ先出しです。先に入れたものを先に取り出します。英語では FIFO、First In, First Out と呼ばれます。
行列に並ぶ場面を考えると、キューのイメージが分かりやすいです。先に並んだ人から順に処理されます。
基本情報処理技術者試験では、スタックとキューの違いが問われることがあります。スタックは LIFO、キューは FIFO。この対比は必ず押さえておきましょう。
試験ではどう問われるか
試験では、スタックの操作を順番に追う問題が出てきます。
たとえば、push A、push B、push C のあとに pop したら、取り出されるのは C です。さらに pop すると B が取り出されます。
問われやすいポイントは、次のようなものです。
pushとpopの意味- 操作後のスタックの中身
- 次に取り出される値
- LIFO の意味
- キューとの違い
- 関数呼び出しや逆ポーランド記法など、スタックを使う場面
特に、操作の順番を落ち着いて追うことが大切です。図を書いて、上に積まれているものから取り出すと考えると、間違えにくくなります。
実務ではどう使われるか
実務では、スタックという名前を直接使わなくても、考え方として登場することがあります。
JavaScriptの配列で push() と pop() を使う処理は、スタック的な使い方です。履歴管理、Undo/Redo、画面遷移、フォーム操作の記録など、最後の操作から戻したい場面で使えます。
また、エラー調査でスタックトレースを読むときにも役立ちます。どの関数からどの関数が呼ばれたのかをたどるとき、スタックの考え方を知っていると理解しやすくなります。
実装そのものはシンプルですが、「データをどの順番で入れて、どの順番で取り出すか」を意識できるようになると、コードの読み方が少し変わります。
まとめ: スタックは「積んで、上から取り出す」基本のデータ構造
スタックは、最後に入れたデータを最初に取り出すデータ構造です。この性質を LIFO、または後入れ先出しと呼びます。
JavaScriptでは、配列の push() と pop() を使うことで、スタックの動きを簡単に確認できます。必要に応じて peek() や isEmpty() のような操作を加えると、スタックとして扱いやすくなります。
基本情報処理技術者試験では、操作後の状態、次に取り出される値、キューとの違いが重要です。実務でも、Undo、履歴管理、コールスタック、スタックトレースなどに考え方がつながります。
次に学ぶなら、スタックと対になるキューを実装してみると、データ構造の違いがさらに分かりやすくなります。
コメント