キュー

提供: MonoBook
移動: 案内検索

キュー英語:queue)とは、データ構造のひとつで、リストのうちデータを先入れ先出しするものをいう。

概要[編集]

Data Queue.svg

キューからデータを取り出すときには先に入れられたデータから順に取り出される。 いわゆる人気ラーメン屋などの待ち行列のことである。 先に列んでいた者が優先され、後から来たやつは後ろに列べという常識的なデータ構造であり、そのような業務を補助する常識的なシステムでは多用される。

キューにデータを入れることをエンキュー(英語:enqueue)、取り出すことをデキュー(英語:dequeue)という。

キューの変形として先頭と末尾の両端から入出力を行えるものを両端キューという。

また、キューに追加される要素に優先度をつけ、その優先度によりソートを行うものを優先度付きキーという。現実世界の例でいえば、最近なにかと話題の上級国民を優遇する制度を思い浮かべるかもしれないが、みじかなところでは医療における診療の優先度(トリアージ)などがある。

キューとは逆に後入れ先出しのリストスタックと呼ぶ。

主な実装[編集]

C#[編集]

C#ではSystem.Collections.Generic.Queue<T>クラスが標準で用意されている。

    using System;
    using System.Collections.Generic;
 
    class MainClass
    {
        public static void Main(string[] args)
        {
            var queue = new Queue<string>();
 
            queue.Enqueue("A");
            queue.Enqueue("B");
 
            Console.WriteLine(queue.Dequeue()); //B
            Console.WriteLine(queue.Dequeue()); //A
        }
    }

PHP[編集]

PHPではデータ構造クソ食らえで基本は配列のみとなる。標準ではなんでもかんでもarray()である。 エンキューを行うにはarray_unshift関数を使い、デキューを行うにはarray_shift関数を使うことでキューの様に動作する。 このためキューとして動作していたと思ったら途中からスタックのように動作しだした、などという奇怪なソースコードに遭遇する事例も多々ある。

<?php
$queue = array();
 
array_unshift($queue, "A");
array_unshift($queue, "B");
 
var_dump(array_shift($queue)); //B
var_dump(array_shift($queue)); //A

関連項目[編集]

参考文献[編集]