C LANGUAGE TECHNOLOGY

【C言語】キューとは【FIFOキュー,優先度キュー,二項ヒープ,赤黒木】

2021年9月6日

悩んでいる人

C言語のキューを教えて!

こういった悩みにお答えします.

本記事の信頼性

  • リアルタイムシステムの研究歴12年.
  • 東大教員の時に,英語でOS(Linuxカーネル)の授業.
  • 2012年9月~2013年8月にアメリカのノースカロライナ大学チャペルヒル校(UNC)コンピュータサイエンス学部で客員研究員として勤務.C言語でリアルタイムLinuxの研究開発.
  • プログラミング歴15年以上,習得している言語: C/C++PythonSolidity/Vyper,Java,Ruby,Go,Rust,D,HTML/CSS/JS/PHP,MATLAB,Assembler (x64,ARM).
  • 東大教員の時に,C++言語で開発した「LLVMコンパイラの拡張」,C言語で開発した独自のリアルタイムOS「Mcube Kernel」GitHubにオープンソースとして公開
  • 2020年1月~現在はアメリカのノースカロライナ州チャペルヒルにあるGuarantee Happiness LLCのCTOとしてECサイト開発やWeb/SNSマーケティングの業務.2022年6月~現在はアメリカのノースカロライナ州チャペルヒルにあるJapanese Tar Heel, Inc.のCEO兼CTO.
  • 最近は自然言語処理AIイーサリアムに関する有益な情報発信に従事.
    • (AI全般を含む)自然言語処理AIの論文の日本語訳や,AIチャットボット(ChatGPT,Auto-GPT,Gemini(旧Bard)など)の記事を50本以上執筆.アメリカのサンフランシスコ(広義のシリコンバレー)の会社でプロンプトエンジニア・マネージャー・Quality Assurance(QA)の業務委託の経験あり.
    • (スマートコントラクトのプログラミングを含む)イーサリアムや仮想通貨全般の記事を200本以上執筆.イギリスのロンドンの会社で仮想通貨の英語の記事を日本語に翻訳する業務委託の経験あり.

こういった私から学べます.

C言語を独学で習得することは難しいです.

私にC言語の無料相談をしたいあなたは,公式LINE「ChishiroのC言語」の友だち追加をお願い致します.

私のキャパシティもあり,一定数に達したら終了しますので,今すぐ追加しましょう!

友だち追加

独学が難しいあなたは,元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう.後悔はさせません!

【C言語】キューとは

キューとは,データを先入れ先出し(First In First Out)で保持するデータ構造です.

キューにデータに入れることをエンキュー(enqueue),データをキューから取り出すことをデキュー(dequeue)と呼びます.

本記事では,C言語のキューを紹介していきます.

他のデータ構造を知りたいあなたはこちらからどうぞ.

FIFOキュー

C言語のFIFOキューのコードは以下になります.

QUEUE_SIZE分のデータを格納できます.

実行結果は以下になります.

データをFIFOで操作していることがわかります.

優先度キュー

優先度キューは,キューのデータを優先度順で管理するキューです.

優先度キューは,リアルタイムOSやLinuxカーネルのスケジューラ等で利用されます.

リアルタイムOSの技術であるリアルタイムシステムやLinuxカーネルを知りたいあなたはこちらからどうぞ.

優先度キューのコードは以下になります.

データの数値が小さいほど高い優先度になり,最高優先度のデータは優先度キューの先頭に格納されます.

実行結果は以下になります.

二項ヒープ

二項ヒープは,優先度キューを実現するデータ構造の一つです.

二項ヒープの特徴は以下になります.

  • 二分ヒープとよく似たデータ構造であるが,二項ヒープは2つのヒープを素早くマージする操作をサポート
  • 特殊な木構造「二項木」を利用して実現
  • マージ可能な抽象データ型ヒープの実装

二項ヒープのコードは以下になります.

とても複雑なので,時間をかけて読みましょう.難しかったら読み飛ばしても構いません.

二項ヒープのコードで実装されている主な関数は以下になります.

  • enqueue_bheap_queue関数:二項ヒープにノードをエンキュー
  • dequeue_bheap_queue関数:二項ヒープからノードをデキュー
  • pick_next_value関数:二項ヒープから最高優先度ノードの値(struct value型)を取得
  • print_bheap関数:二項ヒープのノードを表示

実行結果は以下になります.

enqueue_bheap_queue関数でノードをエンキューしたり,dequeue_bheap_queue関数でノードをデキューしたりした場合に,二項ヒープの木構造がどのように変化するのかをprint_bheap関数で確認しています.

最高優先度ノードの値を取得したい場合は,pick_next_value関数を利用します.

ここで,pick_next_value関数では,ノードをデキューしないことに注意して下さい.

赤黒木

赤黒木は,平衡二分木の一種で,以下の性質を持ちます.

  • あるノードの右部分木に含まれるノードの値以下
  • あるノードの左部分木に含まれるノードの値以上

赤黒木の特徴は,探索,挿入,削除などの操作における最悪時間計算量が\(\mathcal{O}(\log n)\)と短いことです.

赤黒木は,Linuxカーネルのスケジューラ「Completely Fair Scheduler(CFS)」で利用されています.

LinuxカーネルのCFSを知りたいあなたはこちらからどうぞ.

赤黒木のコードは以下になります.

実行結果は以下になります.

まとめ

C言語のキューを紹介しました.

具体的には,FIFOキュー,優先度キュー,二項ヒープ,赤黒木を解説しました.

特に,二項ヒープや赤黒木は実用的なキューなので,難しいですが理解しておきましょう!

他のキューとしてリングバッファ(リングキュー)が挙げられます.

C言語のリングバッファのコードを知りたいあなたはこちらからどうぞ.

C言語を独学で習得することは難しいです.

私にC言語の無料相談をしたいあなたは,公式LINE「ChishiroのC言語」の友だち追加をお願い致します.

私のキャパシティもあり,一定数に達したら終了しますので,今すぐ追加しましょう!

友だち追加

独学が難しいあなたは,元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう.後悔はさせません!

-C LANGUAGE, TECHNOLOGY
-, , , , , , ,