キュー（Queue）：先に並んだものから
FIFO（先入れ先出し）という約束 — 素朴な実装の罠とリングバッファ、BFS・タスク処理での使いどころ、C・Java・C#・Python での書き方
キューとは：レジ待ちの行列
キューは「後ろに並ぶ」と「先頭から出る」だけができる入れ物です。レジ待ちの行列と同じで、後から来たものが先頭に割り込むことはできません。追加を enqueue、取り出しを dequeue と呼びます。
enqueue(40) dequeue() -> 10 | ^ v | 後ろ +------+------+------+------+ 先頭 ----> | 40 | 30 | 20 | 10 | ----> +------+------+------+------+ FIFO: First-In, First-Out（先入れ先出し）
先に入れたものが先に出てくる規律を FIFO（First-In, First-Out：先入れ先出し）と呼びます。スタックとの違いは出口の位置だけです — スタックは入り口と出口が同じ端、キューは反対の端にあります。
素朴な配列実装の罠と、リングバッファ
配列でキューを作るとき、先頭から取り出すたびに残りの要素を全部ずらすと、取り出しに O(n) かかってしまいます。Array と List のページで見た「配列は先頭への操作が苦手」が、そのまま現れるのです。
そこで使われるのがリングバッファ（循環バッファ）です。先頭の位置と末尾の位置を指す 2 つの添字を持ち、取り出しは先頭の添字を 1 つ進めるだけ、追加は末尾の添字の位置に書いて 1 つ進めるだけです。添字が配列の端まで来たら 0 に戻って、一周します。
リングバッファ: 添字が端まで来たら 0 に戻って一周する index: 0 1 2 3 4 +------+------+------+------+------+ | | 20 | 30 | 40 | | +------+------+------+------+------+ ^ ^ head tail dequeue: head を 1 進めるだけ -> O(1) enqueue: tail の位置に書いて 1 進めるだけ -> O(1) 添字 4 の次は 0 へ（配列を円環とみなす）
「ずらす」作業が消えたので、追加も取り出しも O(1) になりました。満杯になったときは、動的配列と同じ発想で、より大きい配列を確保して詰め直します。
どこで使われているか
「来た順に処理する」あらゆる場面で使われます。幅優先探索（BFS）は「近い場所から順に調べる」ためにキューを使います — 行けるだけ深く進む DFS がスタックだったのと、きれいに対になっています。
実務では、タスクキュー・ジョブスケジューラ・メッセージキュー（システム間の連携）・入力バッファなど、「受け取る速さと処理する速さが違うもの同士をつなぐ緩衝材」として至るところにあります。
変種も重要です。両端から出し入れできるものを両端キュー（Deque：デック）、並んだ順ではなく優先度の高いものから出てくるものを優先度付きキュー（priority queue）と呼びます。
各言語での書き方：C・Java・C#・Python
C の例
/* C: リングバッファを自作する */ int queue[8]; int head = 0, tail = 0; void enqueue(int v) { queue[tail] = v; tail = (tail + 1) % 8; } int dequeue(void) { int v = queue[head]; head = (head + 1) % 8; return v; }
C ではリングバッファを自作します。head / tail の 2 つの添字と剰余演算（%）だけで「一周」が書けます（満杯・空の検査は省略しています）。
Java の例
// 定石: Queue インターフェース + ArrayDeque 実装 Queue<String> queue = new ArrayDeque<>(); queue.offer("a"); // 後ろに並ぶ queue.offer("b"); String head = queue.poll(); // "a" — 先に並んだものから出る // ArrayDeque の中身はリングバッファ: // Object[] elements; int head; int tail; // 満杯になるとより大きい配列に詰め直す（動的配列と同じ発想）
Java の Queue はインターフェースで、追加は offer、取り出しは poll、先頭を覗くだけなら peek です。標準の実装は ArrayDeque — 中身はまさに上で見たリングバッファで、Object 型の配列と head / tail の 2 つの添字を持ち、満杯になるとより大きい配列に詰め直します。
LinkedList も Queue を実装しています（双方向連結リストなので両端の操作は O(1)）が、Array と List のページで見たキャッシュの事情（連続した配列のほうが速い）から、ArrayDeque を選ぶのが定石です。優先度付きキューには PriorityQueue を使います — 中身はヒープという木構造で、次のページで見るツリーの親戚です。
C# の例
// C#: Queue<T> クラス（中身はリングバッファ） var queue = new Queue<string>(); queue.Enqueue("a"); // 後ろに並ぶ queue.Enqueue("b"); string head = queue.Dequeue(); // "a" — 先に並んだものから出る
C# の Queue<T> も中身はリングバッファです。Enqueue / Dequeue という名前で、概念そのままに使えます。
Python の例
# Python: list.pop(0) は O(n) の罠 — collections.deque を使う from collections import deque queue = deque() queue.append("a") # enqueue queue.append("b") head = queue.popleft() # "a" — O(1) で先頭から取り出す
Python で list の pop(0) を使うと O(n) の罠にはまります。標準の collections.deque（両端キュー）を使えば、popleft が O(1) です。
まとめ
キューは enqueue / dequeue だけの入れ物。規律は FIFO（先入れ先出し）。
配列で素朴に作ると取り出しが O(n) — リングバッファ（head / tail の 2 つの添字＋一周）が両方を O(1) にする。
BFS・タスク処理・メッセージキューなど、「来た順に処理する」場面の標準部品。
Java の ArrayDeque も C# の Queue<T> も中身はリングバッファ。Python は collections.deque（list.pop(0) は O(n) の罠）。C では自作する。