キュー

提供: 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

関連項目[編集 | ソースを編集]

参考文献[編集 | ソースを編集]