【C言語】キューのポインタでの実装方法

キューのポインタでの実装方法解説ページアイキャッチ

SHARE

このページにはプロモーションが含まれています

このページでは「キュー」を “ポインタを用いて” 実装する方法について解説していきたいと思います。

キューがどのようなものであり、キューの配列での実装方法は下記ページで解説しています。もし、これらをご存知ない方は、まず下記ページを読んでいただけると、以降の解説が理解しやすくなると思います！

スタックとキューの配列での実装方法解説ページアイキャッチ 【C言語/データ構造】スタックとキューの配列での実装方法

ポインタで実装するので、ポインタの理解も必要です。また、構造体も利用するため構造体の理解も必要です。そのほかにも malloc 関数や NULL の知識も必要です。

本ページでもこれらに関して極力解説するようにはしていますが、キューをポインタで実装するにあたって必要になる知識の解説ページへのリンクを下に貼っておくので、必要に応じてご参照していただければと思います。

ポインタの解説ページアイキャッチ 【C言語】ポインタを初心者向けに分かりやすく解説 構造体解説ページのアイキャッチ 【C言語】構造体について初心者向けに分かりやすく解説 malloc解説ページのアイキャッチ 【C言語】malloc関数（メモリの動的確保）について分かりやすく解説 NULLの解説ページアイキャッチ 【C言語】「NULL」の意味とNULLを用いた「安全なポインタの使い方」

キューのポインタでの実装方法

では、キューを “ポインタを用いて” 実装する方法について解説していきたいと思います。

前述の通り、キューを配列で実装する方法は下記ページで解説しています。

スタックとキューの配列での実装方法解説ページアイキャッチ 【C言語/データ構造】スタックとキューの配列での実装方法

ポイントだけ抜粋すると、キューを実装するためのポイントは下記の４つになります。

  • データの先頭を管理する
  • データの最後尾を管理する
  • データの追加時にはデータの最後尾の１つ後ろにデータを格納する
  • データの取り出し時にはデータの先頭からデータを取得する

要は、これらのポイントを、配列を使わずに “ポインタで” 実現していきます。

データの格納先のメモリを用意する

まず、配列を使わないので、配列に代わるデータの格納先が必要になります。

このデータの格納先は malloc 関数で確保したメモリとしたいと思います。

malloc 関数は下記ページで解説していますが、要はプログラム内で利用するメモリを追加で取得する関数です。

malloc解説ページのアイキャッチ 【C言語】malloc関数（メモリの動的確保）について分かりやすく解説

引数に取得したいメモリのサイズをバイト単位で指定して実行すると、そのサイズのメモリが確保され、そのメモリの先頭アドレスを戻り値として取得することができます。

malloc関数のイメージ図

データの追加時には、その都度、データを格納する用のメモリを malloc で取得し、取得したメモリにそのデータを格納していくようにします。

mallocで取得したメモリにデータを格納する様子

スポンサーリンク

各メモリをポインタで繋ぐ

で、キューを実装しようと思うと、どのデータがどの順番で追加されたのかが分からないといけません。

配列の場合は、この順番は配列の添字から確認できましたね！

ただし、単に malloc したメモリはそれぞれで独立しており、このままだと、どのデータがどの順番で追加されたのかが分からないのでキューを実現することができません…。

mallocしたメモリが独立で存在している様子

なので、malloc したメモリには単にデータを格納するだけでなく、”次に追加されたデータが格納されたメモリ” を指すためのアドレスも格納するようにします。

これを実現するために、例えば下記のような NODE_T 構造体を定義します。

NODE_T構造体 
typedef struct NODE {
    /* 追加されたデータそのものを格納する変数 */
    int data;
    /* 次のノードを指すポインタ */
    struct NODE *next;
} NODE_T;

data が “追加されたデータそのもの” を格納するためのメンバで、next が “次に追加されたデータが格納されたメモリ のアドレス” を格納するためのメンバ（つまりポインタ）になります。

NODE_T構造体のメンバ

