データ構造(スタックとキュー)に関する世界観です。
データ構造 | 意味 |
---|---|
スタック | 最後に入れたものが最初に取り出される。 どんどん上に重ね、上から取る。 スタックにデータを積む操作をプッシュ、取り出す操作をポップという。 |
キュー | 最初に入れたものが最初に取り出される。 列に並んで、最初に並んだ人から順に待機する。 キューに入れる操作をエンキュー、取り出す操作をデキューという。 |
(Ruby Way 第2版 (Professional Ruby Series)を参考に執筆しました。)
メッセージキューも参照のこと。
スタックとキューは、さまざまな場面で使われます。
特に、スタックは非常に一般的で、たとえばカッコを処理する際に、最後に開いたカッコが最初に閉じたカッコに対応します。
このように、「最後が最初に対応する」という場面は、意外と多く、そのため、スタックはさまざまな用途に使われます。
一方キューについては、カーネルのような低レベルレイヤーやプリンターのようなデバイス処理の中で、サブシステム同士を繋ぐインターフェースとして使うことが多いです。
特に、効率的な処理と非効率的な処理が一緒になる時に、非同期で処理をやり取りするような場合に、キューは使われることが多いです。
たとえば、Linuxのファイルシステムの中の、ダーティビットが付けられたi-nodeを順次書き込むために使われる、I/Oリクエストキューなどがこれに当たります。
そのように、スタックやキューはわりとよく使われます。配列や連結リストやツリーなど、単純なデータ構造よりも、少し癖のある形で使われるので、習得や理解は難しいですが、それらのデータ構造と同じぐらいよく使われるデータ構造だと言えます。
2023.07.28
Perl, PHP, Python, Rubyなどでは、リストに対してポップやプッシュなどのスタックやキューとしての操作を行うことができる。
Perl、PHP(言語)、Python(データ構造)、Ruby(基本)などを参照のこと。
2023.09.05
以下の書籍を参考に執筆しました。