カテゴリ:2.ソフトウェア > 2.1 スタックとキュー

 

1.スタック領域とヒープ領域

メモリ領域にはいくつかの種類があります。
その中で、スタック領域とヒープ領域について簡単に違いを理解しておきましょう。
過去問(H26秋AP問15)では、「プログラムの実行時に利用される記憶領域にスタック領域とヒープ領域がある」として、「サブルーチンからの戻り番地の退避にはスタック領域が使用され,割当てと解放の順序に関連がないデータの格納にはヒープ領域が使用される。」とあります。

以下は、H26秋SC午後1問1の過去問から引用しています。
こんな風にわかれているんだなぁと、雰囲気だけつかんでください。

メモリ領域
応用情報技術者試験を勉強する成子 

なぜ、領域が分かれているのですか?
メモリを使用する変数において、サイズが明確なものと、そうでないものがあるからです。
①明確なもの
変数の値やアドレスなどのサイズがわかっている値を格納する際は、スタック領域を使います。
高速に処理できます。
②動的にメモリを確保するもの
たとえば、ファイルを読み込む際には、ファイルサイズがわからないので、ヒープ領域を使います。自由度が高いですが、ポインタなどでアドレスを参照する必要があり、同じ物理メモリでありながら、スタックよりも低速になります。
また、プログラムで不要な領域を解放することも可能なので、メモリ領域を効率よく使うことが可能。メモリサイズが小さいときは、スタック領域を大きくなりすぎないようにする工夫をしたりします。
⇒一方、メモリを解放しないと、使用効率が悪くなるので、ガーベジコレクションが必要です。
 

sm.seeeko.com

 ヒープ領域に関しては、IPAの資料が参考になります。

www.ipa.go.jp

2.メモリ領域の過去問を解いてみよう

(1)H26秋AP

問15 プログラムの実行時に利用される記憶領域にスタック領域とヒープ領域がある。それらの領域に関する記述のうち,適切なものはどれか。
ア サブルーチンからの戻り番地の退避にはスタック領域が使用され,割当てと解放の順序に関連がないデータの格納にはヒープ領域が使用される。
イ スタック領域には未使用領域が存在するが,ヒープ領域には未使用領域は存在しない。
ウ ヒープ領域はスタック領域の予備領域であり,スタック領域が一杯になった場合にヒープ領域が動的に使用される。
エ ヒープ領域も構造的にはスタックと同じプッシュとホップの操作によって,データの格納と取出しを行う。





イ:ヒープ領域は未使用領域が存在します。
ウ:ヒープ領域とスタック領域は別々の用途で利用され、予備領域という概念はありません。

【正解】ア

リスト構造に関して、以下の過去問(平成17年春期 FE 午後 問1)を見てみましょう。

問1 リストに関する次の記述を読んで,設問1~3に答えよ。

リストの構造は図1のとおりとする。
17-FE問1-1
(1)ROOTは,リストの先頭を指す。
(2)リストの要素は連続する2語からなる。第1語には値が,第2語には次の要素へのポインタが格納されている。
(3)リストの各要素は値の昇順に連結されていて,値はすべて異なる。最後の要素の第2語にはポインタとして0000が格納されている。
(4)図1の構造をもつリストが,図2のとおりに主記憶の00FF番地から0117番地までに格納されている。00FF番地はROOTである。
(5)1語は16ビットからなり,語単位で番地が付いている。
17-FE問1-2



設問1 010C番地の内容として正しい答えを,解答群の中から選べ。

解答群
ア 0099  イ 00A1  ウ 00A3  エ 00A4  オ 00A5






【正解】イ

設問2 次の記述中の[   ]に入れる正しい答えを,解答群の中から選べ。

 0110番地及び0111番地からなる要素をリストから削除するには,[ a ]番地の内容を[ b ]に変えればよい。

解答群
ア 0101  イ 0102  ウ 0103  エ 0104  オ 0105
カ 0113  キ 0114  ク 0115  ケ 0116  コ 0117






【正解】
a コ  
b イ

設問3 次の記述中の[   ]に入れる正しい答えを,解答群の中から選べ。

 0118番地から011D番地に格納されている3要素からなるサブリストと,設問2で要素を削除する前のリストを併合するには,[ c ]番地の内容を011Aに,[ d ]番地の内容を0102に,[ e ]番地の内容を011Cに,[ f ]番地の内容を0108にそれぞれ変えればよい。

