paizaで学ぶスタック実装：JavaScriptのpush/popで理解するLIFOデータ構造

こんにちは、いーさんです。

今回は、paizaの「スタック実装編」を通して学んだ「スタック（Stack）」について解説します。

スタックは「後入れ先出し（LIFO: Last In First Out）」という特徴を持つデータ構造で、プログラミングの基本中の基本です。paizaで実際に問題を解きながら、その仕組みと実装方法を理解できました。

スタックとは？

スタックをイメージで理解する

スタックは、一番最後に入れたデータが一番最初に取り出されるデータ構造です。

身近な例：ブロックの積み重ね

想像してください。床にブロックを積み重ねていくとします：

最初にオレンジのブロックを置く
その上に黄色のブロックを置く
その上に青いブロックを置く
その上に緑のブロックを置く
その上に紫のブロックを置く
一番上に赤いブロックを置く

さて、ブロックを取るときはどうしますか？

一番上の赤いブロックから取りますよね。

ポイント：

最後に置いたブロックが最初に取れる
最初に置いたブロックが最後に取れる
途中のブロックは取り出せない（上から順番）

LIFO（Last In First Out）とは

スタックの動きを表す言葉です。

Last In（ラスト・イン）：最後に入った
First Out（ファースト・アウト）：最初に出る

覚え方： 「後入れ先出し」= 後に入れたものが先に出る

反対の構造： 「最初に入れたものが最初に出る」のは**キュー（Queue）**です（次の記事で解説します）。

スタックの基本操作

スタックには主に2つの操作があります。ブロックの例で考えると分かりやすいです。

1. push（プッシュ）

スタックの一番上にデータを追加します。

JavaScriptでの実装：

let stack = [];
stack.push("オレンジ");  // ["オレンジ"]
stack.push("黄色");      // ["オレンジ", "黄色"]
stack.push("青");        // ["オレンジ", "黄色", "青"]

2. pop（ポップ）

スタックの一番上からデータを取り出します。

JavaScriptでの実装：

let stack = ["オレンジ", "黄色", "青"];
let ブロック = stack.pop();   // ブロック = "青", stack = ["オレンジ", "黄色"]
let ブロック2 = stack.pop();  // ブロック2 = "黄色", stack = ["オレンジ"]

重要なポイント：

pop() は取り出したデータを返してくれる
取り出したデータはスタックからなくなる（削除される）
一番上からしか取り出せない

JavaScriptでのスタック実装

JavaScriptでは、配列（Array）がそのままスタックとして使えます。

基本的な実装

// スタックの初期化
let stack = [];

// データを追加（push）
stack.push("Apple");
stack.push("Banana");
stack.push("Cherry");

console.log(stack);  // ["Apple", "Banana", "Cherry"]

// データを取り出す（pop）
let fruit = stack.pop();
console.log(fruit);  // "Cherry"
console.log(stack);  // ["Apple", "Banana"]

スタックが空かどうかチェック

if(stack.length === 0){
    console.log("スタックは空です");
} else {
    console.log("スタックにデータがあります");
}

一番上のデータを見る（取り出さない）

let stack = [1, 2, 3];

// 最後の要素を見るだけ（削除しない）
let top = stack[stack.length - 1];
console.log(top);    // 3
console.log(stack);  // [1, 2, 3] ← 変わらない

paizaで解いた問題：スタック実装

paizaの「スタック実装編 step 2」という問題に取り組みました。

問題概要

Q個のクエリ（操作）が与えられます。各クエリは以下のいずれかです：

クエリ1 N：整数Nをスタックに追加し、スタックの中身を出力
クエリ2：スタックから1つ取り出して出力し、残りのスタックを出力

実装したコード

const Q = Number(lines[0]);
let LIFO = [];  // スタックを表す配列

for(let i = 0; i < Q; i++){
    let query = lines[i+1].split(" ");
    
    if(query[0] === "1"){
        // データを追加
        LIFO.push(query[1]);
        console.log(...LIFO);
    } else {
        // データを取り出す
        console.log(LIFO.pop());
        console.log(...LIFO);
    }
}

コードの解説

1. スタックの初期化

let LIFO = [];

