１．スタックとは
スタックは,最後の格納したデータを最初に取り出す後入れ先出し（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を，逆ポーランド表記法では１２３×+と表記します。
このとき、人間では柔軟に考えることができますが、プログラムには「柔軟に」という命令が出せません。
一つ一つの動作をロジカルに命令するしかないのです。
ここでは、変換前の配列（1＋2×3）を変換後の配列（１２３×+）に入れる際に、一時的な領域としてスタックを使っています。
詳細な動きはこの問題文に解説されていますが、簡略化すると
(1)変換前配列から１つずつ読み取る
(3)数字ならスタックにPush
(2)四則演算子ならスタックのデータをPopして変換後配列に追加、四則演算子をスタックにPush
(4)変換前配列が空になったら全てをPopして変換後配列に追加
※(3)と(2)は、流れに合わせて逆にしました。
２．スタックに関する過去問
（１）過去問（H21春FE午前問5 ）| 問5 関数や手続を呼び出す際に,戻り番地や処理途中のデータを一時的に保存するのに適したデータ構造はどれか。 ア 2分探索木 イ キュー ウ スタック エ 双方向連結リスト |
↓
↓
↓
↓
正解は、ウ
（２）H28春AP
問5 A，B，Cの順序で入力されるデータがある。各データについてスタックヘの挿入と取出しを1回ずつ行うことができる場合，データの出力順序は何通りあるか。
ア 3 イ 4 ウ 5 エ 6
↓
↓
↓
↓
↓
【正解】ウ
（３）H27春AP
問7 プログラムの実行に関する次の記述の下線部a～dのうち，いずれかに誤りがある。誤りの箇所と正しい字句の適切な組合せはどれか。自分自身を呼び出すことができるプログラムは，a再帰的であるという。このようなプログラムを実行するときは，bスタックに局所変数，c仮引数及び戻り番地を格納して呼び出し･復帰するときはdFIFO （First ln First Out）方式で格納したデータを取り出して復元する必要がある。
↓
↓
↓
↓
↓
【正解】エ
（４）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
コメント