問題
三つのスタックA，B，Cのいずれの初期状態も[1，2，3]であるとき，再帰的に定義された関数f()を呼び出して終了した後のBの状態はどれか。ここで，スタックが，[a1 a2，…，an-1]の状態のときにanをpushした後のスタックの状態は[a1 a2，…，an-1，an]で表す。
f(){
Aが空ならば{
何もしない。
}
そうでない場合{
Aからpopした値をCにpushする。
f()を呼び出す。
Cからpopした値をBにpushする。
}
}
- ア：[1，2，3，1，2，3]
- イ：[1，2，3，3，2，1]
- ウ：[3，2，1，1，2，3]
- エ：[3，2，1，3，2，1]
基本情報技術者平成31年春期 午前問6
問題
A，C，K，S，Tの順に文字が入力される。スタックを利用して，S，T，A，C，Kという順に文字を出力するために，最小限必要となるスタックは何個か。ここで，どのスタックにおいてもポップ操作が実行されたときには必ず文字を出力する。また，スタック間の文字の移動は行わない。
ア：1 イ：2 ウ：3 エ：4
基本情報技術者令和元年秋期 午前問8
データ構造の1つであるスタックとキュー、その仕組みはシンプルで簡単です。ただし 基本情報技術者試験では、スタックとキューを応用した問題で出題されることが多く難しく感じます。
本記事では、スタックとキューについて図解で分かりやすく解説していきます。
本記事で学べること
- スタックとキューの動きを理解
- 基本情報技術者試験の過去問の解き方を学ぶ
目次
スタック（Stack）
スタック（英：stack）とは、データ構造（※配列のように複数のデータを格納できる入れ物）の1つで、入ってきたデータを順番に格納し、取り出す時は最後に格納したデータから取り出す後入れ先出し（LIFO：Last-In First-Out）方式のデータ構造です。
上記はスタックのイメージ例です。スタックに入れる時は順番に格納していき、スタックから取り出す時は最後に格納したデータから順番に取り出します。
スタックにデータを追加する操作を「PUSH」（プッシュ）、スタックからデータを取り出す操作を「POP」（ポップ）といいます。
スポンサーリンク
キュー（Queue）
キュー（英：queue）とは、データ構造（※配列のように複数のデータを格納できる入れ物）の1つで、格納したデータから順に取り出す先入れ先出し（FIFO：First-In First-Out）方式のデータ構造です。
上記はキューのイメージ例です。キューに追加するときは末尾に追加し、キューから取り出す時は先頭のデータから順番に取り出します。
キューにデータを追加する操作を「enqueue」（エンキュー）、キューからデータを取り出す操作を「dequeue」（デキュー）といいます。
基本情報技術者試験 過去問の解説
基本情報技術者平成31年春期 午前問6
問題
三つのスタックA，B，Cのいずれの初期状態も[1，2，3]であるとき，再帰的に定義された関数f()を呼び出して終了した後のBの状態はどれか。ここで，スタックが，[a1 a2，…，an-1]の状態のときにanをpushした後のスタックの状態は[a1 a2，…，an-1，an]で表す。
f(){
Aが空ならば{
何もしない。
}
そうでない場合{
Aからpopした値をCにpushする。
f()を呼び出す。
Cからpopした値をBにpushする。
}
}
- ア：[1，2，3，1，2，3]
- イ：[1，2，3，3，2，1]
- ウ：[3，2，1，1，2，3]
- エ：[3，2，1，3，2，1]
基本情報技術者平成31年春期 午前問6
この問題は、A、B、Cのスタックに次の値が格納されている状態で、関数f()を呼び出して終了した後のスタックBの状態が解答のア～エのどれにあてはまるかという問題です。
A [1, 2, 3]
B [1, 2, 3]
C [1, 2, 3]
(1) 1回目の関数f() 実行 Aからpopした値をCにpush
はじめに関数f()を呼び出します。
Aは空ではないので「Aからpopした値をCにpushする。」を実行します。(Aから3を取り出し、Cに追加する）
(2) 2回目の関数f()実行 Aからpopした値をCにpush
「f()を呼び出す。」を実行して、関数f()を呼び出します。
Aは空ではないので再び「Aからpopした値をCにpushする。」を実行します。(Aから2を取り出し、Cに追加する）
(3) 3回目の関数f()実行 Aからpopした値をCにpush
「f()を呼び出す。」を実行して、関数f()を呼び出します。
Aは空ではないので再び「Aからpopした値をCにpushする。」を実行します。(Aから1を取り出し、Cに追加する）
(4) 3回目の関数f()の続き Cからpopした値をBにpush
「f()を呼び出す。」を実行して、関数f()を呼び出します。
Aは空なので「何もしない」で終了。3回目の関数f()に戻り「Cからpopした値をBにpushする。」を実行します。(Cから1を取り出し、Bに追加する）
(5) 2回目の関数f()の続き Cからpopした値をBにpush
2回目の関数f()に戻り「Cからpopした値をBにpushする。」を実行します。(Cから2を取り出し、Bに追加する）
(6) 1回目の関数f()の続き Cからpopした値をBにpush
1回目の関数f()に戻り「Cからpopした値をBにpushする。」を実行します。(Cから3を取り出し、Bに追加する）
関数f()の処理は終了です。結果はスタックBは[1, 2, 3, 1, 2, 3]となり「ア」が正解です。
基本情報技術者令和元年秋期 午前問8
問題
A，C，K，S，Tの順に文字が入力される。スタックを利用して，S，T，A，C，Kという順に文字を出力するために，最小限必要となるスタックは何個か。ここで，どのスタックにおいてもポップ操作が実行されたときには必ず文字を出力する。また，スタック間の文字の移動は行わない。
ア：1 イ：2 ウ：3 エ：4
基本情報技術者令和元年秋期 午前問8
この問題はスタックに「A，C，K，S，T」の順に追加（PUSH）し「S，T，A，C，K」の順に取り出す（POP）には、スタックが最低何個必要かという問題です。
解答はスタックの数が1～4なので、1から順番に考えてみます。
スポンサーリンク
スタックの数が1つの場合
「A，C，K，S，T」の順にスタックに「PUSH」します。
- push A → [A]
- push C → [A, C]
- push K → [A, C, K]
- push S → [A, C, K, S]
「S，T，A，C，K」の順に取り出したいので「POP」します。
- pop [A, C, K] → S
残りの「T」をスタックに「PUSH」します。
- push T → [A, C, K, T]
「S，T，A，C，K」の順に取り出したいので再び「POP」します。
- pop [A, C, K] → T（出力の順：S, T）
- pop [A, C] → K（出力の順：S, T, K）
[S, T, A]ではなく[S, T, K]になってしまうので、スタック1つでは設問の順に取り出すことはできない。
スタックの数が2つの場合
「A，C，K，S，T」の順にスタックに「PUSH」します。
- push A → stack1[A] stack2[]
- push C → stack1[A] stack2[C]
- push K → stack1[A] stack2[C, K]
- push S → stack1[A, S] stack2[C, K]
- push T → stack1[A, S] stack2[C, K, T]
「S，T，A，C，K」の順に取り出したいので「POP」します。
- stack1からpop：stack1[A] → S
- stack2からpop：stack2[C, K] → T（出力の順：S, T）
- stack1からpop：stack1[] → A（出力の順：S, T, A）
- stack2からpop：stack2[C] → K（出力の順：S, T, A, K）
[S, T, A, C]ではなく[S, T, A, K]になってしまうので、スタック2つでは設問の順に取り出すことはできない。
スタックの数が3つの場合
「A，C，K，S，T」の順にスタックに「PUSH」します。
- push A → stack1[A] stack2[] stack3[]
- push C → stack1[A] stack2[C] stack3[]
- push K → stack1[A] stack2[C] stack3[K]
- push S → stack1[A, S] stack2[C] stack3[K]
- push T → stack1[A, S] stack2[C, T] stack3[K]
「S，T，A，C，K」の順に取り出したいので「POP」します。
- stack1からpop：stack1[A] → S
- stack2からpop：stack2[C] → T（出力の順：S, T）
- stack1からpop：stack1[] → A（出力の順：S, T, A）
- stack2からpop：stack2[] → C（出力の順：S, T, A, C）
- stack3からpop：stack3[] → K（出力の順：S, T, A, C, K）
「S，T，A，C，K」の順番で取り出すことができたので、最低スタックが3つあれば設問の順に取り出すことができる。「ウ」の「3」が正解です。
基本情報技術者試験おすすめの参考書・問題集
| いちばんやさしい 基本情報技術者 | 『基本情報技術者試験』試験に、短期間で一発合格するための試験対策本。ITの知識がまったくない、未経験者やでもスラスラと学習を進められるよう、丁寧に解説。 |
| かやのき先生の基本情報技術者教室 | 基本情報技術者をめざす方のためのやさしいオールインワンタイプの参考書＆問題集。イラストや豊富な図解・例え話を駆使して理解しやすく・記憶に残りやすいように説明。 |
| 基本情報技術者 パーフェクトラーニング過去問題集 | 科目A・Bともに万全の対策ができる、定番の過去問題集！科目A・科目Bの両方について万全の対策ができる。 |
| キタミ式イラストIT塾 基本情報技術者 | すべての解説をイラストベースで行っているため，とてもわかりやすい解説本。いちばん最初に読む基本情報技術者試験関連の書籍を探している人におすすめ！ |
| 出るとこだけ！基本情報技術者［科目B］ | 基本情報技術者【科目Ｂ】対策の定番書！前提知識＋解き方＋試験問題を掲載。効率よく学習できる。 |
| 基本情報技術者 合格教本 | 出題範囲を体系的にきちんと理解しながら学習したい人におすすめ！基本情報技術者試験の定番テキストの改訂版。 |
| 基本情報技術者 超効率の教科書＋よく出る問題集 | 動画でスムーズに学習スタート、テキストでしっかり理解度を深める！よく出る問題を反復学習することで、合格に直結するチカラが身に付く！ |