InfraAcademy Blog

文字を出力するために最小限必要となるスタックは何個か | 基本情報過去問解説

公開日: 2021-10-15 更新日: 2026-09-01 | #基本情報技術者試験 #過去問解説

Linux・ネットワーク・AWSを、環境構築なしで実践学習できます

こんにちは、フルスタックエンジニアのryuです。

今回は、基本情報技術者試験の過去問から、スタックを使って文字を並べ替える問題を解説します。

スタックは、基本情報技術者試験でよく出てくるデータ構造の一つです。「LIFOは覚えているけど、実際にデータが動くと分からなくなる」という方も多いと思います。

今回の問題も、スタックの意味だけを暗記していると少し難しく感じます。ただ、どの文字がスタックの一番上にあるのかを順番に考えていけば、それほど難しい問題ではありません。

また、現在の基本情報技術者試験では、科目Bでスタックやキューなどのデータ構造を擬似言語で扱うことがあります。そのため、「スタック＝LIFO」と覚えるだけではなく、PUSHやPOPによってデータがどう変化するのかまで理解しておくことが大切です。

この記事では、過去問を解きながら、スタックの基本、なぜ答えが3個になるのか、科目Bの擬似言語でスタックが出たときの考え方まで順番に解説します。

文字を出力するために最小限必要となるスタックは何個か¶

今回はこちらの問題です。

A，C，K，S，Tの順に文字が入力される。スタックを利用して，S，T，A，C，Kという順に文字を出力するために，最小限必要となるスタックは何個か。ここで，どのスタックにおいてもポップ操作が実行されたときには必ず文字を出力する。また，スタック間の文字の移動は行わない。

ア：1 イ：2 ウ：3 エ：4 出典：令和元年秋期問8

答えは、ウの3個です。

「A、C、K、S、Tと入力されるのに、なぜS、T、A、C、Kという順番で取り出すために3個も必要なの？」と思いますよね。

答えを考える前に、まずスタックの仕組みを確認しましょう。

スタックとは？¶

スタックとは、データを一時的に保存するためのデータ構造の一つです。

特徴は、最後に入れたデータから先に取り出すことです。

これを、

後入れ先出し（LIFO：Last In First Out）

と呼びます。

スタックの構造

引用：スタック – Wikipedia

スタックは、箱や本を積み重ねるイメージで考えると分かりやすいです。

例えば、A、B、Cという3つのデータを順番に入れます。

最初

[   ]

Aを入れる

[ A ]

Bを入れる

[ B ]
[ A ]

Cを入れる

[ C ]
[ B ]
[ A ]

一番上にあるのはCです。

この状態からデータを取り出すと、

C → B → A

という順番になります。

Aを最初に入れていますが、Aの上にBとCが積まれているため、Aを先に取り出すことはできません。

この性質が、今回の問題を解く一番重要なポイントです。

PUSHとPOPを覚えよう¶

スタックでは、データを入れる操作をPUSH、取り出す操作をPOPと呼びます。

例えば、

PUSH(A)
PUSH(B)
PUSH(C)

とすると、スタックは次の状態になります。

上
C
B
A
下

ここで、

POP()

すると、取り出されるのはCです。

もう一度POPするとB、その次はAです。

操作	スタックの状態	取り出した値
PUSH(A)	A	-
PUSH(B)	B, A	-
PUSH(C)	C, B, A	-
POP()	B, A	C
POP()	A	B
POP()	空	A

科目Bでは、PUSHやPOPという名前がそのまま出てくる場合もあれば、配列と変数を使ってスタックの処理が実装されている場合もあります。

そのため、「PUSHは入れる」「POPは取り出す」という意味だけではなく、最後にPUSHされたものが最初にPOPされることまで理解しておきましょう。

今回の問題を解いてみよう¶

それでは、今回の問題を実際に考えてみます。

入力される順番は、

A → C → K → S → T

です。

一方、出力したい順番は、

S → T → A → C → K

です。

最初に入力されるA、C、Kは、すぐには出力できません。

最初に出力したいのはSだからです。

そのため、A、C、Kはいったんスタックへ保存しておく必要があります。

ここから「何個のスタックが必要なのか」を考えていきます。

スタックが1個の場合¶

まず、スタックが1個しかない場合を考えてみましょう。

A、C、Kが順番に入力されるので、そのままPUSHすると次の状態になります。

上
K
C
A
下

そのあとSが入力されます。

SをPUSHして、すぐにPOPすればSを出力できます。

