ホームに戻る
出典 :
キュー (コンピュータ) - Wikipedia 優先度付きキュー - Wikipedia スタック - Wikipedia
関連 :
[C++]コンテナ [.NET]コレクション
目次 :

キュー、スタックの概要

集合を扱う基本的なデータ構造で、データを 先入れ先出し(First In First Out) または 後入れ先出し(Last In First Out) のリスト構造で保持するもの。
C++(STL)などのモダンなプログラミング言語では、キュー・スタック構造を用いるためのデータ型が用意されている場合が多い。
画像

キュー(Queue / FIFO / 待ち行列)

データを 入力された順番通りに(旧いものから順に) 処理する必要がある場合に用いる。
イベント駆動型のプログラムにおいては、イベント(メッセージ)を受け取る側は(特殊な場合を除き)メッセージを受けた順に処理することとなるため、処理待ちのメッセージをプールしておく場として「メッセージキュー」を用いるのが通例である。
(メッセージ発行時点で別のメッセージが処理中であっても、キューにメッセージを入れておけば、順番が巡れば処理される。)

優先度付きキュー

エンキューする要素に優先度を付与し、(追加順ではなく)優先度に基づいてキュー内でソートする。結果として 最も優先度の高いものからデキューされる

リングバッファ

固定長領域を用いたキューの実装。データ領域(固定長配列)、書き込み位置、読み出し位置で構成される。
領域の末尾と先頭を疑似的に結合し、書き込み・読み出し位置が領域の末尾に達したら先頭まで巻き戻す。
構造が簡単で、バッファ(キュー)領域を動的に拡大・縮小することなく継続的に領域を再利用できるため、メモリに限りがあり、かつ長期間継続的にデータが追加されるような用途に適している。
(ドライブレコーダの映像保存⇒外部記憶に書き出し、など。)
画像

スタック(Stack / LIFO)

データを 入力された順番と逆順で(新しいものから順に) 処理する必要がある場合に用いる。

コールスタック

プログラムでサブルーチン(割り込み含む)が呼ばれた場合、最後に呼ばれたもの(最も内側)から順に戻ることになる。
このためコンピュータ上では、戻り先のアドレス(およびローカル変数と引数)をスタック形式(コールスタック)で保持している。コールスタックの上端(次の戻り先)を指すレジスタをスタックポインタと呼ぶ。
プログラムの実行に当たっては、メモリ(主記憶)は(ヒープとして確保する以外は)コールスタック(およびグローバル変数)に用いられることから、
ヒープ領域を除いたメモリをスタック領域と呼ぶ。特にメモリに限りがある組み込み用途では、スタックの使用量を見積もることが重要である。
転じて、「呼び出し階層」の意味でも用いられる。(「コールスタックが深い」など)