【C言語入門の次】 第06回 キュー

https://youtu.be/gGyrQcatl4c

$\textcolor{pink}{四国めたん: }$教師役ですわ

$\textcolor{lime}{ずんだもん: }$生徒役なのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ こんにちは。四国めたんです

$\footnotesize \textcolor{lime}{ずんだもん:}$ ずんだもんなのだ。こんにちはなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 今回は キュー という データ構造 についてお話ししますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ キュー ？

$\footnotesize \textcolor{pink}{四国めたん:}$ はい、データを出し入れするための有名な方法のひとつですわね

$\footnotesize \textcolor{lime}{ずんだもん:}$ ふむふむ

キュー

$\footnotesize \textcolor{pink}{四国めたん:}$ キュー とは、データの出し入れの方法のひとつですわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ そうなのか？

$\footnotesize \textcolor{pink}{四国めたん:}$ はい、 待ち行列 とも呼ばれますわね

$\footnotesize \textcolor{lime}{ずんだもん:}$ なるほどなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ データの出し入れは、インデックスの指定ではなく、データを入れた順番で決まりますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ そこは スタック と同じなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ ただ、 キュー の場合、データの取り出しは、先に入れたデータから順番におこなわれますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ スタック とは逆なのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ このようなデータの出し入れの方法を FIFO (First In First Out)と云いますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ スタック のときのように LILO (Last In Last Out)とは云わないのか？

$\footnotesize \textcolor{pink}{四国めたん:}$ LILO とも云いますが、殆ど使われませんわね

$\footnotesize \textcolor{lime}{ずんだもん:}$ りょうかいなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ なお、データの入力は、 キュー の言葉通りにデータを列の最後尾に並ばせますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ ふむ

$\footnotesize \textcolor{pink}{四国めたん:}$ また、データの出力は、最前列から順番に取り出していきますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ なるほどなのだ

キューの実装

$\footnotesize \textcolor{pink}{四国めたん:}$ キュー は リスト と非常に相性が良いですわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ そうなのか？

$\footnotesize \textcolor{pink}{四国めたん:}$ はい、 リスト を少し変形するだけで キュー になりますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ その辺りは スタック と似ているのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 特に以前の 連結リスト は相性が良いですわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ うむ

$\footnotesize \textcolor{pink}{四国めたん:}$ 例として、以前の 連結リスト を少し変更して、学生番号と名前を キュー として扱うようにしてみましょう

$\footnotesize \textcolor{lime}{ずんだもん:}$ よろしくなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ まずはヘッダーファイルですわ

queue.h

#pragma once
#ifndef _INC_QUEUE
#define _INC_QUEUE

#include <stdio.h>

#define NAME_SIZE (20)

typedef struct student {
  unsigned int id;
  char name[NAME_SIZE];
  struct student* pnext;
} student;

typedef struct {
  student* ptop;
  student* pbuttom;
  size_t num;
} student_queue;

void init_queue(student_queue* plist);

void final_queue(student_queue* plist);

int push(student_queue* plist, unsigned int id, char name[]);

student* pop(student_queue* plist);

#endif  // _INC_QUEUE

$\footnotesize \textcolor{pink}{四国めたん:}$ 今回は、 連結リスト の最初のノードや最後のノード、リストのサイズを構造体student_queueにまとめていますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ りょうかいなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ そして、 連結リスト の操作にかかわる関数と合わせて、"queue.h"ヘッダーファイルに宣言していますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ なるほどなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 次は実装ですわね

queue.c

#include <memory.h>
#include <stdlib.h>
#include <string.h>

#include "queue.h"

void init_queue(student_queue* pqueue) {
  if (pqueue != NULL) {
    pqueue->ptop = NULL;
    pqueue->pbuttom = NULL;
    pqueue->num = 0;
  }
  return;
}

void final_queue(student_queue* pqueue) {
  if (pqueue != NULL) {
    student* pdata = pop(pqueue);
    while (pdata != NULL) {
      free(pdata);
      pdata = pop(pqueue);
    }
  }
  return;
}

student* get_data(unsigned int id, char name[]) {
  student* pstudent = (student*)malloc(sizeof(student));
  if (pstudent != NULL) {
    pstudent->id = id;
    strcpy_s(pstudent->name, NAME_SIZE, name);
    pstudent->pnext = NULL;
  }
  return pstudent;
}

