キュー (コンピュータ)

キュー（英: queue）あるいは待ち行列は、コンピュータにおける基本的なデータ構造の一つ。データを先入れ先出し（FIFO）のリスト構造で保持するものである。キューからデータを取り出すときには、先に入れられたデータから順に取り出される。キューにデータを入れることをエンキュー（enqueue）、取り出すことをデキュー（dequeue）という。

プリンターへの出力処理や、ウィンドウシステムにおけるイベントあるいはメッセージのハンドリング、プロセスの管理、探索などのアルゴリズムの下請けなど、データを入力された順番通りに処理する必要があるケースに用いられる。また、個々のタスクの実行時間が予測できない、あるいは実行に時間がかかってしまい、即座に（同期的に）実行することができない場合、キューを使っていったんタスクを溜め込んでおき、後からタスクを取り出して非同期で実行する、というような目的で使用できる。

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

キューとは逆に後入れ先出し（LIFO）のリスト構造を持つデータバッファをスタックと呼ぶ。

プログラミング言語によっては、キューを標準ライブラリとして実装していて、プログラマがキューそのもののプログラムを書かなくても利用できるようになっている。標準ライブラリとして用意されていない場合であっても、他のデータ構造、例えばリンクトリストをキューと見立てて利用することも多い。

優先度付きキュー

→「優先度付きキュー」も参照

キューに追加する要素に優先度をつけ、優先度に基づいて、キュー内でソートするものを優先度付きキューという。高速化のための各種アルゴリズムが研究されており、また様々な他のアルゴリズムで間接的に使われている。

キューの応用

メッセージキュー: 通信のために使用されるメッセージのキュー。

UNIXでは、msgsnd および msgrcv システム・コールにより、それぞれデータを送信および受信できる。データを送信する先は同じプロセスであってもよいし、他のプロセスであってもよい。

Microsoft Windowsでは、メッセージループを持つスレッドあるいはプロセスにイベントを送信するのに用いられ、イベント駆動型プログラミングを実現している。特にGUIアプリケーションで必須であり、プログラムは受信したイベントメッセージを1つずつメッセージループ内で取得し、適切なプロシージャ（イベントハンドラー）に配送し、イベントに対応する動作を実行する。メッセージ情報はMSG構造体^[1]によるインターフェイスを介して提供される。

コマンドキュー: ソフトウェアまたはハードウェアに複数のコマンド（命令）を送信して非同期実行させるためのキュー。

例えばグラフィックスハードウェア (GPU) との双方向通信には時間がかかるので、スループットを向上するためにほとんどの描画命令は応答が不要な単方向形式となっており、いったんコマンドキューにキューイングされ、まとめて非同期にバッチ処理される。

コマンドキューはハードウェアに近いデバイスドライバー層で実装してあり、上位レベルのAPIやミドルウェアを利用するアプリケーション層では意識しないで済むこともあるが、下位レベルのAPIではミドルウェアやアプリケーション側で明示的にコマンドキューを利用することもある^[2]。

タスクキュー: ワーカースレッドやサービスプロセスに委譲する処理を一時的に溜め込んでおくためのキュー^[3]。

キューマシン

キューマシンは、中間結果格納用にキューを用いる計算モデルである。^[4]^[5]^[6]^[7]

演算はデータをデキューして行い、その結果をエンキューする（スタックマシンの、ポップ＝デキューでプッシュ＝エンキューだと考えれば良い）。そのため、スタックマシンと同じように0オペランドの命令で表現することができる。

また、キューマシンはデータフローに沿って命令を実行することになる。これはキューマシンの特徴の一つといえる。

PostScript風の、しかしスタックではなくキュー（FIFO）ベースの言語「FIFOL」があり^[8]^[9]^[10]^[11]、不動点プログラミングについて考察されていたり^[12]、万能機械の実装が（万能チューリング機械のようにして）示されている^[13]。 ^[14]も参照。

ここでは例として 9 * (8 - 1) / (3 + 6) という式からのコード生成と、そのキューマシンでの実行を見てゆく。