そして、malloc でメモリを取得するときには、上記の NODE_T 構造体のサイズ分のメモリを取得するようにし、さらにこのメモリのアドレスを NODE_T*でキャストします。

NODE_T構造体のmalloc 
node = (NODE_T*)malloc(sizeof(NODE_T));

これにより取得したメモリを NODE_T 構造体として扱うことができます。例えば data メンバに 100 を格納する場合は、下記のようにアロー演算子を用いて data メンバにアクセスします。

データの格納 
node->data = 100;

アロー演算子について詳しく知りたい方は、下記ページで解説していますのでこちらをご参照いただければと思います。

C言語のアロー演算子（->）を分かりやすく、そして深く解説

今後は、malloc によって取得したメモリ（NODE_T 構造体）をノードと呼びます。つまり、ノードは「データそのもの」と次のノードを指す「ポインタ」から構成されるデータです。

この next で次に追加されたノードを指すようにすることで、どのデータがどの順番で追加されたかを把握することができるようになります。

nextで各ノードに繋がりを持たせた様子

上の図では、next が次のノードを指している様子を矢印で表現しています。ポインタとは下記ページで解説している通り、矢印です。

ポインタの解説ページアイキャッチ 【C言語】ポインタを初心者向けに分かりやすく解説

例えばあるノードから次のノードを辿る処理は、下記のように next を利用することで実現することができます。

次のノードを辿る 
/* nodeはノード構造体を指すポインタ */
nextNode = node->next;

キューの先頭と最後尾をポインタで指す

ここまでの内容により、キューに追加したデータの格納先が用意でき、さらに各データの追加された順番も把握できるようになりました。

次はいよいよキューへの「データの追加」と「データの取り出し」を実装していきます。

で、下記ページで解説しているように、キューへの「データの追加」と「データの取り出し」を行うためには、「データの最後尾」と「データの先頭」がどこであるかを管理しておく必要があります。

スタックとキューの配列での実装方法解説ページアイキャッチ 【C言語/データ構造】スタックとキューの配列での実装方法

ポインタでキューを実装する際も同じで、これらの２つの位置を管理していく必要があります。

そのために、２つのポインタを導入し、１つ目のポインタでは「先頭のノード」、２つ目のポインタでは「最後尾のノード」を指させるようにします。

ここではこの１つ目のポインタの変数名を head、２つ目のポインタの変数を tail としたいと思います。

データの先頭とデータの最後尾を指すポインタの説明図

つまり、データの追加時には、tail が指しているノードの１つ後ろにノードを追加することになります。そして、tail には新しく追加したノードを指させるようにします。

また、データの取り出し時には、head が指しているノードの「データそのもの」を取得して返却します。そして、head が指しているノードの１つ後ろのノードを head に指させるようにします。

データの追加やデータの取り出し時に、データの先頭とデータの最後尾を head と tail でしっかり管理しておくところが、ポインタでキューを実現するときのポイントになります。

また、malloc したメモリは free で解放する必要がありますので、データの取り出し時に不要になったノードをしっかり free するところもポイントです。

それでは、このデータの追加とデータの取り出しの処理の詳細を、ここから解説していきたいと思います。

データの追加

データの追加は下記の２つの場合で処理が異なるので、この２つの場合それぞれの処理について解説していきたいと思います。

  • キューが空でない場合
  • キューが空の場合

キューが空でない場合のデータの追加

まずデータの追加を行う際には、データの新たな格納先が必要になります。

この格納先は前述の通り、malloc により用意します。

ですので、下記のように malloc を実行してノードを追加し、追加したノードの data メンバにデータそのものを格納します（malloc の戻り値 node には、追加したノードの先頭アドレスが格納されます）。

ノードの追加とデータの格納 
node = (NODE_T*)malloc(sizeof(NODE_T));

/* inputは追加するデータ */
node->data = input;

ただし、このままの状態だとノードは独立した状態で、どのタイミングで追加されたのか分かりません。

追加したノードが独立している様子

そのため、今までの最後尾のノード（つまり tail が指しているノード）の next で、追加したノード（node）を指させるようにします。

追加したノードをnextで指す様子

