C/C++のデータ構造

C・C++の循環キュー（circular queue）

このレッスンでは、Cの循環配列とC++のstd::queueで、先入れ先出しのキューを実装します。

はじめに

キュー（queue）は先入れ先出し（FIFO）のルールで動きます。普通の配列で実装すると、要素を取り出すたびに残りの要素を前に詰めなければなりません。循環キュー（circular buffer）は、インデックスを先頭に戻して空いた位置を再利用することで、この問題を解決します。

大切なポイント

操作を書く前に、データ構造で常に成り立つべき条件（不変条件、invariant）を決めましょう。
空のとき、満杯のとき、メモリ確保に失敗したときもきちんと処理しましょう。
各操作の計算量とメモリ管理を、あわせて評価しましょう。

動きで理解する

enqueueとdequeueを試すと、要素が到着した順番どおりに出ていくことがわかります。

CとC++のコード例

実行 →

main.c

#include <stdio.h>

typedef struct {
    int data[4];
    int head;
    int size;
} Queue;

int push(Queue *queue, int value) {
    if (queue->size == 4) return 0;
    int tail = (queue->head + queue->size) % 4;
    queue->data[tail] = value;
    ++queue->size;
    return 1;
}

int pop(Queue *queue, int *value) {
    if (queue->size == 0) return 0;
    *value = queue->data[queue->head];
    queue->head = (queue->head + 1) % 4;
    --queue->size;
    return 1;
}

int main(void) {
    Queue queue = {{0}, 0, 0};
    int value;
    push(&queue, 7);
    push(&queue, 9);
    pop(&queue, &value);
    printf("%d\n", value);
}

実行結果

C++

実行 →

main.cpp

#include <iostream>
#include <queue>

int main() {
    std::queue<int> values;
    values.push(7);
    values.push(9);
    std::cout << values.front() << '\n';
    values.pop();
}

実行結果

CとC++の比較

Cのキューは先頭の位置headと要素数sizeを保存します。新しい要素の位置は余りの計算(head + size) % 4で求めるので、配列の末尾に達するとインデックスは自動で先頭に戻ります。C++のstd::queueはコンテナアダプター（container adapter）で、front、push、popの操作が最初から用意されています。

データ（struct）と操作は分かれていて、メモリは手作業で確保・解放します。

C++

クラスとコンテナが、データの正しさを守り、リソースを自分で管理します。

発展問題

両方のバージョンを実行し、コードを書き換えて、それぞれの言語がもたらす安全性の違いを観察しましょう。

空の状態と、容量の上限に達したときのテストを追加しましょう。
メモリを解放する処理を書き、メモリリークがないか確認しましょう。
標準ライブラリの対応するコンテナと計算量を比べましょう。

チャレンジで練習する

このレッスンの内容を使って実際の問題を解きましょう。各チャレンジはブラウザで動き、すぐにテストされ、AI のレビューも受けられます。

Course Schedule Order Order courses so every prerequisite comes first. 難しい

すべてのチャレンジ