優先度付きキューとは,キュー (Queue) からデータを取り出す順は,FIFO (First In First Out) というルールに従うのではなく,データの大きい順(または小さい順)に従う,というデータ構造.

例えば、優先度付きキューに、 10, -2, 5, 1 という4つのデータが格納されているとする。小さい値が優先だとすれば、4つのデータの取り出される順は、-2, 1, 5, 10 になる。

以下の実装法は,15パズルを解くために用意したもの.恐らく,もっとも短い実装法のひとつだと思う.
MIN-Priority-queue (小さい順優先).

サポートする操作は2種類のみ.
 void enq(QUE *q)  データをキューに格納(挿入)する操作
 int deq(QUE *q)  最小値のデータをキューから取り出す操作(成功時はリターン値が 1.失敗時は 0)

(下のソースプログラムのテキスト版は こちら

最後のmain() 関数部分では,テストも兼ねて,キューの使い方を説明している.10 から ー5 までの順で整数をキューに挿入したのに対し,取り出した順は -5 から 10 となっている.

ご利用の際に,キューの大きさ(QSIZE) や,キューの構造体(QUE)を適宜変更してください.

なお,最大値優先キュー MAX-Priority-queue (大きい順優先)の実装プログラムは こちら にあり,上のMIN-Priority-queue とは,本質的に,値比較のための不等号向き3つが異なるだけだ.

Comments are closed.

Post Navigation