Queue - tanakakenji/Rinko GitHub Wiki

イントロダクション

キュー（Queue）は、要素を線形に保持し、要素の追加（enqueue）は列の末尾（後端・背面・rearなど）、要素の削除（dequeue）は列の先頭（前端・frontなど）で行われるデータ構造です。一般的にFIFO（First In, First Out：先入れ先出し）方式で動作し、この名称は、現実の行列（例えばお店のレジ待ちなど）に並ぶ人々のイメージから来ています。

抽象データ型としてのキューは、配列や単方向リストを使って実装が可能です。
幅優先探索（Breadth-first search）は、しばしばキューを用いて実装されます。

学習リソース (Learning resources)

読み物

動画

実装 (Implementations)

言語 API
C++ std::queue
Java java.util.Queue を使用（java.util.ArrayDeque推奨）
Python queue モジュール
JavaScript N/A（標準のキュークラスはなし）

時間計算量 (Time complexity)

操作 Big-O
Enqueue / Offer O(1)
Dequeue / Poll O(1)
Front O(1)
Back O(1)
isEmpty O(1)

面接で注意すべき点 (Things to look out for during interviews)

多くの言語には、デフォルトで使えるキュークラスがありません。そのため、候補者は配列（JavaScript）やリスト（Python）をキューとして使おうとすることがあります。しかし、その場合、要素の削除（dequeue）が先頭で行われるとすると、すべての要素を1つ左に移動しなくてはならないため、削除操作が O(n) になってしまいます。実際の面接では、面接官に対して「効率的なdequeue操作を備えたキュー構造を想定している」と明確に伝えましょう。

コーナーケース (Corner cases)

  1. 空のキュー（要素数が0）
  2. 要素が1つだけのキュー
  3. 要素が2つだけのキュー

重要問題 (Essential questions)

このトピック（キュー）を学習する際、まず取り組むべき代表的な問題です。

  • Implement Stack using Queues

おすすめの練習問題 (Recommended practice questions)

上記の問題をクリアしたあと、さらに練習したい場合は以下もおすすめです。

  • Implement Queue using Stacks
  • Design Circular Queue
  • Design Hit Counter (LeetCode Premium)

キューは、コンピュータのCPUやOSの内部で、様々な重要な役割を果たしています。

キューの基本的な概念 キューは、コンピュータにおける基本的なデータ構造の一つで、データを先入れ先出し（FIFO: First In, First Out）のリスト構造で保持します[3][6][9].

  • データを入れることをエンキュー、取り出すことをデキューと言います[3].
  • 銀行や病院の待ち行列をイメージすると理解しやすいでしょう[6].

OSにおけるキューの利用

  • タスク管理とプロセスのスケジューリング: OSは、実行可能な状態のタスクを管理するために優先順位ごとにキューを使用します[6][15]. CPUのコアごとにスレッドの実行待ちキューがあり、準備ができたスレッドから順に実行されます[2]. タスク管理プログラムは、CPUがタスクの処理に使うことができる時間を割り当て、コンピュータシステムの効率的な利用を可能にします[11].
  • 割り込み処理: ハードウェアからの割り込み要求を処理するために、割り込み処理キューが使用されます。
  • I/O管理: OSは、キーボード、マウス、ディスプレイ、ハードディスクドライブなどの外部デバイスとのデータ送受信を制御するためにキューを使用します[14].
  • ジョブ管理: OS内のジョブ管理もキューを使って行われます[5].
  • 非同期タスクの実行: タスクをいったんキューに溜め込んでおき、後からタスクを取り出して非同期で実行する目的で使用できます[3].

CPUにおけるキューの利用

  • スレッドの実行待ち: CPUの各コアには、スレッドの実行待ちキューがあり、準備ができたスレッドから順に実行が開始されます[2].
  • ハードウェアフリップキュー: ハードウェアフリップキューは、OSの有効化/無効化ネゴシエーションのために使われます[4].

キューの種類

  • データキュー: OS内部のデータを管理する手法の一つとして使われています[7][16].
  • 両端キュー(deque): 先頭と末尾の両端から入出力を行えるキューです[3].

このように、キューはCPUとOSの内部で、タスクのスケジューリング、割り込み処理、I/O管理など、様々な処理を効率的に行うために広く利用されています。

Citations: [1] https://learn.microsoft.com/ja-jp/windows/win32/medfound/media-foundation-work-queue-and-threading-improvements [2] https://atmarkit.itmedia.co.jp/ait/articles/1410/30/news150_2.html [3] https://ja.wikipedia.org/wiki/%E3%82%AD%E3%83%A5%E3%83%BC_(%E3%82%B3%E3%83%B3%E3%83%94%E3%83%A5%E3%83%BC%E3%82%BF) [4] https://learn.microsoft.com/ja-jp/windows-hardware/drivers/display/hardware-flip-queue [5] https://www.scc-kk.co.jp/scc-books/wp-content/data/7392/9784886477392_sample.pdf [6] https://www.issoh.co.jp/tech/details/4587/ [7] https://www.tron.org/ja/onwebseminar/glossary/ [8] https://jpwinsup.github.io/blog/2022/07/15/Performance/SystemResource/PerformanceCounterProcessor/ [9] https://zenn.dev/antez/books/568dd4d86562a1/viewer/531a45 [10] https://www.tron.org/ja/onwebseminar/chap3/ [11] https://jeea.or.jp/course/contents/12106/ [12] https://www.youtube.com/watch?v=KPwAZqthwfY [13] https://www.japacom.co.jp/blog/toda/p2/2-3.shtml [14] https://qiita.com/_mi/items/e71ecf4b4db169165286 [15] https://fielddesign.jp/technology/rtos/rtos_kernel/ [16] https://solid.kmckk.com/SOLID/doc/latest/user_guide/rtos_viewer.html [17] https://www.kumikomi.jp/rtos_beginner2/ [18] https://qiita.com/minimabot/items/ea60998c181d7bc8785f [19] https://qiita.com/yokoto/items/a2536bd1b81b42479bba [20] https://itmanabi.com/queue-stack/