int push(student_queue* pqueue, unsigned int id, char name[]) {
  int rc = -1;
  if (pqueue != NULL) {
    student* pdata = get_data(id, name);
    if (pdata != NULL) {
      if (pqueue->num == 0) {
        pqueue->ptop = pdata;
        pqueue->pbuttom = pdata;
      } else {
        pqueue->pbuttom->pnext = pdata;
        pqueue->pbuttom = pdata;
      }
      pqueue->num++;
      rc = pqueue->num;
    }
  }
  return rc;
}

student* pop(student_queue* pqueue) {
  student* pdata = NULL;
  if ((pqueue != NULL) && (pqueue->num > 0)) {
    pdata = pqueue->ptop;
    pqueue->ptop = pdata->pnext;
    pqueue->num--;
  }
  return pdata;
}

初期化関数

$\footnotesize \textcolor{pink}{四国めたん:}$ まず、初期化の関数として、init_queueを定義していますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 初期化では何をしているのだ？

$\footnotesize \textcolor{pink}{四国めたん:}$ この関数では、ポインターをNULL、データのサイズ"num"を0に初期化していますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 以前と違って ダミーノード を作成していないのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ はい、今回は ダミーノード を使わないようにしましたわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ りょうかいなのだ

終了関数

$\footnotesize \textcolor{pink}{四国めたん:}$ 次に、終了処理の関数としてfinal_queueを定義していますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ pop関数はなんなのだ？

$\footnotesize \textcolor{pink}{四国めたん:}$ 後で説明しますが、 ノード を取り出す関数ですわね

$\footnotesize \textcolor{lime}{ずんだもん:}$ なるほどなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 取り出したノードをfree関数で破棄していますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 全てのノードを取り出して破棄しているのだ

データ追加関数

$\footnotesize \textcolor{pink}{四国めたん:}$ 次に、データを追加する関数pushを定義していますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ データの挿入位置の指定がないのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ はい、 キュー では、ノードの追加は 連結リスト の最後に限定されますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ りょうかいなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ なお、ノードを追加し易いように、student_queue構造体には、リストの最後のノードへのポインタpbuttomを設定していますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ これで、リストの最初からノードを辿らなくても、リストの最後のノードに直接、アクセスできるのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ そして、追加するノードはget_data関数内で、mallocにより確保していますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ なるほどなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ ちなみに、今回は ダミーノード を使わなかったので、データ数が0の場合のみ、ノードの操作が異なっていますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ うむ

データ取得関数

$\footnotesize \textcolor{pink}{四国めたん:}$ 次にデータを取得する関数popを定義していますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ ふむふむ

$\footnotesize \textcolor{pink}{四国めたん:}$ 戻り値としては、 連結リスト の最初のノードを返しますわね

$\footnotesize \textcolor{lime}{ずんだもん:}$ うむ

$\footnotesize \textcolor{pink}{四国めたん:}$ なお、ptopが指すノードへのポインタは、取り出したデータのpnextが指しているノードになりますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ りょうかいなのだ

メイン関数

main.c

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

#include "queue.h"

int main(int argc, char* argv[]) {
  student_queue queue;
  init_queue(&queue);

  push(&queue, 1, "佐藤紬");
  push(&queue, 2, "鈴木陽翔");
  push(&queue, 3, "高橋翠");
  push(&queue, 4, "田中朝陽");
  push(&queue, 5, "伊藤凛");

  size_t size = queue.num;
  for (size_t i = 0; i < size; i++) {
    student* pstudent = pop(&queue);
    printf("学生番号: %d, 名前: %s\n", pstudent->id, pstudent->name);
    free(pstudent);
  }

  final_queue(&queue);

  return 0;
}

$\footnotesize \textcolor{pink}{四国めたん:}$ メイン関数内では、まず、5人分の学生のデータをpush関数で追加していますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ ふむ

$\footnotesize \textcolor{pink}{四国めたん:}$ 次に、pop関数を5回呼び出して、5人分の学生のデータを出力しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ ふむふむ

$\footnotesize \textcolor{pink}{四国めたん:}$ なお、得られたstudent構造体のノードは、free関数で開放する必要がありますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 注意しないと忘れてしまうのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ それでは実行してみましょう