スタックのデータの流れ1

次にTも同じです。

TをPUSHしてすぐにPOPすれば、2文字目のTを出力できます。

スタックのデータの流れ2

ここまでは、

S → T

と正しく出力できています。

問題はこのあとです。

次に出力したい文字はAです。

しかし、スタックの中は、

上
K
C
A
下

となっています。

Aを取り出すためには、その上にあるKとCを先にPOPしなければなりません。

今回の問題では、POPした文字は必ずそのまま出力されます。

つまり、Aを取り出そうとすると、

K → C → A

という順番になってしまいます。

欲しい順番は、

A → C → K

なので、これではダメです。

スタックのデータの流れ3

つまり、スタック1個では実現できません。

スタックが2個でも足りない理由¶

では、スタックを2個に増やしたらどうでしょうか。

ここが今回の問題で少し考えるところです。

A、C、Kを2個のスタックに分ける必要があります。

しかし、3文字を2個のスタックへ入れるので、どちらか一方のスタックには必ず2文字以上が入ります。

例えば、

スタック1：A、C
スタック2：K

とすると、スタック1ではAのあとにCが入るため、

上
C
A
下

となります。

AよりCを先に取り出さなければならなくなります。

しかし、出力したいのは、

A → C → K

です。

AとCを同じスタックへ入れることはできません。

では、

スタック1：A、K
スタック2：C

ならどうでしょうか。

Aの上にKが乗るので、Aより先にKを取り出さなければなりません。これもダメです。

スタック1：A
スタック2：C、K

も、Cの上にKが乗るため、

K → C

の順番になってしまいます。

つまり、A、C、Kのうち2文字を同じスタックへ入れると、入力された順番とは逆の順番でしか取り出せません。

そのため、スタック2個でも足りません。

スタックが3個なら実現できる¶

そこで、A、C、Kをそれぞれ別のスタックへ入れます。

スタック1：A
スタック2：C
スタック3：K

これなら、どの文字もそれぞれのスタックの一番上にあります。

Sが入力されたら、空いているスタックへPUSHしてすぐPOPします。

スタックのデータの流れ4

Tも同じようにPUSHしてPOPします。

スタックのデータの流れ5

これで、

S → T

まで出力できました。

あとは、それぞれのスタックから、

A
C
K

の順番でPOPすればよいだけです。

スタックのデータの流れ6

結果は、

S → T → A → C → K

となり、問題文で指定された順番と一致します。

したがって、最小限必要なスタックは、

3個

です。

なぜ「3個」が最小なのかを整理する¶

今回の問題は、「3個ならできる」だけではなく、2個ではできないことまで考える必要があります。

ポイントは、A、C、Kの出力順です。

入力も、

A → C → K

出力も、

A → C → K

です。

つまり、この3文字については入力された順番を維持したまま出力しなければなりません。

しかし、同じスタックへ2文字入れると、その2文字の順番は逆になります。

例えば、

PUSH(A)
PUSH(C)

なら、

POP() → C
POP() → A

です。

AをCより先に出したいのに、逆になってしまいます。

したがって、A、C、Kは同じスタックへ重ねることができず、1文字ずつ別々のスタックへ保存する必要があります。

この考え方ができると、「なんとなく3個」ではなく、なぜ2個ではダメで、3個必要なのかまで説明できます。

スタックとキューの違い¶

スタックと一緒に出てきやすいのがキューです。

どちらもデータを一時的に保存するデータ構造ですが、取り出す順番が逆です。

	スタック	キュー
取り出し方	後入れ先出し	先入れ先出し
英語	LIFO	FIFO
入れる操作	PUSH	enqueue
取り出す操作	POP	dequeue
イメージ	積み重ねた本	レジの行列

例えば、

A → B → C

の順番で入れた場合、

スタックなら、

C → B → A

キューなら、

A → B → C

の順番で取り出されます。

FIFOとLIFOの文字だけを暗記すると混乱しやすいので、実際にA、B、Cを入れたときにどうなるかまで考えられるようにしておくと分かりやすいです。

科目Bではスタックが擬似言語として出てくる¶

今回の問題は旧試験制度の過去問ですが、スタックそのものは現在の基本情報技術者試験でも重要です。

現在の科目Bでは、データ構造やアルゴリズムを擬似言語で読み、処理の流れや変数の変化を追う力が求められます。

例えば、スタックの処理が次のような形で表されることがあります。

整数型の配列: stack
整数型: top ← 0