これにより、新しく追加したノード（node）が 、tail が指しているノードの “次に追加されたノード” であることが分かるようになります。

また、このノードの追加により最後尾ノードの位置も変わりますので、これに合わせて tail の指す先も変更します。

具体的には、tail には追加したノードを指させるようにします。追加したノードのアドレスは malloc 関数の戻り値 node となりますので、tail = node を行えば良いことになります。

データの最後尾の再設定を行う様子

まとめると、キューが空でない場合のデータの追加時には下記の４つの処理を行うことになります。

  1. malloc でノードを追加
  2. 追加したノードにデータを格納
  3. tail が指すノードの next に追加したノードを指させる
  4. tail に追加したノードを指させるキューが空でない状態でのデータの追加の流れ

キューが空の場合のデータの追加

続いてキューが空の状態でのデータの追加について説明します。キューが空とは、要は head も tail も NULL を指している場合になります。

キューが空の時のheadとtailの状態

で、この場合も malloc してノードを追加し、その data にデータそのものを格納することになるのですが、キューが空の状態なので、tail が指すノードは存在しません。

ですので、「キューが空でない場合のデータの追加」とは異なった処理を行う必要があります。

ただし、処理自体は簡単で、head と tail 両方に、malloc で追加したノードを指させてやれば良いだけです。

空のキューにデータを追加した後のheadとtailの状態

つまり、「キューが空の場合」にデータを追加した場合、その追加したデータを格納するノードが「先頭ノード」であり、さらに「最後尾ノード」になります。

まとめると、キューが空の場合のデータの追加時には下記の４つの処理を行う必要があります。

  1. malloc でノードを追加
  2. 追加したノードにデータを格納
  3. head に追加したノードを指させる
  4. tail に追加したノードを指させるキューが空の状態でデータを追加する時の処理の流れ

スポンサーリンク

データの取り出し

データの取り出しは下記の２つの場合で処理が異なるので、この２つの場合それぞれの処理について解説していきたいと思います。

  • 取り出してもキューが空にならない場合
  • 取り出すとキューが空になる場合

取り出してもキューが空にならない場合のデータの取り出し

まず、データの取得先は先頭のノードに格納されているデータ、つまり head が指しているノードに格納されているデータ（data メンバ）です。

キューの先頭からデータを取得する様子

さらに、データの取り出しによってノードの先頭の位置が変わります。具体的には、ノードの先頭は head が指しているノードの “次のノード”（next が指しているノード）になりますので、head に next を指させます。

データ取り出し後にheadを再設定する様子

以上によりデータの取り出し自体は完了するのですが、データの取り出し先のノードはキューから不要なデータになりましたので、free 関数で解放してやる必要があります。

MEMO

malloc で取得したメモリは、不要になった際に free しないとメモリリークになります

メモリリークが大量に発生すると、簡単に言うと、メモリが不足してプログラムが正常に動作できなくなります

free 関数の引数に指定するのは不要になったメモリのアドレスになります。この場合は、「データの取り出し先のノード」のアドレスです。つまり元々の head ですね。

ただし、free を行う前に head に next を指させてしまうと（head に next の値を代入してしまうと）、free を行うアドレスが分からなくなってしまいます。

freeすべきアドレスが分からなくなってしまう様子

そのため、head に next を指させる前に、まず head が指しているノード（データの取り出しを行う前の先頭ノード）のアドレスを他のポインタに退避しておくようにします。

freeすべきアドレスを退避しておく様子

そして、head が next を指した後に、その退避しておいたアドレスのノードを free するようにします。

退避しておいたアドレスのメモリを解放する様子

これで、不要になったノードを free 関数で解放することができます。

まとめると、取り出してもキューが空にならない場合のデータの取り出し時には、下記の４つの処理を行うことになります。

  1. head の指すノードからデータ取得
  2. head のアドレスを他のポインタに退避
  3. head に、head が指すノードの次のノードを指させる
  4. 他のポインタに退避しておいた元々の head のアドレスのノードを free する取り出してもキューが空にならない場合のデータ取り出し時の処理の流れ

