データをメモリに一時的に保持する仕組みとして、スタックとキューがあります。
今回はスタックとキューについて説明します。
スタックは先入れ後出し、キューは先入れ先出し方式でデータを保持します。
例えば、a,b,cの順番でデータを投入する場合、スタックはc,b,a、キューはa,b,cの順番でデータが取りだされます。
なお、スタックにデータを入れる操作はプッシュ、スタックからデータを取り出す操作はポップ、キューにデータを入れる操作はエンキュー、キューからデータを取り出す操作はデキューと呼びます。
以下、イメージ図です。
・スタック
・キュー
スタックが使われる代表的な場面としては、関数呼び出し時に戻り先を保持する場面が挙げられます。
例えば、以下のような構造になっている場合
f() {
g() //①
}
g() {
h() //②
}
h() {
}
関数g()が呼び出された時点でスタックに①のアドレス、関数h()が呼び出された時点でスタックに②のアドレスが戻り先として保持されます。
そして、関数h()が終了した時点でスタックから戻り先として②のアドレスが取り出され、関数g()が終了した時点でスタックから戻り先として①のアドレスが取り出されます。
余談ですが、以下のように再帰呼び出しになっている時は注意が必要です。
ループ終了条件を満たさないまま大量の再帰呼び出しを行った場合、戻り先アドレスのサイズがスタックのサイズを超えてしまい、プログラムが異常終了してしまいます。
f() {
ループ {
f()
}
}
キューが使われる代表的な場面としては、マルチスレッドの制御を行う場面が挙げられます。
１つのスレッドの処理が「①軽い処理→②重い処理」となっており、かつ①の処理を先に行ったスレッドが②の処理を先に行う必要がある場合、①と②の間にキューを入れて対応します。
①の処理は処理が終わるごとにキューの中にスレッドのオブジェクトを格納し、②の処理は処理が終わる毎にキューの中のスレッドのオブジェクトを取り出し次の処理に移ることで、①の処理と②の処理の速度差を吸収することができます。
----------------------
目次