push(value)
    top ← top + 1
    stack[top] ← value

pop()
    value ← stack[top]
    top ← top - 1
    return value

最初はコードが増えて難しく見えるかもしれません。

ただ、見るべきポイントはそれほど多くありません。

この例なら、

stack：データを保存している配列
top：現在のスタックの一番上
push：データを入れる
pop：一番上のデータを取り出す

という意味です。

擬似言語のスタックをトレースしてみよう¶

例えば、次の処理を実行するとします。

push(10)
push(20)
push(30)
pop()
pop()

値の変化を表にすると、次のようになります。

操作	top	スタック	POPした値
初期状態	0	空	-
push(10)	1	10	-
push(20)	2	10, 20	-
push(30)	3	10, 20, 30	-
pop()	2	10, 20	30
pop()	1	10	20

10 → 20 → 30の順番でPUSHしていますが、POPされるのは、

30 → 20

です。

最後に入れた30から取り出されているので、LIFOになっていることが分かります。

科目Bでスタックが出てきたときは、頭の中だけで処理しようとせず、

top
スタックの中身
取り出した値

を書き出してみるのがおすすめです。

スタックの問題でよくある間違い¶

スタックの問題では、いくつか間違えやすいところがあります。

PUSHした順番のまま取り出せると思ってしまう¶

例えば、

PUSH(A)
PUSH(B)
PUSH(C)

としたら、

A → B → C

と取り出せるように感じることがあります。

しかし、スタックはLIFOなので、

C → B → A

です。

PUSHした順番とPOPされる順番は逆になります。

一番下のデータを直接取り出そうとする¶

スタックでは、基本的に一番上のデータだけを取り出します。

例えば、

C
B
A

と積まれている状態で、いきなりAだけをPOPすることはできません。

まずC、次にBを取り出す必要があります。

今回の過去問も、この性質を理解しているかがポイントになっています。

スタックとキューを混同する¶

「先に入れたものから取り出す」のはキューです。

「最後に入れたものから取り出す」のがスタックです。

迷ったら、

スタック → 本を積む
キュー → 行列に並ぶ

とイメージしてみてください。

スタックはどんなところで使われる？¶

スタックは試験問題のためだけのデータ構造ではありません。

実際のプログラムでもさまざまなところで使われています。

例えば、

関数の呼出し
再帰処理
式の評価
元に戻す処理
深さ優先探索

などです。

特に科目Bを勉強していると、再帰処理とスタックがつながってくることがあります。

関数を呼び出したあとに元の処理へ戻れるのも、呼出し元の情報をスタックのような形で管理しているからです。

最初はそこまで深く考えなくても大丈夫ですが、スタックを単なる「LIFOという試験用語」ではなく、プログラムを動かすうえで実際に使われる仕組みとして理解すると覚えやすくなります。

Giji Academyでスタックや擬似言語を実践的に学ぶ¶

スタックは、説明を読んでいるとそれほど難しくありません。

しかし、科目Bで擬似言語として出てくると、

「topが今いくつなのか」「どの値が一番上なのか」「このPOPでは何が返されるのか」

を同時に追う必要があります。

ここで苦手になる方は多いと思います。

Giji Academyでは、基本情報技術者試験の科目Bに必要な擬似言語を、ブラウザ上で実行しながら学習できます。

変数、条件分岐、繰返し、配列、トレースなどの基礎から、スタックやキューを含むデータ構造、探索・整列アルゴリズムまで段階的に学べます。

今回のスタック問題が難しかった場合も、いきなり難しい問題を何問も解く必要はありません。

まずは、

変数
↓
配列
↓
繰返し
↓
トレース
↓
データ構造

という順番で進めると、擬似言語を追いやすくなります。

「LIFOの意味は分かるけど、コードになると分からない」という方は、実際に擬似言語を動かして値の変化を確認してみてください。

Giji Academyで科目Bの擬似言語を学ぶ

登録不要で無料体験できます。

過去問解説まとめ¶

今回の記事では、次の問題を解説しました。

A，C，K，S，Tの順に文字が入力される。スタックを利用して，S，T，A，C，Kという順に文字を出力するために，最小限必要となるスタックは何個か。ここで，どのスタックにおいてもポップ操作が実行されたときには必ず文字を出力する。また，スタック間の文字の移動は行わない。

ア：1
イ：2
ウ：3
エ：4

出典：令和元年秋期問8

答えは、ウの3個です。

今回のポイントは、