キュー構造

待ち行列とキュー構造
コンビニのレジ待ち行列をデータとして扱うときのように、先に入った要素を先に処理していくときによく使われるデータ構造がキュー構造である。リスト構造を拡張することで表現できる。

サンプル・プログラム

待ち行列と Pythonによるキュー構造

待ち行列とキュー構造
待ち行列では、キュー構造がよく使われる。
たとえばコンビニでレジ待ちの行列ができているとする。行列の先頭を root、最後尾を tail としてみれば、リスト構造 の一種であることが分かる。
ここでは、1秒に 1 人ずつ行列に並んでいき、レジ処理に 1.5秒かかるとする(人間業とは思えない早さ)。これを Python のプログラムにしてみよう。Python には deque オブジェクトというデータ構造が用意されており、これを使ってプログラム "dt03-31-01.py" を作成する。

0009: from collections import deque
0010: import systimethreading
0011: 
0012: """
0013:  * キューにIDを1つ追加する
0014:  * @global deque Que キュー
0015:  * @param なし
0016:  * @return なし
0017: 
"""
0018: def pushID():
0019:     global Que
0020:     id = 1                          #IDの初期値
0021:     for i in range(10):
0022:         time.sleep(1.0)           #1.0秒待ち
0023:         Que.append(id)               #キューに追加
0024:         sys.stdout.write("追加:{0:2d}".format(id))
0025:         sys.stdout.write(" - 残り:{}\n".format(list(Que)))
0026:         id += 1
0027:     return(0)
0028: 
0029: """
0030:  * キューからIDを1つ取り出し処理する
0031:  * @global deque Que キュー
0032:  * @param なし
0033:  * @return なし
0034: 
"""
0035: def popID():
0036:     global Que
0037:     for i in range(10):
0038:         time.sleep(1.5)               #1.5秒待ち
0039:         id = Que.popleft()               #キューから取り出し
0040:         sys.stdout.write("処理:{0:2d}".format(id))
0041:         sys.stdout.write(" - 残り:{}\n".format(list(Que)))
0042:     return(0)
0043: 
0044: # メイン・プログラム ======================================================
0045: # キューを用意
0046: global Que
0047: Que = deque([])
0048: 
0049: sys.stdout.write("\n")
0050: 
0051: # スレッドを用意
0052: th1 = threading.Thread(target=pushID)
0053: th2 = threading.Thread(target=popID)
0054: 
0055: # スレッド開始
0056: th1.start()
0057: th2.start()

待ち行列とキュー構造
プログラム "dt03-31-01.py" は、行列に並ぶ処理を pushID、発券する処理を popID として、それぞれマルチスレッドで走らせる。関数内部では、sleep を使って 1.0秒、1.5秒待つようにしてある。

プログラムの実行結果は左図の通りである。
先に入れた ID が、先に取り出されて処理されてゆく様子が分かる。

C++によるキュー構造

C++は Python と同じクラス deque を備えており、マルチスレッド処理も記述できるので、Python プログラム "dt03-31-01.py" をほぼそのまま移植し、"dt03-31-03.cpp" とした

0009: #include <iostream>
0010: #include <iomanip>
0011: #include <unistd.h>
0012: #include <sstream>
0013: #include <thread>
0014: #include <deque>
0015: 
0016: using namespace std;
0017: 
0018: deque<int> *Que;     //キューを用意
0019: 
0020: /**
0021:  * キューの内容を成形して返す
0022:  * @param deque キュー
0023:  * @return string 整形した文字列
0024: **/
0025: string listQue(deque<int> *que) {
0026:     ostringstream res;
0027:     int i = 0;
0028:     res << "";
0029:     for (deque<int>::iterator itc = que->begin(); itc != que->end(); itc++) {
0030:         if (i != 0)      res << "";
0031:         res << *itc;
0032:         i++;
0033:     }
0034:     res << " ]";
0035:     return res.str();
0036: }
0037: 
0038: /**
0039:  * キューにIDを1つ追加する
0040:  * @global deque Que キュー
0041:  * @param なし
0042:  * @return なし
0043: **/
0044: void pushID(void) {
0045:     int id = 1;                              //IDの初期値
0046:     for (int i = 0; i < 10; i++) {
0047:         usleep(1000000);                 //1.0秒待ち
0048:         Que->push_back(id);               //末尾に追加
0049:         cout << "追加:" << setw(2) << id;
0050:         cout << " - 残り:" << listQue(Que) << endl;
0051:         id++;
0052:     }
0053: }
0054: 
0055: /**
0056:  * キューからIDを1つ取り出し処理する
0057:  * @global deque Que キュー
0058:  * @param なし
0059:  * @return なし
0060: **/
0061: void popID(void) {
0062:     for (int i = 0; i < 10; i++) {
0063:         usleep(1500000);                 //1.5秒待ち
0064:         int id = *Que->begin();           //先頭から取り出す
0065:         Que->pop_front();                 //先頭を削除
0066:         cout << "処理:" << setw(2) << id;
0067:         cout << " - 残り:" << listQue(Que) << endl;
0068:     }
0069: }
0070: 
0071: // メイン・プログラム ======================================================
0072: int main() {
0073:     Que = new deque<int>;        //キューの実体
0074:     cout << endl;
0075: 
0076:     //スレッドを用意
0077:     thread th1(pushID);
0078:     thread th2(popID);
0079: 
0080:     //スレッド完了を待つ
0081:     th1.join();
0082:     th2.join();
0083: 
0084:     return (0);
0085: }

まず、クラス deque へのポインタをグローバル変数として用意し、実体は main関数の中で new 演算子を用いて用意する。