取り出すとキューが空になる場合のデータの取り出し

最後に、データの取り出しを行うとキューが空になる場合のデータの取り出しを行う場合の処理について解説します。

「データの取り出しを行うとキューが空になる場合」とは、要は head と tail の指す先が同じノードである場合です（head == tail）。

取り出すとキューが空になるときのtailとheadの状態

この場合もデータの取得先は head が指すノードの data メンバになります。

取り出すとキューが空になる場合のデータの取り出し先

また、データを取り出して不要になったノードを free するところも同じです。free するノードは head が指すノードになります。

取り出すとキューが空になる場合の解放すべきノード

ただし、データを取り出すことでキューが空になるので、head や tail が指すノードは存在しません。ですので、単に head と tail には NULL を指させます。

取り出すとキューが空になる場合のデータ取り出し後のheadとtailの状態

「取り出してもキューが空にならない場合のデータの取り出し」とは異なり、head が指す先は NULL 固定ですので、他のポインタにアドレスを退避しておくような処理は不要になります。

まとめると、「取り出しを行うとキューが空になる場合」のデータの取り出し時には、下記の４つの処理を行うことになります。

  1. head の指すノードからデータ取得
  2. head の指すノードを free
  3. head に NULL を指させる
  4. tail に NULL を指させる取り出すとキューが空になる場合のデータの取り出し時の処理の流れ

キューをポインタで実装したソースコード

最後に、ここまでの解説を踏まえた「キューをポインタで実装したソースコード」を紹介しておきます。

キュー（ポインタ） 
#include <stdio.h>
#include <stdlib.h>


/* ノード構造体 */
typedef struct NODE {
    /* 追加されたデータそのものを格納する変数 */
    int data;
    /* 次のノードを指すポインタ */
    struct NODE *next;
} NODE_T;

/* キューの情報を構造体 */
typedef struct QUEUE {
    /* キューの先頭を指すポインタ */
    NODE_T *head;
    /* キューの最後尾を指すポインタ */
    NODE_T *tail;
} QUEUE_T;

void initQueue(QUEUE_T*);
void finishQueue(QUEUE_T*);
void printQueue(QUEUE_T*);
void enqueue(QUEUE_T*, int);
int deqeueue(QUEUE_T*);

/* キューを初期化する関数 */
void initQueue(QUEUE_T *queue){

    queue->head = NULL;
    queue->tail = NULL;
}

/* キューの終了処理をする関数 */
void finishQueue(QUEUE_T *queue){
    NODE_T *p, *next;

    /* キュー内の全ノードをfree */
    p = queue->head;
    while(p != NULL){
        next = p->next;
        free(p);
        p = next;
    }
}

/* エンキューする関数 */
void enqueue(QUEUE_T *queue, int input){

    NODE_T *node;

    /* mallocでノードを追加 */
    node = (NODE_T*)malloc(sizeof(NODE_T));

    /* メモリが足りなければ何もせず関数終了 */
    if(node == NULL){
        printf("メモリが取得ないためエンキューできません\n");
        return ;
    }

    /* 追加したノードデータを格納 */
    node->data = input;

    /* 次のノードはないのでNULLを設定 */
    node->next = NULL;

    if(queue->head == NULL && queue->tail == NULL){
        /* キューが空の場合 */
        
        /* headに追加したノードを指させる */
        queue->head = node;

        /* tailに追加したノードを指させる */
        queue->tail = node;

        return ;
    }

    /* 空でない場合はキューの最後尾にnodeを追加 */

    /* tailが指すノードのnextに追加したノードを指させる */
    queue->tail->next = node;

    /* tailに追加したノードを指させる */
    queue->tail = node;
}

