スタックとは？データ構造の基本をわかりやすく解説

ブラウザで「戻る」ボタンを押すと、さっき見ていたページに戻れますよね。
Word で「元に戻す（Ctrl+Z）」を押すと、一つ前の状態に戻せます。

実は、これらの機能には「スタック」というデータ構造が使われているんです。

スタックは、プログラミングで最も基本的で重要なデータ構造の一つです。シンプルですが、コンパイラ、ブラウザ、ゲームなど、あらゆるソフトウェアの中で活躍しています。

この記事では、スタックとは何か、どんな仕組みで動くのか、そしてどこで使われているのかを、プログラミング初心者の方にもわかりやすく解説していきます。

スタックとは？
1. 後入れ先出しって何？
2. 英語の Stack の意味
スタックの基本操作
スタックとキューの違い
1. キューとは？
2. 比較表
スタックの実装方法
1. 1. 配列（Array）を使った実装
2. 2. 連結リスト（Linked List）を使った実装
スタックが使われている場面
スタックオーバーフロー
1. スタックオーバーフローとは？
2. Q&Aサイトの名前にも
各言語でのスタック実装
スタックの計算量
まとめ

スタックとは？

スタック（Stack）は、後入れ先出し（LIFO: Last In First Out）の原則に従うデータ構造です。

後入れ先出しって何？

「最後に入れたものが、最初に出てくる」という意味です。

身近な例で考えてみましょう：

お皿を積み重ねる場合

お皿を洗って積んでいく → 上に上に積み重なる
お皿を使う時 → 一番上から取る
一番下のお皿を取りたい → 上のお皿を全部どかさないと取れない

本を机に積む場合

本を積んでいく → 上に積み重なる
本を読みたい → 一番上の本から取る

このように、「最後に置いたものが最初に取れる」構造がスタックなんです。

英語の Stack の意味

「Stack」という英語には「積み重ね」「山積み」という意味があります。

まさに、データを積み重ねるイメージから名付けられたんですね。

スタックの基本操作

スタックには、いくつかの基本的な操作があります。

1. Push（プッシュ）- データを追加

スタックにデータを追加する操作を Push（プッシュ） と言います。

イメージ：
お皿を一番上に置く = スタックにデータを追加

例：

初期状態：  [ ]
Push(A) →  [A]
Push(B) →  [A, B]
Push(C) →  [A, B, C]  ← Cが一番上

2. Pop（ポップ）- データを取り出す

スタックから一番上のデータを取り出す操作を Pop（ポップ） と言います。

イメージ：
一番上のお皿を取る = スタックからデータを取り出す

例：

現在の状態：[A, B, C]  ← Cが一番上
Pop() → Cを取り出す
結果：      [A, B]     ← Bが新しい一番上

Pop() → Bを取り出す
結果：      [A]

3. Peek（ピーク）- 一番上を見る

一番上のデータを取り出さずに 見るだけ の操作を Peek（ピーク） または Top（トップ） と言います。

イメージ：
一番上のお皿を確認するだけ（取らない）

例：

現在の状態：[A, B, C]
Peek() → Cを返す（でも取り出さない）
結果：      [A, B, C]  ← そのまま

4. isEmpty（イズエンプティ）- 空かどうか確認

スタックが空かどうかを確認する操作です。

なぜ必要？
空のスタックからPopしようとすると、エラーになってしまうからです。

例：

スタック：[A, B]
isEmpty() → False（空ではない）

スタック：[ ]
isEmpty() → True（空）

スタックとキューの違い

スタックと並んでよく登場するのが「キュー（Queue）」というデータ構造です。

キューとは？

キューは 先入れ先出し（FIFO: First In First Out） のデータ構造です。

イメージ：

レジの行列
列に並んだ人
最初に並んだ人が最初にサービスを受ける

比較表

項目	スタック（Stack）	キュー（Queue）
原則	LIFO（後入れ先出し）	FIFO（先入れ先出し）
例え	積まれたお皿	レジの行列
追加	上に積む（Push）	列の最後に並ぶ（Enqueue）
取り出し	上から取る（Pop）	列の先頭から出る（Dequeue）

覚え方：

スタック = お皿を積む → 上から取る
キュー = 列に並ぶ → 先頭から出る

スタックの実装方法

スタックは、主に2つの方法で実装できます。

1. 配列（Array）を使った実装

メリット：

シンプルで実装しやすい
メモリ効率が良い
アクセスが速い

デメリット：