空の配列を用意します。これがスタックになります。

LIFO = Last In First Out を意味する変数名にしました。

2. クエリの処理

let query = lines[i+1].split(" ");

クエリを分解します：

"1 5" → ["1", "5"]
"2" → ["2"]

3. push操作

if(query[0] === "1"){
    LIFO.push(query[1]);
    console.log(...LIFO);
}

query[0] === "1" なら追加操作
query[1] をスタックに追加
...LIFO でスタックの中身をスペース区切りで出力

スプレッド構文 ... について：

let arr = [1, 2, 3];
console.log(arr);      // [1, 2, 3]
console.log(...arr);   // 1 2 3

4. pop操作（ここが重要！）

else {
    console.log(LIFO.pop());
    console.log(...LIFO);
}

query[0] === "2" なら取り出し操作
pop() で取り出したデータを出力
その後、残りのスタックを出力

paizaで学んだ重要なポイント：

最初、私は pop() が「削除するだけ」のメソッドだと思っていました。

でも実際は違いました！

let stack = [1, 2, 3];
let value = stack.pop();  

console.log(value);  // 3 ← 取り出した値が返ってくる！
console.log(stack);  // [1, 2] ← そして削除される

pop() の動作順序：

まず、一番上の値を取得（返り値として返す）
その後、その値をスタックから削除

だから、console.log(LIFO.pop()) と書くだけで、取り出した値を表示できるんです。

これを理解していないと：

// ❌ 間違った理解
LIFO.pop();  // 削除するだけ？
console.log(何を出力する？);  // 値が分からない

// ✅ 正しい理解
console.log(LIFO.pop());  // 取り出した値が返ってくるから直接出力できる

この動作を知ったことで、コードがとてもシンプルになりました！

実行例

入力：

実行の流れ：

// 初期状態
LIFO = []

// クエリ1: "1 3" → 3を追加
LIFO.push("3")
出力: 3
LIFO = [3]

// クエリ2: "1 5" → 5を追加
LIFO.push("5")
出力: 3 5
LIFO = [3, 5]

// クエリ3: "2" → 取り出す
出力: 5 ← pop()の結果
出力: 3 ← 残りのスタック
LIFO = [3]

// クエリ4: "1 7" → 7を追加
LIFO.push("7")
出力: 3 7
LIFO = [3, 7]

// クエリ5: "2" → 取り出す
出力: 7
出力: 3
LIFO = [3]

最終出力：

スタック実装のポイント

1. 配列のどちら側を使うか

JavaScriptでは配列の末尾を使うのが効率的です。

// ✅ 推奨：末尾を使う
stack.push(data);  // O(1) - 高速
stack.pop();       // O(1) - 高速

// ❌ 非推奨：先頭を使う
stack.unshift(data);  // O(n) - 遅い
stack.shift();        // O(n) - 遅い

理由： 配列の先頭に追加・削除すると、全要素をずらす必要があるため遅い。

2. 空のスタックからpopしない

let stack = [];

// ❌ 空の状態でpop
let data = stack.pop();  // undefined

// ✅ チェックしてからpop
if(stack.length > 0){
    let data = stack.pop();
}

3. スタックのサイズを確認

let stack = [1, 2, 3];

console.log(stack.length);  // 3

// 空かどうか
if(stack.length === 0){
    console.log("空です");
}

まとめ

今回、paizaの「スタック実装編」を通して学んだポイント：

スタックはLIFO（後入れ先出し）のデータ構造
ブロックの積み重ねをイメージすると理解しやすい
JavaScriptでは配列の push/pop で簡単に実装できる
配列の末尾を使うと効率的（O(1)）
空のスタックから pop しないように注意
pop() は取り出した値を返してから削除する（重要！）

スタックの基本操作まとめ

操作	メソッド	説明	計算量
追加	`push(data)`	スタックの一番上に追加	O(1)
取り出し	`pop()`	スタックの一番上から取り出す	O(1)
確認	`stack[stack.length-1]`	一番上を見る（削除しない）	O(1)
サイズ	`stack.length`	スタック内の要素数	O(1)
空チェック	`stack.length === 0`	スタックが空か確認	O(1)