解答群
ア 0109  イ 010B  ウ 010D  エ 010F  オ 0111
力 0113  キ 0115  ク 0117  ケ 0119  コ 011B






【正解】
c オ
d コ
e キ
f ケ

 

1.データ構造とは

(1)データ構造
プログラムによる処理においては、プログラムをどういう手順で実行するかという「アルゴリズム」と、データをどのように持つかという「データ構造」が重要です。
データ構造には、配列やリスト、スタック、キュー、木構造などがあります。
応用情報技術者試験を勉強する成子 

なんでそんなに種類があるのですか?
それぞれ特徴があるからです。データがもし書き込んだらそれでおしまいであれば、データ構造をあまり気にする必要はありません。しかし、データというのは追加したり変更したり削除したりします。
また、データベースなどの検索が重要な場合に、高速に検索できる仕組みが求められます。
そういう観点で、データ構造は重要なのです。
の上位から下位に節点をたどることによって,データを取り出すことができる構造である(H16春FE午前問43)」。

2.静的データ構造と動的データ構造

データの領域割り当てという観点でみると、データ構造は以下に分けられます。
(1)静的データ構造
メモリ領域が、固定で割り当てられる。そして、プログラムが終了するとデータ領域が開放される。
①配列
 たとえば、生徒の点数の結果だけを配列に入れます。
 a(6)={21,5,53,71,3,17} 
 この配列を並べ替えたり、平均点を計算するなどのプログラムが考えられます。
 データを1つずつ、
 a1=21、a2=5、a3=53などと定義してもプログラムとしては処理ができますが、面倒ですよね。

②構造体
 c言語の場合、structで定義されます。
 構造体は、データ型などを自由に設定できます。たとえば、生徒の名前、学籍番号、英語の点数、国語の点数、などなど。それぞれ入力される値が数字(int)だったり日本語(char)だったり、いろいろです。それらを定義して、データベースのように扱うことができます。

(2)動的データ構造
データの都度、メモリ領域が変更される。
①リスト構造
・リスト構造は、データ部とポインタ部で構成される。ポインタ部にはアドレスが入る。
・過去問では、「データ部と一つのポインタ部で構成されるセルをたどることによって,データを取り出すことができる構造である(H16春FE午前問43)」

②木構造
・過去問では、「階層の上位から下位に節点をたどることによって,データを取り出すことができる構造である(H16春FE午前問43)」。
以下に少しだけ詳しく解説しています。
http://sm.seeeko.com/archives/15876927.html

■メモ過去問を例に
基本情報技術者試験の過去問(H23春FE午後問11)の「出題趣旨」でも「プログラムの作成において,データ構造は実行時の特性に大きな影響を及ぼすので,適切なデータ構造を選択することは重要である。」とあります。データ構造へのデータの格納および取り出しの順番として、FIFO(First In First Out)とLIFO(Last In First Out)があります。
キューのデータ構造では、FIFO
スタックのデータ構造では、LIFOが使われます。

過去問を基に整理します。
(1)スタック
「格納した順序とは逆の順序でデータを取り出すことができる構造である(H16春FE午前問43)」
(2)キュー
「格納した順序でデータを取り出すことができる構造である(H16春FE午前問43)。」
→スタックやキューは、配列やリスト構造を用いたもの。(静的データ構造、動的データ構造のどちらにもなりうる(らしい)) ★要調査

3.データ構造の過去問を解いてみよう

(1)H17秋FE午前

問13 データ構造に関する記述のうち,適切なものはどれか。
ア 2分木は,データ間の関係を階層的に表現する木構造の一種であり,すべての節が二つの子をもつデータ構造である。
イ スタックは,最初に格納したデータを最初に取り出す先入れ先出しのデータ構造である。
ウ 線形リストは,データ部と次のデータの格納先を指すポインタ部から構成されるデータ構造である。
エ 配列は,ポインタの付替えだけでデータの挿入・削除ができるデータ構造である。





【正解】ウ

(2)H19春AD午前問34

問34 データ構造の特徴のうち,適切なものはどれか。
ア 配列は,添字によってデータを任意の順序で読み出すことができる。
イ 配列を用いることによって,データ構造とアルゴリズムを独立させることができる。
ウ リストは,添字によってデータの検索や更新ができる。
エ リストは,データの挿入や削除のときに既存のデータを移動する必要がある。