$\footnotesize \textcolor{lime}{ずんだもん:}$ pushした順にデータが表示されたのだ

循環リストでキューを

$\footnotesize \textcolor{pink}{四国めたん:}$ 連結リスト で キュー を実装すると、 キュー から取り出したノードをfreeで破棄しなければなりませんわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 少々面倒なのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ そこで、 連結リスト の一種である 循環リスト を用いて キュー を実装することにしますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 循環リスト を用いると何か良いことがあるのか？

$\footnotesize \textcolor{pink}{四国めたん:}$ いくらかの制約はありますが、 キュー から取り出したノードをfreeで破棄する必要がなくなりますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ お～、それは素晴らしいのだ

循環リスト

$\footnotesize \textcolor{lime}{ずんだもん:}$ 循環リスト は、以前に 連結リスト のバリエーションとして少しだけ触れているのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ そうですわね

$\footnotesize \textcolor{pink}{四国めたん:}$ 循環リスト は 連結リスト の一種で、最後のノードが指す次のノードをNULLではなく、先頭のノードにしている点が異なりますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 結果として、 最後のノード とか 先頭のノード とかの概念がなくなるのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 代わりに キュー で次にデータを取り出すノードや次にデータを入れるノードを指すポインタが必要になりますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ うむ

循環リストでのキューの実装

$\footnotesize \textcolor{pink}{四国めたん:}$ それでは 循環リスト での キュー の実装を見てみましょう

$\footnotesize \textcolor{lime}{ずんだもん:}$ よろしくなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ まずはヘッダーファイルですわ

queue.h

#pragma once
#ifndef _INC_QUEUE
#define _INC_QUEUE

#include <stdio.h>

#define NAME_SIZE (20)
#define LIST_SIZE (10)

typedef struct student {
  unsigned int id;
  char name[NAME_SIZE];
  struct student* pnext;
} student;

typedef struct {
  student* pin;
  student* pout;
  size_t num;
  size_t size;
} student_queue;

int init_queue(student_queue* plist);

void final_queue(student_queue* plist);

int push(student_queue* plist, unsigned int id, char name[]);

student* pop(student_queue* plist);

#endif  // _INC_QUEUE

$\footnotesize \textcolor{pink}{四国めたん:}$ 今回、student_queue構造体ではノードの先頭などを指すポインタを削除していますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ ふむ

$\footnotesize \textcolor{pink}{四国めたん:}$ その代わり、次にデータを入れるノードを指すポインタ"pin"と、次にデータを取り出すノードを指すポインタ"pout"を導入していますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ ふむふむ

$\footnotesize \textcolor{pink}{四国めたん:}$ また、ノードの数を表す"size"と、有効なデータの数を表す"num"を設けていますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ りょうかいなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 次に実装ですわね

queue.c

#include "queue.h"

#include <memory.h>
#include <stdlib.h>
#include <string.h>

student* get_node() {
  student* pstudent = (student*)malloc(sizeof(student));
  if (pstudent != NULL) {
    pstudent->id = 0;
    pstudent->name[0] = 0;
    pstudent->pnext = NULL;
  }
  return pstudent;
}

int init_queue(student_queue* pqueue) {
  int rc = -1;
  if (pqueue != NULL) {
    student* pbottom = get_node();
    if (pbottom != NULL) {
      pqueue->num = 0;
      pqueue->pin = pbottom;
      pqueue->size = 1;
      for (size_t i = 1; i < LIST_SIZE; i++) {
        student* pstudent = get_node();
        if (pstudent != NULL) {
          pstudent->pnext = pqueue->pin;
          pqueue->pin = pstudent;
          pqueue->size++;
        }
      }
      pbottom->pnext = pqueue->pin;
      pqueue->pout = pqueue->pin;
      rc = 0;
    }
  }
  return rc;
}

void final_queue(student_queue* pqueue) {
  if (pqueue != NULL) {
    student* pdata = pqueue->pin;
    for (size_t i = 0; i < pqueue->size; i++) {
      pqueue->pin = pdata->pnext;
      free(pdata);
      pdata = pqueue->pin;
    }
  }
  return;
}

int push(student_queue* pqueue, unsigned int id, char name[]) {
  int rc = -1;
  if (pqueue != NULL) {
    if (pqueue->num < pqueue->size) {
      pqueue->pin->id = id;
      strcpy_s(pqueue->pin->name, NAME_SIZE, name);
      pqueue->pin = pqueue->pin->pnext;
      pqueue->num++;
      rc = 0;
    }
  }
  return rc;
}

