【C言語入門】線形データ構造「キュー」の基本概念と実装方法をわかりやすく解説

データ構造とは、データを体系的に整理して格納するための仕組みのことです。データ構造は大きく分けて以下の2種類に分類されます。

• 線形データ構造 − データが一列に直線状に並んで格納される構造です。例：配列、構造体、スタック、キュー、連結リストなど。
• 非線形データ構造 − データが階層的・網羅的に格納される構造です。例：木（ツリー）、グラフ、集合、テーブルなど。

キュー（Queue）とは

キューは線形データ構造の一つで、要素の挿入は後端（リア/rear）から行い、削除は前端（フロント/front）から行うという特徴を持っています。

キューではFIFO（First In First Out：先入れ先出し）という順序が採用されており、最初に入れた要素が最初に取り出されます。これは現実世界の行列（待ち行列）と同じ動作イメージです。

主な操作

• 挿入（Insert / Enqueue） − キューに要素を追加します。
• 削除（Delete / Dequeue） − キューから要素を取り除きます。

エラー状態

• オーバーフロー（Queue Overflow） − 満杯のキューに対して要素を挿入しようとしたときに発生する状態。
• アンダーフロー（Queue Underflow） − 空のキューから要素を削除しようとしたときに発生する状態。

各操作のアルゴリズム

挿入（insert）のアルゴリズム

まずキューのオーバーフローをチェックします。

if (r == n)
    printf("Queue overflow");

オーバーフローでなければ、キューに要素を挿入します。

q[r] = item;
r++;

削除（delete）のアルゴリズム

まずキューのアンダーフローをチェックします。

if (f == r)
    printf("Queue under flow");

アンダーフローでなければ、キューから要素を削除します。

item = q[f];
f++;

表示（display）のアルゴリズム

まずキューが空かどうかを確認します。

if (f == r)
    printf("Queue is empty");

空でなければ、「f」から「r」までのすべての要素を出力します。

for (i = f; i < r; i++)
    printf("%d", q[i]);

C言語による実装プログラム

以下は、配列を使ってキューを実装するC言語プログラムの例です。循環バッファの考え方を取り入れ、rearとfrontを剰余演算で管理している点がポイントです。

#include<limits.h>
#include<stdio.h>
#include <stdlib.h>

struct Queue {
    int front, rear, size;
    unsigned capacity;
    int* array;
};

struct Queue* createQueue(unsigned capacity){
    struct Queue* queue = (struct Queue*)malloc(
        sizeof(struct Queue));
    queue->capacity = capacity;
    queue->front = queue->size = 0;
    queue->rear = capacity - 1;
    queue->array = (int*)malloc(
        queue->capacity * sizeof(int));
    return queue;
}

// キューが満杯かどうかを判定
int isFull(struct Queue* queue){
    return (queue->size == queue->capacity);
}

// キューが空かどうかを判定
int isEmpty(struct Queue* queue){
    return (queue->size == 0);
}

void Equeue(struct Queue* queue, int item){
    if (isFull(queue))
        return;
    queue->rear = (queue->rear + 1)
        % queue->capacity;
    queue->array[queue->rear] = item;
    queue->size = queue->size + 1;
    printf("%d entered into queue\n", item);
}

int Dqueue(struct Queue* queue){
    if (isEmpty(queue))
        return INT_MIN;
    int item = queue->array[queue->front];
    queue->front = (queue->front + 1)
        % queue->capacity;
    queue->size = queue->size - 1;
    return item;
}

// キューの先頭要素を取得する関数
int front(struct Queue* queue){
    if (isEmpty(queue))
        return INT_MIN;
    return queue->array[queue->front];
}

// キューの末尾要素を取得する関数
int rear(struct Queue* queue){
    if (isEmpty(queue))
        return INT_MIN;
    return queue->array[queue->rear];
}

int main(){
    struct Queue* queue = createQueue(1000);
    Equeue(queue, 100);
    Equeue(queue, 200);
    Equeue(queue, 300);
    Equeue(queue, 400);
    printf("%d is deleted element from queue\n\n",
        Dqueue(queue));
    printf("1st item in queue is %d\n", front(queue));
    printf("last item in queue %d\n", rear(queue));
    return 0;
}

実行結果

上記のプログラムを実行すると、次のような結果が出力されます。

100 entered into queue
200 entered into queue
300 entered into queue
400 entered into queue
100 is deleted element from queue

1st item in queue is 200
last item in queue 400

この実行結果からも分かるように、最初に挿入した「100」が最初に削除されており、キューがFIFO（先入れ先出し）の規則に従って動作していることが確認できます。