/* デキューする関数 */
int dequeue(QUEUE_T *queue){
    int ret = 0;
    NODE_T *oldHead;

    /* キューが空なら何もせずに関数終了 */
    if(queue->head == NULL){
        printf("キューが空です\n");
        return -1;
    }

    /* headの指すノードからデータを取得 */
    ret = queue->head->data;

    if (queue->head == queue->tail) {
        /* 取り出すとキューが空になる場合 */

        /* headの指すノードをfree */
        free(queue->head);

        /* headとtailにNULLを指させる */
        queue->head = NULL;
        queue->tail = NULL;

        return ret;
    }

    /* 取り出してもキューが空にならない場合 */

    /* headのアドレスをoldHeadに退避 */
    oldHead = queue->head;

    /* headに、headが指すノードの次のノードを指させる */
    queue->head = queue->head->next;

    /* デキューしたノード（元々のhead）を解放 */
    free(oldHead);

    return ret;
}

/* キューの中身を表示 */
void printQueue(QUEUE_T *queue){
    NODE_T *p;

    p = queue->head;
    while(p != NULL){
        printf("%d,", p->data);
        p = p->next;
    }
    printf("\n");
}

int main(void){

    int m;
    int input;
    int output;
    QUEUE_T queue;

    /* キューを初期化 */
    initQueue(&queue);

    while(1){
        /* ユーザからメニューを選んでもらう */
        printf("メニュー\n 1:エンキュー\n 2:デキュー\n 3:キュー表示\n それ以外:終了\n");
        scanf("%d", &m);

        /* 選ばれたメニューに応じて処理を分岐 */
        if(m == 1){
            printf("エンキューする数は？（0以上の整数のみ可）");
            scanf("%d", &input);
            if(input < 0){
                printf("負の数は受け付けていません\n");
                continue;
            }
            printf("%dをエンキューします\n", input);
            enqueue(&queue, input);
        }else if(m == 2){
            printf("デキューします\n");
            output = dequeue(&queue);
            if(output != -1){
                printf("%dをデキューしました\n", output);
            }
        } else if(m == 3){
            printf("キューの中身を表示します\n");
            printQueue(&queue);
        } else {
            /* 1, 2, 3以外の場合はwhile文を抜け出すためにbreakを実行 */
            printf("終了します\n");
            break;
        }
    }

    /* 最後にキューのノードを全て解放 */
    finishQueue(&queue);

    return 0;
}

データの先頭を指す head とデータの最後尾を指す tail は下記の QUEUE_T 構造体にまとめています。

QUEUE_T構造体 
/* キューの情報を構造体 */
typedef struct QUEUE {
    /* キューの先頭を指すポインタ */
    NODE_T *head;
    /* キューの最後尾を指すポインタ */
    NODE_T *tail;
} QUEUE_T;

キューを扱う関数では、上記の QUEUE_T 構造体（のアドレス）を受け取り、この構造体の head と tail を用いて処理を行うようにしています。

キューの実装でのポイントとなる「データの追加」と「データの取り出し」は、それぞれ enqueue 関数と dequeue 関数で行なっています。

これらはキューのポインタでの実装方法で解説した内容をほぼそのままプログラミングしているだけなので、解説内容と見比べながらソースコードを読んでいただければ何をやっているかは理解していただけると思います。

また、メモリリークが発生しないように、プログラム終了時には finishQueue 関数で、キュー内の全てのノードのメモリを解放するようにしています。

まとめ

このページでは、キューをポインタで実装する方法の解説と、実際にキューをポインタで実装したソースコードの紹介を行いました。

キューをポインタで実装する時のポイントは下記の３つだと思います

  • データの格納先のメモリを malloc で取得する
  • データの最後尾とデータの先頭をしっかり管理する
  • malloc したメモリを不要になった時にしっかり free する

これらを実装しようと思うと、ポインタの指す先を意識しながらプログラミングする必要がありますので、実際に実装してみるとかなりポインタへの理解を深めることができると思います！

是非解説を理解した上で、ご自身でもキューをポインタで実装してみてください！

同じカテゴリのページ一覧を表示

前の記事

プログラミングで数独を解く方法の解説ページのアイキャッチ
【C言語】数独（ナンプレ）をプログラミングで解く【バックトラッ…

次の記事

挿入ソートを図を使って分かりやすく解説（C言語サンプルプログラ…
挿入ソートの解説ページアイキャッチ