応用情報処理技術者試験の対策サイトです。 応用情報処理技術者試験の午前問題を中心とした基礎用語の解説を中心に掲載します。書き始めたばかりなので、内容はまだまだ不十分です。
カテゴリ:

2.プログラミング > 2.1 スタックとキュー

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

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

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

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

ヒープ領域に関しては、IPAの資料が参考になります。
https://www.ipa.go.jp/security/awareness/vendor/programmingv2/contents/c007.html

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

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

IPAの資料にスタックに関する詳しい記載があります。
https://www.ipa.go.jp/security/awareness/vendor/programmingv2/contents/c006.html

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

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


【正解】ウ


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

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

問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 ケ です。

データ構造とは、データをどのように持つかという方法のことです。
配列やリスト、スタック、キュー、木構造などがあります。
応用情報技術者試験を勉強する成子 

なんでそんなに種類があるのですか?
それぞれ特徴があるからです。データがもし書き込んだらそれでおしまいであれば、データ構造をあまり気にする必要はありません。しかし、データというのは追加したり変更したり削除したりします。
また、データベースなどの検索が重要な場合に、高速に検索できる仕組みが求められます。
そういう観点で、データ構造は重要なのです。

基本情報技術者試験の過去問(H23春FE午後問11)の「出題趣旨」でも「プログラムの作成において,データ構造は実行時の特性に大きな影響を及ぼすので,適切なデータ構造を選択することは重要である。」とあります。

過去問を基に整理します。
スタック
「格納した順序とは逆の順序でデータを取り出すことができる構造である(H16春FE午前問43)」

キュー
「格納した順序でデータを取り出すことができる構造である(H16春FE午前問43)。」

リスト
「データ部と一つのポインタ部で構成されるセルをたどることによって,データを取り出すことができる構造である(H16春FE午前問43)」

木構造
「階層の上位から下位に節点をたどることによって,データを取り出すことができる構造である(H16春FE午前問43)」。

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

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

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

スタックは,最後の格納したデータを最初に取り出す後入れ先出し(LIFO:Last In First Out)のデータ構造です。
★あとでイメージ図を入れる

スタックにデータを挿入することをpush、スタックからデータを取り出すことをpopといいます。

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

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



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

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



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

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
正解は、

H18春FE午前
問12 空の状態のキューとスタックの二つのデータ構造がある。次の手続を順に実行した場合,変数xに代入されるデータはどれか。ここで,
データ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
正解は、イのbです。

実行結果を先に書きます。実際のプログラムは後半に記載します。
c:\pg>stack.exe
初期状態
スタックの状態:
キューの状態:

push(a) データ a をスタック(の最後)に挿入
スタックの状態:[a]
キューの状態:

push(b) データ b をスタック(の最後)に挿入
スタックの状態:[a][b]
キューの状態:

enq(pop()) スタック(の最後)からデータを取り出して、それをキュー(の最後)に挿

スタックの状態:[a]
キューの状態:[b]

enq(c) データ c をキュー(の最後)に挿入
スタックの状態:[a]
キューの状態:[b][c]

push(d) データ d をスタック(の最後)に挿入
スタックの状態:[a][d]
キューの状態:[b][c]

push(deq()) キュー(の先頭)からデータを取り出して、スタック(の最後)に挿入
スタックの状態:[a][d][b]
キューの状態:[c]

x = pop() スタック(の最後)からデータを取り出したデータを x とする
x の値: b
スタックの状態:[a][d]
キューの状態:[c]
続きを読む

スポンサードリンク

このページのトップヘ