連結キューのC++実装：ノードのリーク、空キューのdequeue、速度実測

2026年11月改訂： この記事は2021年に韓国語で書いた連結キューの講座を、日本語向けに書き直したものです。例を Apple clang 21（-Wall -Wextra、警告0件）でコンパイルし直すと、出力は当時と同じ 80, 90, 89 でした。しかしプログラムはdequeue したノードを1つも解放しておらず（macOS の leaks で5件）、空のキューで dequeue するとヌルポインタを参照して UBSan と ASan の両方に捕まりました。その出力、ノードを自分で管理するよう直したクラス、リングバッファ・std::queue・C# Queue<T> との速度比較をまとめます。

課題や面接、ジョブの待ち行列のために連結ノードでキューを自作する人と、C# の Queue<T> と何が違うのか知りたい人向けの記事です。キューは先に入ったものが先に出る（FIFO）構造で、後ろ（rear）に入れて前（front）から取り出します。連結版は容量の上限がなく、どちらの操作も O(1) ですが、「ノードを誰が解放するか」と「front がないのに触る」の2つのミスが起きやすく、測ってみると配列のリングバッファより約16倍遅くなりました。

連結キューのしくみ

駅の券売機の行列を思い浮かべてください。新しく来た人は最後尾に並び、先頭の人から抜けていきます。連結キューはポインタを2つ持ちます。

• front：次に取り出すノード
• rear：最後のノード。これがあるので enqueue のたびにリストをたどらずに済みます。

enqueue はノードを作って rear の後ろにつなぎ、rear を新しいノードに移します。dequeue は front を取り出し、front を次のノードに進めます。最後のノードが抜けるときは rear も空にしないと、解放済みのメモリを指したままになります。循環キューと違って「満杯」がなく、メモリが許す限り伸びます。ノードと next ポインタそのものは連結リストの記事で扱っています。

2021年のコードを動かす：出力は正しく、ノードはリーク

2021年のクラスには、enqueue、Node* を返す dequeue、isEmpty、getSize、そして空になるまで dequeue して delete するデストラクタがありました。サンプルの main はこうです。

lq.enqueue(50); lq.enqueue(60); lq.dequeue();
lq.enqueue(80); lq.enqueue(90); lq.dequeue();
lq.enqueue(89);
size = lq.getSize();
for (int i = 0; i < size; i++)
    cout << "dequeued: " << lq.dequeue()->data << endl;

clang 21 での出力は2021年と同じ値です。

dequeued: 80
dequeued: 90
dequeued: 89

デストラクタがあるので安全そうに見えますが、解放するのはまだキューに残っているノードだけです。dequeue() が返したノードは呼び出し側の責任になり、main はそれを全部捨てていました。戻り値を無視した lq.dequeue(); が2回、値だけ読んでポインタを失う lq.dequeue()->data が3回です。デストラクタが走る時点でキューは空なので、何も解放しません。

Apple Silicon の macOS では AddressSanitizer のリーク検出が使えない（detect_leaks is not supported on this platform）ため、ASan の実行は何事もなく終わり、何も教えてくれませんでした。システムの leaks コマンドは教えてくれます。

$ leaks --atExit -- ./linked_queue_2021
Process 64094: 5 leaks for 160 total leaked bytes.
    5 (160 bytes) ROOT LEAK: <malloc in LinkedQueue::enqueue(int)> [32]

5個入れて、5個取り出して、5個リークしています。所有権付きの生ポインタを返す設計の落とし穴で、Node* dequeue() というシグネチャのどこにも「これは呼び出し側が delete すること」とは書いてありません。

空のキューで dequeue

2021年の dequeue はこう始まります。

Node* temp = front;
if (front->nextNode == NULL)   // 「ノードは1つ以下」

コメントは「1つ以下」と言っていますが、0個なら front は NULL で、最初の判定でいきなり参照します。ループのあとに dequeue() をもう1回足しました。

通常ビルド:  終了コード139（セグメンテーション違反）

UBSan:  lq_2021.cpp:22:20: runtime error: member access within null pointer of type 'Node'
ASan:   ERROR: AddressSanitizer: SEGV on unknown address 0x000000000008
            #0 in LinkedQueue::dequeue() lq_2021.cpp:22
            #1 in main lq_2021.cpp:41

