スタックのC++実装：溢れチェック・ASanの指摘・速度の実測

2026年11月改訂： この記事は2021年に韓国語で書いたスタックの講座を、日本語向けに書き直したものです。C++ の例2つを Apple clang 21（-Wall -Wextra、警告0件）でコンパイルし直し、AddressSanitizer と UndefinedBehaviorSanitizer を有効にして動かしました。サンプルの main は2021年と同じ結果を出しますが、クラス自体にはオーバーフローのチェックもアンダーフローのチェックもなく、コピーすると二重解放になり、連結リスト版は全ノードをリークしながら push と pop のたびにリストを端から端までたどっていました。サニタイザーの出力、修正したコード、括弧チェックの例、速度の実測をまとめます。

授業や競技プログラミング、ちょっとしたパーサーのために C/C++ でスタックを自分で書く人と、C# の Stack<T> が何を肩代わりしているのか知りたい人向けの記事です。先に結論を書くと、スタックは後から入れたものが先に出る（LIFO）構造で、事故はほぼ必ず「満杯なのに push」と「空なのに pop」の2か所で起きます。チェックを2行入れた配列スタックが今回測った中で最速で、連結スタックは約50倍遅く、上限がないときにだけ選ぶ理由があります。

スタックとは、どこで使われるか

食堂のトレイ置き場を思い浮かべてください。トレイは上に重ねて置き、取るときも一番上から取ります。入れる操作を push、取り出す操作を pop、取り出さずに一番上を見るだけの操作を peek（2021年のコードでは getTop）と呼びます。片端しか触らないので、まともに作れば push も pop も O(1) です。

実務でスタックに出会う場所：

• すべてのプログラムのコールスタック（再帰が深すぎると起きる「スタックオーバーフロー」。ソートの記事のクイックソートがまさにこれで落ちました）
• エディタの元に戻す（Undo）の履歴
• コンパイラの括弧チェックや式の構文解析
• 深さ優先探索（DFS）をループで書くときの明示的なスタック

2021年の配列スタックを AddressSanitizer で動かす

2021年の最初の例は、new T[maxSize] で配列を確保し、top に要素数を持つテンプレートクラスでした。断片コードには #include <iostream> と using namespace std; だけが抜けていたので、その2行を足すと、元の main（a〜e を push して5回 pop）は clang++ -std=c++17 -Wall -Wextra で警告なしにコンパイルでき、2021年と同じ e, d, c, b, a の順で出力しました。

問題はこの正常系の外側です。push は stack[top++] = data;、pop は return stack[--top]; だけで、isFull は「まだ使わない」としてコメントアウトされていました。誤った使い方を3つ用意し、通常ビルドと -fsanitize=address,undefined -g ビルドの両方で実行しました。

本当に怖いのは上の2行です。サニタイザーなしでは何も起きていないように見えます。 確保した領域の1バイト後ろに書き、1バイト前を読み、そのまま実行が続きます。3行目は「3の規則（rule of three）」の問題で、生ポインタを所有しているのにコピーコンストラクタはコンパイラ生成のままなので、2つのオブジェクトが同じ配列を delete[] します。

修正した配列スタック

チェックを2つ入れ、失敗は戻り値で知らせ、コピーを禁止しました。空のスタックの peek は返す値がないので例外にします。

template <class T>
class ArrayStack {
    T* data_; int top_ = 0; int cap_;
public:
    explicit ArrayStack(int cap) : data_(new T[cap]), cap_(cap) {}
    ~ArrayStack() { delete[] data_; }
    ArrayStack(const ArrayStack&) = delete;             // コピー禁止 → 二重解放なし
    ArrayStack& operator=(const ArrayStack&) = delete;
    bool push(const T& v) {                              // オーバーフロー：書かずに知らせる
        if (top_ == cap_) return false;
        data_[top_++] = v; return true;
    }
    bool pop(T& out) {                                   // アンダーフロー：読まずに知らせる
        if (top_ == 0) return false;
        out = data_[--top_]; return true;
    }
    const T& peek() const {
        if (top_ == 0) throw std::out_of_range("peek on empty stack");
        return data_[top_ - 1];
    }
    bool empty() const { return top_ == 0; }
    bool full()  const { return top_ == cap_; }
};

容量5のスタックに a〜f を入れてから全部取り出した結果です。

push('f') rejected: stack full
e d c b a
pop on empty -> false

同じテストを ASan/UBSan ビルドで動かしても報告は出ません。満杯のとき false を返すか、例外を投げるか、配列を広げるかは設計次第ですが、「それでも書く」という選択肢だけはありません。

応用：括弧の対応チェック

