3．2 待ち行列(キュー）

番号 以下をクリックすると，該当箇所にジャンプします
（１） 考え方
（２） 配列によるキューの実現
（３） サイクリックなキュー
（１）考え方

待ち行列（キュー）とは，スタックと同様，
データを一時的に蓄えるデータ構造のひとつです。

キューでは，最初に入れたデータが最初に取り出されます。

ですから，先入れ先出し（FIFO:First In First Out）方式
とも呼ばれま。

タスクや通信等の処理待ち行列，離散系シミュレーション等，
様々な場面に使われます。。

　　　　　


番号 以下をクリックすると，該当箇所にジャンプします
（１） 考え方
（２） 配列によるキューの実現
（３） サイクリックなキュー
（２）配列によるキューの実現

スタックと同様，配列によってキューを実現することができます。

(a) エンキューでデータを最後尾に入れる。

(b) デキューで先頭を取り出して，配列をずらす


［Program 3−2］ キュー動きを確認するプログラム


//宣言分部
private string[] Que=new string[10];
private int QuePointer=0;

// dequeue
private string Deque()
{
　if(QuePointer==0) {MessageBox.Show("キューが空です."); return "" }
　else {
　　string R=Que[0]; QuePointer--;
　　for(int i=0;i<QuePointer;i++) Que[i]=Que[i+1];// すべての要素をずらす
　　return R;
　}
}

// enqueue
private void Enque(string V)
{
　if (QuePointer>=Que.Length) MessageBox.Show("キューが満杯です．");
　else Que[QuePointer++]=V;
}

private void 表示()
{
　listBox1.Items.Clear();
　for(int i=0;i<QuePointer;i++)listBox1.Items.Add(Que[i]);
}

private void button1_Click(object sender, System.EventArgs e)
{
　 Enque(textBox1.Text); 表示();
}
private void button2_Click(object sender, System.EventArgs e)
{
　string R=Deque(); label1.Text=R; 表示();
}

番号 以下をクリックすると，該当箇所にジャンプします
（１） 考え方
（２） 配列によるキューの実現
（３） サイクリックなキュー
（３）サイクリックなキュー

単純な配列でキューを実現すると，
データを取り出すたびに，配列をずらす必要があります。

そこで，ポインタを進める際，
ポインタが配列サイズより大きければ，
０に戻すような配列を考えてみましょう。

概念的には，サイクリックな配列を考えていることになります。

このような配列を考えると，配列をずらす替わりに，
先頭ポインタをカウントすることで，
キューを実現することができます。

　　　　

プログラム上の操作は，以下のようになります。

［エンキュー］

　@）終了ポインタをカウントアップ
　A）終了ポインタが配列数よりおおきければ，終了ポインタを０とする。
　B）終了ポインタが開始ポインタと同じであれば，満杯とみなし，エラー。
　C）終了ポインタが示す領域にデータを設定する。

［デキュー］
　@）終了ポインタと開始ポインタが同じであれば,空とみなす。
　A）開始ポインタをカウントアップ。
　B）開始ポインタが配列数よりおおきければ，開始ポインタを０とする。
　C）C開始ポインタが示す領域からデータを取り出す。

　　　　　　　　

［Program 3−3］ キュー動きを確認するプログラム

　　フォーム定義は［Program 3-2］と同じです。

// 宣言分部
private const int MAXQUE = 10;
private string[] QUE=new string[MAXQUE];
private int StartPointer;
private int EndPointer;

// 初期設定
private void Form1_Load(object sender, System.EventArgs e)
{
　　 StartPointer=0; EndPointer=0;
}

// キュー内容の表示
private void 表示()
{
　int i;
　listBox1.Items.Clear();
　if(EndPointer==StartPointer)
　　for(i=0;i<MAXQUE;i++)listBox1.Items.Add("----");
　else if(EndPointer<StartPointer) {
　　for(i=0;i<EndPointer;i++)listBox1.Items.Add(QUE[i]);
　　for(i=EndPointer;i<StartPointer;i++)listBox1.Items.Add("----");
　　for(i=StartPointer;i<MAXQUE;i++)listBox1.Items.Add(QUE[i]);
　}
　else {
　　for(i=0;i<StartPointer;i++)listBox1.Items.Add("----");
　　for(i=StartPointer;i<EndPointer;i++)listBox1.Items.Add(QUE[i]);
　　for(i=EndPointer;i<MAXQUE;i++)listBox1.Items.Add("----");
　}
}

private string Deque()
{
　string SR="";
　if(StartPointer!=EndPointer){
　　SR=QUE[StartPointer]; StartPointer=CountP(StartPointer);
　}
　else MessageBox.Show("キューが空です.");
　return SR;
}

private void Enque(string V)
{
　int P = CountP(EndPointer);
　if(P!=StartPointer) {
　　QUE[EndPointer]=V; EndPointer=P;
　}
　else MessageBox.Show("キューが満杯です．");
}

private int CountP(int P)
{
　P++; if(P>=MAXQUE) P= 0; return P;
}

private void button1_Click(object sender, System.EventArgs e)
{
　Enque(textBox1.Text); 表示();
}

private void button2_Click(object sender, System.EventArgs e)
{
　label1.Text=Deque(); 表示();
}

番号 以下をクリックすると，該当箇所にジャンプします
（１） 考え方
（２） 配列によるキューの実現
（３） サイクリックなキュー
1. 基本的なアルゴリズム

2. 基本的なデータ構造

3. 操作を伴うデータ構造

4. 探索

5. 再帰的アルゴリズム

6. ソート

7. 集合

8. 文字列処理

9. 色々なアルゴリズム


上のタイトルをクリックします