式を二分木であらわし、幅優先探索の逆順で、一番下の葉から横に、次いで上に、の順でたどってゆき、現れたノードを順にトークン（コマンド）にしてゆく。

キューマシンのJavaで実装したサンプルを以下に示す。

import java.util.LinkedList;
import java.util.NoSuchElementException;
import java.util.Queue;
import java.util.StringTokenizer;

class QueueMachine {
  public static void main (final String[] args) {

    final String machineCode = "8 1 9 - 3 6 * + /";

    final Queue<Integer> q = new LinkedList<Integer>();

    final StringTokenizer st = new StringTokenizer(machineCode);
    for (;;) {
      try {
        final String token = st.nextToken();
        System.out.print(q + " : ");
        try {
          q.add(Integer.valueOf(token));
        } catch (final NumberFormatException e) {
          final int a, b;
          switch (token.charAt(0)) {
          case '+':
            a = q.remove().intValue();
            b = q.remove().intValue();
            q.add(Integer.valueOf(a + b));
            break;
          case '-':
            a = q.remove().intValue();
            b = q.remove().intValue();
            q.add(Integer.valueOf(a - b));
            break;
          case '*':
            a = q.remove().intValue();
            b = q.remove().intValue();
            q.add(Integer.valueOf(a * b));
            break;
          case '/':
            a = q.remove().intValue();
            b = q.remove().intValue();
            q.add(Integer.valueOf(a / b));
            break;
          default:
            throw new RuntimeException();
          }
        }
        System.out.println(token);
      } catch (final NoSuchElementException e) {
        break;
      }
    }
    System.out.println(q);
  }
}

実行結果を以下に示す。［］内がキューの内容、コロンの右が実行しようとしているトークン（コマンド）である。右端からエンキュー、左端からデキューしている。

$ java QueueMachine
[] : 8
[8] : 1
[8, 1] : 9
[8, 1, 9] : -
[9, 7] : 3
[9, 7, 3] : 6
[9, 7, 3, 6] : *
[3, 6, 63] : +
[63, 9] : /
[7]

脚注

^ MSG (winuser.h) - Win32 apps | Microsoft Docs
^ Design Philosophy of Command Queues and Command Lists - Win32 apps | Microsoft Docs
^ Queue サービスを作成する | Microsoft Docs
^ 前田敦司:キューマシンモデルを用いた関数型言語の並列処理系、日本ソフトウェア科学会第13回大会報告集（1996年）
^ 前田敦司:キューマシンアーキテクチヤとその並列Lisp処理系への応用、第38回プログラミング・シンポジウム報告集（1997年）pp. 143-154
^ 前田敦司:新しい計算モデルキューマシンとその並列関数型言語への応用、情報処理学会論文誌38巻3号（1997年）pp. 574-583
^ 川田宗太郎・曽和将容:仮想キューマシンVQMの構成と基本性能評価、情報処理学会研究報告ハイパフォーマンスコンピューティング（HPC）38(2004-HPC-098)（2004年）pp. 31-36
^ 田中哲朗:プログラミングコンテスト実施報告、夏のプログラミングシンポジウム「プログラミングの鉄人一プログラミングの技」報告集（2001年）pp. 3-14
^ “夏のプログラミング・シンポジウム「プログラミングの鉄人 - プログラミングの技」”. 2002年8月9日時点のオリジナルよりアーカイブ。2025年10月28日閲覧。
^ 1000speakers用資料 - おびなたん☆ 2025年10月26日閲覧。
^ https://www.iijlab.net/~ew/fifol.html https://www.iijlab.net/~ew/sim.html https://www.iijlab.net/~ew/simulator.html 2025年10月26日閲覧。
^ 山口文彦:キューマシンにおける不動点プログラミング、日本ソフトウェア科学会第34回大会講演論文集（2017年）
^ 和田英一:万能FIFOL機械、第46回プログラミング・シンポジウム報告集（2005年）pp. 71-82
^ 大日向大地:SIMD拡張FIFOLを使った科学技術計算、夏のプログラミング・シンポジウム報告集（2005年）pp. 97-102

優先度付きキュー

キューの応用

キューマシン

脚注

関連項目