student* pop(student_queue* pqueue) {
  student* pdata = NULL;
  if ((pqueue != NULL) && (pqueue->num > 0)) {
    pdata = pqueue->pout;
    pqueue->pout = pdata->pnext;
    pqueue->num--;
  }
  return pdata;
}

初期化関数

$\footnotesize \textcolor{pink}{四国めたん:}$ まず、初期化の関数として、init_queueを定義していますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ ふむ

$\footnotesize \textcolor{pink}{四国めたん:}$ この関数では、予め決めておいた数のノードをget_node関数で作成して 連結リスト を形成していますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ りょうかいなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 最後に 連結リスト の先頭と最後を連結して 循環リスト を形成していますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ なるほどなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ なお、最初は"pin"と"pout"は同じノードを指しますわね

$\footnotesize \textcolor{lime}{ずんだもん:}$ うむ

終了関数

$\footnotesize \textcolor{pink}{四国めたん:}$ 次に、終了処理の関数としてfinal_queueを定義していますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ うむ

$\footnotesize \textcolor{pink}{四国めたん:}$ "pin"から全てのノードをたどり、ノードの数だけfree関数で破棄していますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ りょうかいなのだ

データ追加関数

$\footnotesize \textcolor{pink}{四国めたん:}$ 次に、データを追加する関数pushを定義していますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ うむ

$\footnotesize \textcolor{pink}{四国めたん:}$ この関数ではstudent_queueの"num"と"size"から、ノードに空きがなければエラーとしていますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ ノードを増やすのではいけないのか？

$\footnotesize \textcolor{pink}{四国めたん:}$ ノードを増やすのが一般的ですが、プログラムを簡単にするために、今回はノード数を固定していますわね

$\footnotesize \textcolor{lime}{ずんだもん:}$ りょうかいなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ ちなみに、データは"pin"が指すノードに入れますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ ふむ

$\footnotesize \textcolor{pink}{四国めたん:}$ データを入れたら"num"を1つ増やし、"pin"の指すノードを次のノードに移しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ なるほどなのだ

データ取得関数

$\footnotesize \textcolor{pink}{四国めたん:}$ 次にデータを取得する関数popを定義していますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ うむ

$\footnotesize \textcolor{pink}{四国めたん:}$ student_queueの"num"が0でなければ、"pout"の指すノードを返しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ ふむ

$\footnotesize \textcolor{pink}{四国めたん:}$ そして、"pout"が指すノードを次のノードに移して"num"を1つ減らしますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ りょうかいなのだ

メイン関数

main.c

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

#include "queue.h"

int main(int argc, char* argv[]) {
  student_queue queue;
  init_queue(&queue);

  push(&queue, 1, "佐藤紬");
  push(&queue, 2, "鈴木陽翔");
  push(&queue, 3, "高橋翠");
  push(&queue, 4, "田中朝陽");
  push(&queue, 5, "伊藤凛");
  push(&queue, 6, "渡辺暖");

  size_t size = queue.num;
  for (size_t i = 0; i < size; i++) {
    student* pstudent = pop(&queue);
    printf("学生番号: %d, 名前: %s\n", pstudent->id, pstudent->name);
  }

  final_queue(&queue);

  return 0;
}

$\footnotesize \textcolor{pink}{四国めたん:}$ メイン関数内では、まず、6人分の学生のデータをpush関数で追加しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ ノードの数は10なので、余裕があるのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 次に、pop関数を6回呼び出して、6人分の学生のデータを出力しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 全部のデータを書き出すのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ なお、得られたstudent構造体のノードは、 循環リスト 中で再利用されるので、free関数等で解放してはいけませんわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 前のサンプルコードとは、この部分が異なっているのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ ちなみに、次にpush関数が呼ばれると、ノードのデータ内容が上書きされる場合があるので注意が必要ですわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 次にpushが呼ばれる前に処理を終えておくのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ それでは実行してみましょう

まとめ

$\footnotesize \textcolor{pink}{四国めたん:}$ お疲れさまでした

$\footnotesize \textcolor{lime}{ずんだもん:}$ おつかれさまなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 以上で キュー を終了しますわ