情報処理技術者試験/応用情報技術者試験/200904_平成21年春/問18回答 - 豚吐露＠wiki

---

ア

---

【スタック】
stack
データ構造の一つであるリストの中で、特に挿入、削除がリストの先頭からしかできないものである。このような構造は、LIFO（後入れ先出し）と呼ばれる。

スタックは、例で言えば、机上に積み上げられた本のような構造をしている。
本は上に積み上げられていき、読みたい本は上から順に取っていかなければ取れないという点が、スタックと似ている。

スタックは、情報処理のさまざまな場面に欠かせないデータ構造であるといえる。
プログラムがサブルーチンを実行後に呼び出し元に戻る仕組みには、スタックが使われる。
サブルーチンを実行する前に、スタックに戻り先を積み上げ(PUSH)、サブルーチンが処理を終わると、戻り先、つまり次にプログラムを実行する番地を取り出す(POP)。
文書編集操作の『やり直し』や『元にもどす』などもスタックを利用して実現されているのが一般的である。

【ヒープ】
heap
OSやアプリケーションソフトが使用するメモリ領域の一種。用途に関係なく自由に確保することができる。

OSからはヒープメモリを確保した位置のアドレスが渡され、アプリケーションソフトはこの値を元にして確保したヒープ領域を使用する。
ヒープメモリはアプリケーション側での自由度が高い反面、ガーベジコレクション機能がないプログラミング言語(の処理系)では、確保したヒープをすべて手作業で解放しなければならないため、誤解放や解放漏れなどのミスが起こりやすい。
このヒープの解放漏れが「メモリリーク」である。

---

スタック領域には未使用領域が存在するが、ヒープ領域には未使用領域は存在しない。

⇒ スタックもヒープも確保された段階では未使用です。

ヒープ領域はスタック領域の予備領域であり、スタック領域が一杯になった場合にヒープ領域が動的に使用される。

⇒ スタックとヒープは全く別の領域であり、用途も全く違います。

ヒープ領域も構造的にはスタックと同じプッシュとポップの操作によって、データの格納と取出しを行う。

⇒ スタックはpush/popのList構造だが、ヒープはheap treeによって管理されている。管理方法は全く異なる。heap treeはrootに最小値が来るように配置された双方向リスト構造。

---

更新日： 2009年12月09日 (水) 17時54分19秒