サイズが固定される（最初に決めた大きさまで）
サイズを超えると「スタックオーバーフロー」が起きる

Pythonでの簡単な例：

# スタックを配列（リスト）で実装
stack = []

# Push - データを追加
stack.append('A')
stack.append('B')
stack.append('C')
print(stack)  # ['A', 'B', 'C']

# Pop - データを取り出す
data = stack.pop()
print(data)   # 'C'
print(stack)  # ['A', 'B']

# Peek - 一番上を見る
top = stack[-1]
print(top)    # 'B'

# isEmpty - 空かチェック
is_empty = len(stack) == 0
print(is_empty)  # False

2. 連結リスト（Linked List）を使った実装

メリット：

サイズが動的に変わる（いくらでも追加できる）
スタックオーバーフローが起きにくい

デメリット：

ポインタ（次の要素への参照）を保持する分、メモリを多く使う
実装がやや複雑

実際のプログラミングでは、言語によって標準でスタックが用意されていることが多いです。

スタックが使われている場面

スタックは、実は私たちが毎日使っているソフトウェアの中で大活躍しています。

1. ブラウザの「戻る」ボタン

Webブラウザで複数のページを見た時を考えてみましょう。

動き：

ページAを見る → スタックに A を Push
リンクをクリックしてページBへ → スタックに B を Push
さらにページCへ → スタックに C を Push
「戻る」ボタンを押す → Pop して C を取り出し、B に戻る
もう一度「戻る」→ Pop して B を取り出し、A に戻る

スタック：[A] → [A, B] → [A, B, C] → [A, B] → [A]

「進む」ボタンも、別のスタックで管理されているんです。

2. テキストエディタの「元に戻す（Undo）」機能

Wordやメモ帳で文字を入力する時：

動き：

“Hello”と入力 → スタックに Push
” World”と追加 → スタックに Push
“!”と追加 → スタックに Push
Ctrl+Z（Undo）→ Pop して “!” を取り消す
もう一度 Ctrl+Z → Pop して ” World” を取り消す

状態：Hello → Hello World → Hello World! → Hello World → Hello

「やり直す（Redo）」も、別のスタックで管理されています。

3. 関数の呼び出し（コールスタック）

プログラムで関数を呼び出す時、コンピューターは コールスタック を使っています。

例：

def funcA():
    print("A start")
    funcB()
    print("A end")

def funcB():
    print("B start")
    funcC()
    print("B end")

def funcC():
    print("C")

funcA()

実行の流れ：

1. funcAを呼び出す → スタックに [funcA] を Push
2. funcAの中でfuncBを呼び出す → スタックに [funcA, funcB] を Push
3. funcBの中でfuncCを呼び出す → スタックに [funcA, funcB, funcC] を Push
4. funcCが終了 → Pop して [funcA, funcB]
5. funcBが終了 → Pop して [funcA]
6. funcAが終了 → Pop して []

このスタックのことを「コールスタック（Call Stack）」と呼びます。

4. 数式の計算（逆ポーランド記法）

計算機や電卓の中では、数式をスタックで計算しています。

例：（5 + 3）× 2 の計算

通常の書き方（中置記法）：
(5 + 3) × 2

逆ポーランド記法（後置記法）：
5 3 + 2 ×

スタックでの計算：

5をPush → [5]
3をPush → [5, 3]
+が来たら、5と3をPopして足し算、結果8をPush → [8]
2をPush → [8, 2]
×が来たら、8と2をPopして掛け算、結果16をPush → [16]
答え：16

5. カッコの対応チェック

プログラムのコンパイラは、カッコが正しく閉じられているかをスタックで確認します。

例： ((a + b) * (c - d))

チェックの流れ：