アドレス 0x8 は Node の中での nextNode のオフセットです（4バイトの int と4バイトのパディングの次）。2021年のデストラクタが安全だったのは毎回 isEmpty() を先に確かめていたからで、ほかの呼び出し元もすべて同じことを覚えておく必要がある作りでした。

修正した連結キュー

2つの責任をクラスの中に移しました。dequeue が空を確かめ、値をコピーして返し、空になったら rear も戻し、ノードを自分で delete します。2つのキューが同じノードを共有しないよう、コピーも禁止しました。

class LinkedQueue {
    struct Node { int data; Node* next; };
    Node* front_ = nullptr; Node* rear_ = nullptr; int size_ = 0;
public:
    LinkedQueue() = default;
    ~LinkedQueue() { int v; while (dequeue(v)) {} }          // 残っているノードをすべて解放
    LinkedQueue(const LinkedQueue&) = delete;
    LinkedQueue& operator=(const LinkedQueue&) = delete;
    void enqueue(int v) {
        Node* n = new Node{v, nullptr};
        if (rear_) rear_->next = n; else front_ = n;
        rear_ = n; ++size_;
    }
    bool dequeue(int& out) {                                 // 空のキュー → false
        if (!front_) return false;
        Node* n = front_;
        out = n->data;
        front_ = n->next;
        if (!front_) rear_ = nullptr;
        delete n;                                            // ノードはキューが持ち、キューが解放
        --size_; return true;
    }
    bool empty() const { return front_ == nullptr; }
    int size() const { return size_; }
};

同じ順番で出し入れし、空のキューでもう1回 dequeue し、デストラクタに仕事が残るようわざと2個入れたまま終了しました。

dequeued: 80
dequeued: 90
dequeued: 89
dequeue on empty -> false

ASan/UBSan: 報告なし
leaks:      Process 64434: 0 leaks for 0 total leaked bytes.

int ではなくオブジェクトを入れるなら、std::optional<T> dequeue() で同じ考え方を続けるか、リンクを std::unique_ptr<Node> にして所有権を型で強制する方法もあります。

標準ライブラリ：std::queue と C# Queue

std::queue<T> は既定で std::deque<T> の上にかぶせたアダプターです。空の std::queue で front() や pop() を呼ぶのは未定義動作なので、今回のクラスと同じく先に empty() を確かめます。

C# の Queue<T> は伸長する循環配列で、空での dequeue は例外で知らせます。.NET 10 で確認しました。

var q = new Queue<int>([50, 60]);
q.Dequeue(); q.Enqueue(80); q.Enqueue(90); q.Dequeue(); q.Enqueue(89);
while (q.TryDequeue(out var v)) Console.Write($"{v} ");   // 80 90 89
Console.WriteLine(q.TryDequeue(out _));                     // False
q.Dequeue();   // InvalidOperationException: Queue empty.

ガベージコレクタのおかげでリークの問題は丸ごと消えます。マネージド言語で得られるいちばん大きな利点がこれで、空の扱いには引き続き TryDequeue か Count の確認が要ります。

実測：連結・リングバッファ・std::queue・C

int で2種類の作業を3回ずつ。C++ は Apple clang 21 -O2、C# は .NET 10.0.14 Release、Apple M1 Pro です。

• 詰めて空にする： 1,000万回 enqueue してから1,000万回 dequeue
• 定常状態： 1,000個入った状態で enqueue+dequeue の組を1,000万回（大きくならないジョブキュー）

2021年の記事の結論「連結キューは実装が簡単、循環キューは高性能」は数字でも正しく、詰めて空にする作業で約16倍、定常状態で約20倍の差でした。定常状態のリングバッファは同じ4KBのメモリを使い回しますが、連結キューは相変わらず要素ごとに new と delete を呼びます。双方向の std::list はノードごとにポインタが2つあるのでさらに遅くなります。C# は JIT のウォームアップを除くため、4回のうち最初の1回を捨てた値です。

それでも連結キューが合う場面

同じ所有権の問題はスタックの記事にも出てきます。2021年の連結スタックも、同じ理由でノード6個をすべてリークしていました。

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