問題
三つのスタック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」が正解です。