1. '(' → Push → [(]
2. '(' → Push → [(, (]
3. ')' → Pop  → [(]
4. '(' → Push → [(, (]
5. ')' → Pop  → [(]
6. ')' → Pop  → []（空になったのでOK）

もし最後に空にならなければ、カッコが閉じられていないエラーです。

6. ゲームでの「やり直し」機能

パズルゲームやチェスなどで、1手戻る機能もスタックです。

動き：

手を打つ → その手をスタックに記録
「戻る」→ スタックから Pop して、前の状態に戻す

スタックオーバーフロー

「スタックオーバーフロー（Stack Overflow）」という言葉を聞いたことがありますか？

スタックオーバーフローとは？

スタックに データを入れすぎて、容量を超えてしまう エラーのことです。

起こる原因：

1. 無限ループ的な再帰呼び出し

def recursive_func():
    recursive_func()  # 自分を呼び出し続ける

recursive_func()  # これを実行するとスタックオーバーフロー

関数が自分自身を無限に呼び出すと、コールスタックがどんどん積み重なって、最終的にメモリが足りなくなります。

2. 深すぎる再帰

def countdown(n):
    if n == 0:
        return
    countdown(n - 1)

countdown(100000)  # 深すぎる再帰でエラーになる可能性

対策：

再帰の深さに制限を設ける
再帰ではなく、ループを使う
動的なスタック（連結リストなど）を使う

Q&Aサイトの名前にも

有名なプログラマー向けQ&Aサイト「Stack Overflow」も、この用語から名付けられているんですね。

各言語でのスタック実装

Python

Pythonでは、リスト（list）をスタックとして使えます。

stack = []
stack.append(1)  # Push
stack.append(2)
stack.append(3)
print(stack.pop())  # Pop → 3
print(stack[-1])    # Peek → 2

Java

Javaには標準でStackクラスがあります。

import java.util.Stack;

Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println(stack.pop());   // Pop → 3
System.out.println(stack.peek());  // Peek → 2

JavaScript

JavaScriptでも配列をスタックとして使えます。

let stack = [];
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.pop());   // Pop → 3
console.log(stack[stack.length - 1]);  // Peek → 2

C言語

C言語では、構造体で自作する必要があります。

#define MAX_SIZE 100
int stack[MAX_SIZE];
int top = -1;

// Push
void push(int data) {
    if (top < MAX_SIZE - 1) {
        stack[++top] = data;
    }
}

// Pop
int pop() {
    if (top >= 0) {
        return stack[top--];
    }
    return -1;  // エラー
}

スタックの計算量

スタックの基本操作は、どれも O(1)（定数時間） で実行できます。

操作	計算量
Push	O(1)
Pop	O(1)
Peek	O(1)
isEmpty	O(1)

つまり、データ数に関係なく、いつでも同じ速さで操作できるんです。

ただし：

配列の場合：サイズが固定される
連結リストの場合：ポインタ分のメモリを余分に使う

まとめ

スタックは、プログラミングで最も基本的で重要なデータ構造です。

覚えておきたいポイント：

スタック = 後入れ先出し（LIFO）のデータ構造
Push（追加）、Pop（取り出し）、Peek（確認）が基本操作
お皿を積み重ねるイメージ
キュー（FIFO）とは逆の順序
配列または連結リストで実装できる

主な応用例：

ブラウザの「戻る」ボタン
テキストエディタの「元に戻す」機能
関数の呼び出し（コールスタック）
数式の計算
カッコの対応チェック
ゲームの「やり直し」機能

スタックオーバーフロー：

スタックにデータを入れすぎて起こるエラー
無限再帰や深すぎる再帰で発生しやすい

計算量：

すべての基本操作が O(1)（超高速）

スタックは、一見シンプルですが、その応用範囲は驚くほど広いです。

プログラミングを学ぶ上で、スタックの理解は避けて通れません。でも、「最後に入れたものが最初に出る」という基本さえ押さえれば、難しくないんです。

これからプログラミングを学ぶ方も、「あ、これスタックで実装できそう！」と気づけるようになると、グッとレベルアップできますよ。

まずは、ブラウザの「戻る」ボタンを使う時に、「これがスタックか」と思い出してみてください。身近なところにスタックはたくさん隠れているんです。

スタックとは？

後入れ先出しって何？

英語の Stack の意味

スタックの基本操作

1. Push（プッシュ）- データを追加

2. Pop（ポップ）- データを取り出す

3. Peek（ピーク）- 一番上を見る

4. isEmpty（イズエンプティ）- 空かどうか確認

スタックとキューの違い

キューとは？

比較表

スタックの実装方法

1. 配列（Array）を使った実装

2. 連結リスト（Linked List）を使った実装

スタックが使われている場面

1. ブラウザの「戻る」ボタン

2. テキストエディタの「元に戻す（Undo）」機能

3. 関数の呼び出し（コールスタック）

4. 数式の計算（逆ポーランド記法）

5. カッコの対応チェック

6. ゲームでの「やり直し」機能

スタックオーバーフロー

スタックオーバーフローとは？

Q&Aサイトの名前にも

各言語でのスタック実装

Python

Java

JavaScript

C言語

スタックの計算量

まとめ

Youtube

カテゴリー別人気記事

コメント