クラス deque の内容を表示するメソッドは用意されていないので、関数 listQue として用意した。

それ以外は、Python プログラム "dt03-31-01.py" をほぼそのまま移植した。
なお、g++でコンパイルする場合は、マルチスレッドのためのオプション -pthread をお忘れ無く。

PHPによるキュー構造

PHP にはキュー構造が用意されていないので、前に作ったリスト構造向けのクラス "pahooList" を利用してキュー構造を実装する。

1034: class pahooQue {
1035:     var $plist;              //キューの実体としての配列
1036:     var $error$errmsg;     //エラーフラグ,エラーメッセージ
1037: 
1038: /**
1039:  * コンストラクタ
1040:  * @param なし
1041:  * @return なし
1042: */
1043: function __construct() {
1044:     $this->error  = FALSE;
1045:     $this->errmsg = '';
1046:     $this->plist = new pahooList();
1047: }
1048: 
1049: /**
1050:  * デストラクタ
1051:  * @param なし
1052:  * @return なし
1053: */
1054: function __destruct() {
1055:     $this->plist = NULL;
1056: }
1057: 
1058: /**
1059:  * キューに要素を1つ追加する
1060:  * @param object $data 追加する要素
1061:  * @return なし
1062: */
1063: function push($data) {
1064:     $this->plist->append($data);
1065:     $this->error = $this->plist->error;
1066:     $this->errmsg = $this->plist->errmsg;
1067:     return (! $this->error);
1068: }
1069: 
1070: /**
1071:  * キューから要素を1つ取り出す
1072:  * @param なし
1073:  * @return object 取り出した要素/NULL 要素がない
1074: */
1075: function pop() {
1076:     if ($this->len() == 0) {
1077:         $this->error  = TRUE;
1078:         $this->errmsg = 'que: No data';
1079:         return NULL;
1080:     } else {
1081:         $this->plist->moveRoot();
1082:         $data = $this->plist->get();
1083:         $this->plist->delete();
1084:         return $this->error ? NULL : $data;
1085:     }
1086: }
1087: 
1088: /**
1089:  * キューに残っている要素数を数える
1090:  * @param なし
1091:  * @return int キューの要素数
1092: */
1093: function len() {
1094:     return $this->plist->len();
1095: }
1096: 
1097: /**
1098:  * リストの内容を成形して返す
1099:  * @param なし
1100:  * @return string リストの内容
1101: */
1102: function list() {
1103:     return $this->plist->list();
1104: }
1105: 
1106: // End of Class
1107: }

キューに要素を追加するのは、リストの tail に追加すればいいから、[pahooList::append] メソッドを利用する。
キューから要素を取り出すには、リストの root から取り出し、これを削除すればいいから、pahooList::moveRoot] メソッドを使って root へ移動し、pahooList::get メソッドと、pahooList::delete メソッドを利用する。

キュー構造を実現する pahooQue クラスには、以下のメソッドを用意した。
メソッド機能
push()キューに要素を1つ追加する。
pop()キューから要素を1つ取り出す。
len()キューに残っている要素数を数える。
list()リストの内容を成形して返す。

 

クラス pahooQue を使って Python プログラム "dt03-31-01.py" を PHP に移植したものが "dt03-31-02.php" である。
PHP による push のイメージ
push - PHPによるキュー
PHP による pop のイメージ
pop - PHPによるキュー

0011: //データ構造クラス
0012: require_once('pahooDataStructure.php');
0013: 
0014: // メイン・プログラム ======================================================
0015: // キューを用意
0016: $que = new pahooQue;
0017: 
0018: $id = 1;                 //IDの初期値
0019: while (TRUE) {
0020:     $rd = rand(1, 100);
0021: 
0022:     //IDを追加(40%の確率)
0023:     if (($id <= 10) && ($rd < 40)) {
0024:         $que->push($id);
0025:         printf("追加:%02d - 残り:%s\n", $id$que->list());
0026:         $id++;
0027:     //IDを処理(60%の確率)
0028:     } else if ($que->len() > 0) {
0029:         $i = $que->pop();
0030:         printf("処理:%02d - 残り:%s\n", $i$que->list());
0031:     //ループ終了
0032:     } else if ($id > 10 && $que->len() == 0) {
0033:         break;
0034:     }
0035: }

待ち行列とキュー構造
PHP はシングルスレッドの処理系であることから、行列に並ぶ処理と発券処理をマルチスレッドにするのではなく、乱数関数  rand  を使って場合分けすることにした。

プログラムの実行結果は左図の通りである。

PHPによるマルチスレッド処理(参考)

ここからは参考情報である。
PHP はシングルスレッドの処理系だと書いたが、マルチスレッド処理のための仕組みが用意されている。たとえば、pecl で用意されているクラス pthreads を使うことでマルチスレッド処理が可能となる。
ただし、いくつかの制約がある。
  1. ZTS版の PHP が必要である。
  2. PHP のバージョンによって pthreads のバージョンを選ぶ必要がある。
  3. pthreads のバージョンによっては、スレッドの中で他のインスタンス・メソッドを呼び出すことができない。
たとえば Windows版PHP バージョン 7.2.1 で動作する pthreads は、ここからダウンロードする。解凍して得られたファイルのうち、"php_pthreads.dll" は extension で指定するディレクトリへコピーする。
"pthreadVC2.dll" は、PATH の通ったディレクトリ――"PHP.EXE" のあるディレクトリか "C:\Windows\System32"――へコピーする。
最後に、"php.ini"に "[extension=php_pthreads.dll:blue" を追記する。
(この項おわり)
header