スタックの定番の使い道は、(・[・{ が正しい順に閉じているかの確認です。開き括弧ではその位置を push し、閉じ括弧では pop して種類を比べます。取り出すものがない、種類が違う、最後に残っている、のどれかならエラーです。位置を積んでおけば、どこが悪いかも示せます。

long check_brackets(std::string_view s) {      // 対応が取れていれば -1、だめなら問題の位置
    ArrayStack<long> st(static_cast<int>(s.size()) + 1);
    for (long i = 0; i < (long)s.size(); i++) {
        char c = s[i];
        if (c == '(' || c == '[' || c == '{') { st.push(i); continue; }
        if (c != ')' && c != ']' && c != '}') continue;
        long open;
        if (!st.pop(open)) return i;                      // 開き括弧なしで閉じた
        char o = s[open];
        if ((c == ')' && o != '(') || (c == ']' && o != '[') || (c == '}' && o != '{'))
            return i;                                     // 種類が違う
    }
    long open;
    return st.pop(open) ? open : -1;                      // 閉じていない括弧
}

if (a[i] == f(b)) { x(); }   OK
f(a[1)]                      error at index 5 (')')
while (x) { y(               error at index 13 ('(')
a + b) * c                   error at index 5 (')')
{[()()]}                     OK

3つ目の入力では { と ( の両方が閉じていませんが、最後にスタックの一番上に残っているいちばん内側の ( の位置を指します。スタックの大きさを入力の長さにしているので、ここでオーバーフローは起こりえません。

2021年の連結リストのスタック：リーク、クラッシュ、操作ごとに O(n)

2021年の2つ目の例は、std::string を持つノードでスタックを作っていました。一番下のノード（list）と一番上のノード（top）を持ち、新しいノードをリストの末尾につなぐ作りです。測ってみると問題は3つありました。

ノードがすべてリークします。 pop() は一番上のノードを外してポインタを返すだけで、誰も delete せず、クラスにデストラクタもありません。Apple Silicon の macOS では ASan のリーク検出が使えない（detect_leaks is not supported on this platform）ため、システムの leaks コマンドで確認しました。

$ leaks --atExit -- ./linked_stack_2021
Process 63361: 6 leaks for 288 total leaked bytes.
STACK OF 1 INSTANCE OF 'ROOT LEAK: <malloc in Stack::push(std::basic_string<char>)>'

push 6回でリーク6件です。

空のスタックで pop すると呼び出し側が落ちます。 pop() は「スタックが空です」と表示したあと、NULL の top をそのまま返し、サンプルコードは受け取ってすぐ ->data を読みます。2021年の main の最後に pop() を1回足すと、メッセージを出したあと終了コード139（セグメンテーション違反）で終わりました。ASan の出力：

ERROR: AddressSanitizer: SEGV on unknown address 0x000000000017
    #3 ... in std::operator<<(..., const std::string&) basic_ostream.h:577

push と pop のたびにリストをたどります。 push は一番下から末尾まで、pop は一番上の1つ下を探すためにまた先頭から回ります。1回の操作が O(n) なので、N 回で O(N²) です。2021年の記事は「挿入と削除が複雑になって時間がかかる」と書いていましたが、原因は連結リストそのものではなく末尾につなぐ設計です。N 個 push してから N 個 pop（-O2）：

新しいノードを先頭（head）にすれば解決します。push は head = new Node{v, head};、pop は head を取り出して head->next に進めてから delete。どちらも O(1) で、デストラクタで空になるまで pop すればリークもありません。ノードのつなぎ方そのものは連結リストの記事で扱っています。

実測：配列・連結・std::stack・C# Stack

すべての実装に同じ仕事をさせました。int を1,000万回 push してから1,000万回 pop。C++ は Apple clang 21 -O2、C# は .NET 10.0.14 の Release、Apple M1 Pro で3回実行です。

C++ の1回目が遅いのは、新しいメモリに初めて触れるときのページフォールトのためです。連結スタックは要素ごとに new と delete を1回ずつ行い、ヒープのあちこちを触りますが、配列は連続したアドレスに書きます。std::stack<int> はアダプターにすぎず、vector を指定すれば今回の配列スタック（＋自動拡張）のように、既定の deque ならブロック単位の確保で動きます。

C# ではこう書きます（.NET 10 で実行確認）。

var s = new Stack<char>();
foreach (var c in "abcde") s.Push(c);
while (s.TryPop(out var c)) Console.Write($"{c} ");     // e d c b a
Console.WriteLine(s.TryPop(out _));                       // False
s.Pop();   // InvalidOperationException: Stack empty.

Stack<T> は内部配列を自動で広げるので、オーバーフローの心配はありません。残るのはアンダーフローで、空が普通に起こる処理なら TryPop / TryPeek を使います。

どれを使うか

同じ「満杯か空か」の問題は、キューになるともっと厄介になります。続きは循環キューと連結キューで。

テスト環境：Apple clang 21.0.0（-std=c++17/20 -Wall -Wextra、-fsanitize=address,undefined -g）、macOS の leaks、.NET SDK 10.0.403 / ランタイム 10.0.14、Apple M1 Pro。