【正解】ア

(3)H18SW春午前

問9 データ構造に関する記述のうち,B木の説明として適切なものはどれか。
ア ある特定のアルゴリズムに従って,レコードのキー値から物理的な格納アドレスを求めてレコードを格納する。
イ 索引部の各ノートのキー値を中心にして,小さい側のレコード数と大きい側のレコード数の比率が,ある範囲内に収まるように動的に再配置しながら格納する。
ウ レコードの物理的配置とは独立に,論理的にレコードをつなぐポインタによって,レコードを関係づけて格納する。
エ レコードをキー値の昇順にしてトラックなどのアクセス単位(ページ)ごとに格納し,各ページ内の最大キー値とそのページの番地をもつ索引を作る。





【正解】ウ

 

1.スタックとは

スタックは,最後の格納したデータを最初に取り出す後入れ先出し(LIFO:Last In First Out)のデータ構造です。
★あとでイメージ図を入れる
IPAの資料にスタックに関する詳しい記載があります。
https://www.ipa.go.jp/security/awareness/vendor/programmingv2/contents/c006.html

スタック領域は必ずスタックです。ヒープ領域は、どこからでも自由にデータにアクセスできるから、スタックなどにおけるLIFOなどの概念がありません。
スタックにデータを挿入することをpush、スタックからデータを取り出すことをpopといいます。

応用情報技術者試験を勉強する成子

FIFOとかpushとかpopとか、複雑なことをしますね。
メリットはあるのですか?



プログラムを書く上で、便利なときがあります。
過去問(H25春AP午後問2)を例に考えます。
http://sm.seeeko.com/archives/15877021.html

これは、一般的な表記法の数式を逆ポーランド表記法に変換するプログラムのアルゴリズムです。
たとえば、1+2×3を,逆ポーランド表記法では123×+と表記します。
このとき、人間では柔軟に考えることができますが、プログラムには「柔軟に」という命令が出せません。
一つ一つの動作をロジカルに命令するしかないのです。
ここでは、変換前の配列(1+2×3)を変換後の配列(123×+)に入れる際に、一時的な領域としてスタックを使っています。
詳細な動きはこの問題文に解説されていますが、簡略化すると
(1)変換前配列から1つずつ読み取る
(3)数字ならスタックにPush
(2)四則演算子ならスタックのデータをPopして変換後配列に追加、四則演算子をスタックにPush
(4)変換前配列が空になったら全てをPopして変換後配列に追加
※(3)と(2)は、流れに合わせて逆にしました。

2.スタックに関する過去問

(1)過去問(H21春FE午前問5 )
問5 関数や手続を呼び出す際に,戻り番地や処理途中のデータを一時的に保存するのに適したデータ構造はどれか。
ア 2分探索木
イ キュー
ウ スタック
エ 双方向連結リスト





 正解は、ウ

(2)H28春AP

問5 A,B,Cの順序で入力されるデータがある。各データについてスタックヘの挿入と取出しを1回ずつ行うことができる場合,データの出力順序は何通りあるか。
H28h-問5
ア 3     イ 4     ウ 5     エ 6





【正解】ウ

(3)H27春AP

問7 プログラムの実行に関する次の記述の下線部a~dのうち,いずれかに誤りがある。誤りの箇所と正しい字句の適切な組合せはどれか。

 自分自身を呼び出すことができるプログラムは,a再帰的であるという。このようなプログラムを実行するときは,bスタックに局所変数,c仮引数及び戻り番地を格納して呼び出し・復帰するときはdFIFO (First ln First Out)方式で格納したデータを取り出して復元する必要がある。
H27h-問7





 【正解】エ

(4)H18春FE午前

問12 空の状態のキューとスタックの二つのデータ構造がある。次の手続を順に実行した場合,変数眉こ代入されるデータはどれか。ここで,
データyをスタックに挿入することをpush(y),
スタックからデータを取り出すことをpop(),
データyをキューに挿入することをenq(y),
キューからデータを取り出すことをdeq() ,
とそれぞれ表す。

push(a)
push(b)
enq(pop())
enq(c)
push(d)
push(deq())
x←pop()

ア a  イ b  ウ c  エ d
以下の記事で、実際のプログラムを含めて解説しています。
http://sm.seeeko.com/archives/15877013.html

↑このページのトップヘ