基本情報技術者 PR

【基本情報】スタックとキューってなに?どこで使われている?

記事内に商品プロモーションを含む場合があります

●この記事で学べること
・スタックとはなにか
・キューとはなにか

箱に入れたものを取り出す方法

今、箱にA,B,C,D,Eと書かれた物が入っています。これらの物達はA,B,C,D,Eの順番で箱に詰められました。

では、この物を箱から取り出す方法はいくつあるでしょうか?箱の側面をぶち抜けば、何通りでも考えれそうですが、コンピュータの世界では2つの方法で物を取り出します。その方法がスタックキューの2つです。

スタック

スタックとは、一番最後に入れた物を最初に取り出す方法です。上の箱の例で言うと、最後に入れたEから取り出し、続いてD,C,Bと取り出して、最後にAを取り出します。最後に入れたものを最初に取り出すので、Last In First OutでLIFOなんて言うこともあります。

日常にあるスタックと言えば、山積みにされた本ですね。一番最初に置かれた本は一番最後に取り出されます。

コンピュータの世界にあるスタックと言えば、Excelやブラウザにある戻るボタンです。戻るボタンを押すと、最後に持っていた情報を最初に表示します。2回押すと、最後から2番目の情報を表示します。最後の情報を最初に表示するのでスタックです。

キュー

キューとは、一番最初に入れた物を最初に取り出す方法です。箱の例で言うと、最初に入れたAから取り出し、続いてB,C,Dと取り出して、最後にEを取り出します。最初に入れたものを最初に取り出すので、First In First OutでFIFOなんて言うこともあります。

日常にあるキューと言えば、行列ですね。一番最初に並んだ人が一番最初にお店に入れます。

コンピュータの世界にあるキューと言えば、印刷機の印刷処理です。最初に印刷ボタンを押したファイルから印刷されるのでキューです。

プッシュとポップ

ちなみに、箱に物を入れる操作と箱から物を取り出す操作にも名前が付いています。

プッシュ・・・箱に物を入れる操作
ポップ ・・・箱から物を取り出す操作

基本情報技術者試験での出題例

令和元年度秋期問8

基本情報技術者
午前試験 令和元年度秋期問8

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

ア 1     イ 2     ウ 3     エ 4

正解と解説

正解は”ウ”

実際に検証しながら最小限必要なスタックの数を確かめましょう。

●スタックが1個の場合
最初にSをポップする必要があるのでSがプッシュされるまでひたすらプッシュを繰り返します。
・Aをプッシュ:{A}
・Cをプッシュ:{A,C}
・Kをプッシュ:{A,C,K}
・Sをプッシュ:{A,C,K,S}
やっとSが来たので、Sをポップします。
・Sをポップ :{A,C,K}<S>
次にTをポップする必要があるのでTが来るまでプッシュを繰り返します。
・Tをプッシュ:{A,C,K,T}<S>
Tが来たので、Tをポップします。
・Tをポップ :{A,C,K}<S,T>
次にポップしたいのはAですが、待機しているのはKなのでNGです。
よって、スタックが1個では無理でした。

●スタックが2個の場合
最初にSをポップする必要があるのでSが来るまでプッシュを繰り返します。Sをプッシュする手前の形は以下の4通りが考えれます。
①{A,C,K}&{}
②{A,C}&{K}
③{A,K}&{C}
④{A}&{C,K}

しかし、ポップする順番はS→T→A→C→Kです。つまり、AはCやKよりも先に取り出す必要があります。よってAの後ろにCやKが入っている①②③はこの時点でNGとなります。また、CはKよりも先に取り出す必要がありますが、④だとK→Cの順番でしか取り出せません。よって④もNGとなり、スタックが2個でも無理だと分かります。

●スタックが3個の場合
同じようにSをプッシュする手前の形を考えます。
①{A,C,K}&{}&{}
②{A,C}&{K}&{}
③{A,K}&{C}&{}
④{A}&{C,K}&{}
⑤{A}&{C}&{K}

Aよりも先にCとKが入っている①②③はNG、Cよりも先にKが入っている④はNGです。なので⑤だけに焦点を当てて続きを考えます。

次にプッシュするのはSですが、すぐにプルするのでどのスタックに入れても同じです。
⑥{A,S}&{C}&{K} → {A}&{C}&{K}<S>
⑥{A}&{C,S}&{K} → {A}&{C}&{K}<S>
⑥{A}&{C}&{K,S} → {A}&{C}&{K}<S>

次にプッシュするTもすぐにプルするのでどこに入れても⑦の状態になりますね。
⑦{A}&{C}&{K}<S,T>

あとは、A→C→Kの順番でそれぞれのスタックから取り出せば良いだけです。
⑧{}&{C}&{K}<S,T,A>
⑨{}&{}&{K}<S,T,A,C>
⑨{}&{}&{}<S,T,A,C,K>

よって、最小限必要なスタックの個数は3個です。

Sをプッシュする手前の形を漏れなく洗い出す方法
ここでは今回の問題のように考え得る状況を全て洗い出す方法について紹介します。

スタックが3個の場合のA,C,Kの入れ方を例に考えてみましょう。
今回の例ではスタックも文字も3つあります。なので各スタックに入る文字の数のパターンは以下の3通りしかありません。

①{3文字}&{0文字}&{0文字}
②{2文字}&{1文字}&{0文字}
③{1文字}&{1文字}&{1文字}

ここでのコツは左端のスタックに一番多く文字を入れることです。
左端のスタックに3文字入っている時、残りのスタックは必ず0文字になるので、①のパターンしか存在しないことが分かります。左端のスタックに3文字入っているパターンが分かったので、次は2文字入っているパターンを考えます。

左端のスタックに2文字入っている時、必ず片方は1文字、もう片方は0文字になるので、②のパターンしか存在しません。なので次は左端のスタックに1文字入っているパターンを考えます。

左端のスタックに1文字入っている時、残り2つのスタックに1文字ずつ入っているパターンAと片方に2文字、もう片方に0文字入っているパターンBの2つが考えられます。

パターンA:{1文字}&{1文字}&{1文字}
パターンB:{1文字}&{2文字}&{0文字}

しかし、左端のスタックに一番多く文字を入れるルールなのでパターンBは無視してOKです。実際、このパターンBを並び替えると、左端のスタックに2文字入れた時と全く同じ形になりますよね。パターンBは左端のスタックに2文字入れた時の検証で既に洗い出せているという訳です。

以上のことから各スタックに入っている文字数のパターンは以下の3つになります。

①{3文字}&{0文字}&{0文字}
②{2文字}&{1文字}&{0文字}
③{1文字}&{1文字}&{1文字}

では、ここに実際の文字を入れていきましょう。①と③は1通りしかありませんよね。
①{A,C,K}&{}&{}
③{A}&{C}&{K}

②のパターンは2文字と1文字のスタックがあります。どう考えれば漏れなくパターンを洗い出せるでしょうか。
ここでのコツは少ない文字数のスタックから決めてしまうことです。1文字のスタックはAの場合、Cの場合、Kの場合の3パターンしかないことがすぐに分かります。それぞれについて考えると以下の3パターンになります。

②-1{A}&{C,K}&{}
②-2{C}&{A,K}&{}
②-3{K}&{A,C}&{}

以上から、スタックが3個の場合のA,C,Kの入れ方は以下の5通りと分かります。
①{A,C,K}&{}&{}
②{A,C}&{K}&{}
③{A,K}&{C}&{}
④{A}&{C,K}&{}
⑤{A}&{C}&{K}

平成31年度春期問6

基本情報技術者
午前試験 
平成31年度春期問6

三つのスタックA,B,Cのいずれの初期状態もであるとき,再帰的に定義された関数ƒ()を呼び出して終了した後のBの状態はどれか。ここで,スタックが,[a1 a2,…,an-1]の状態のときにanをpushした後のスタックの状態は[a1 a2,…,an-1,an]で表す。

ƒ(){
Aが空ならば{
何もしない。
}
そうでない場合{
Aからpopした値をCにpushする。
ƒ()を呼び出す。
Cからpopした値をBにpushする。
}
}

ア [1,2,3,1,2,3]
ウ [3,2,1,1,2,3]

イ [1,2,3,3,2,1]
エ [3,2,1,3,2,1]

正解と解説

正解は”ア”

●初期状態
A  B  C

●ƒ()を呼び出す(1回目)
この時点でAは空ではありません。なのでAからpopした値をCにpushします。スタックなのでAは最後にpushした3をpopします。
A  B  C

ここで再度ƒ()を呼び出します。再度呼び出したƒ()の処理が完了した後、「Cからpopした値をBにpushする」という処理が残っていることを忘れないで下さい。

●ƒ()を呼び出す(2回目)
1回目と同じようにAからpopした値をCにpushします。
A  B  C

ここで再度ƒ()を呼び出します。注意点は1回目と同じです。

●ƒ()を呼び出す(3回目)
1回目と同じようにAからpopした値をCにpushします。
A[1]  B  C

ここで再度ƒ()を呼び出します。注意点は1回目と同じです。

●ƒ()を呼び出す(4回目)
Aが空なので何もせずに終了します。
A[]  B  C

ここで3回目のƒ()の続きに戻ります。

●ƒ()を呼び出す(3回目続き)
Cからpopした値をBにpushします。
A[]  B  C

ここで2回目のƒ()の続きに戻ります。

●ƒ()を呼び出す(2回目続き)
Cからpopした値をBにpushします。
A[]  B  C

ここで2回目のƒ()の続きに戻ります。

●ƒ()を呼び出す(1回目続き)
Cからpopした値をBにpushします。
A[]  B  C

これで処理は終了です。

平成30年度秋期問5

基本情報技術者
午前試験 
平成30年度秋期問5

待ち行列に対する操作を,次のとおり定義する。

ENQ n:待ち行列にデータnを挿入する。
DEQ:待ち行列からデータを取り出す。
空の待ち行列に対し,ENQ1,ENQ2,ENQ3,DEQ,ENQ4,ENQ5,DEQ,ENQ6,DEQ,DEQの操作を行った。次にDEQ操作を行ったとき,取り出されるデータはどれか。

ア 1
ウ 5

イ 2
エ 6

正解と解説

正解は”ウ”

待ち行列はいわゆるお店の行列のようにデータの挿入と取り出しを行います。なので先に挿入したデータを先に取り出すキュー構造となります。

それでは実際にデータの状態遷移を見てみましょう。

  1. ENQ 1:
  2. ENQ 2:
  3. ENQ 3:
  4. DEQ:[2,3]→1
  5. ENQ 4:[2,3,4]
  6. ENQ 5:[2,3,4,5]
  7. DEQ:[3,4,5]→2
  8. ENQ 6:[3,4,5,6]
  9. DEQ:[4,5,6]→3
  10. DEQ:[5,6]→4
  11. DEQ:[6]→5

最後に取り出されるのは5になるので、答えはウになります。

平成30年度春期問5

基本情報技術者
午前試験 
平成30年度春期問5

次の二つのスタック操作を定義する。
PUSH n:スタックにデータ(整数値n)をプッシュする。
POP:スタックからデータをポップする。
空のスタックに対して,次の順序でスタック操作を行った結果はどれか。

PUSH 1 → PUSH 5 → POP → PUSH 7 → PUSH 6 → PUSH 4 → POP → POP → PUSH 3

正解と解説

正解は”ウ”

スタックの状態は下図のように遷移します。

よって答えはウです。

平成29年度秋期問5

基本情報技術者
午前試験 
平成29年度秋期問5

A,B,C,Dの順に到着するデータに対して,一つのスタックだけを用いて出力可能なデータ列はどれか。

ア A,D,B,C
ウ C,B,D,A

イ B,D,A,C
エ D,C,A,B

正解と解説

正解は”ウ”

【アの検証】→[A,D,B,C]は出力可能?
●最初にAを出力するので、スタックしたAはすぐにプッシュします。
1.スタック{A} 出力[]
2.スタック{} 出力[A]

●次にDを出力するので、Dをスタックするまでスタックし続けます。
3.スタック{B} 出力[A]
4.スタック{B,C} 出力[A]
5.スタック{B,C,D} 出力[A]

●全てのデータをスタックしたので、後はプッシュするだけです。
6.スタック{B,C} 出力[A,D]
7.スタック{B} 出力[A,D,C] →この時点でアの形にはなりません。

【イの検証】→[B,D,A,C]は出力可能?
●最初にBを出力するので、Bをスタックするまでスタックし続けます。
1.スタック{A} 出力[]
2.スタック{A,B} 出力[]

●Bをスタックしたので、Bを出力します。
3.スタック{A} 出力[B]

●次にDを出力するので、Dをスタックするまでスタックし続けます。
4.スタック{A,C} 出力[B]
5.スタック{A,C,D} 出力[B]

●全てのデータをスタックしたので、後はプッシュするだけです。
6.スタック{A,C} 出力[B,D]
7.スタック{A} 出力[B,D,C] →この時点でイの形にはなりません。

【ウの検証】→[C,B,D,A]は出力可能?
●最初にCを出力するので、Cをスタックするまでスタックし続けます。
1.スタック{A} 出力[]
2.スタック{A,B} 出力[]
3.スタック{A,B,C} 出力[]

●Cをスタックしたので、Cを出力します。
4.スタック{A,B} 出力[C]

●次に出力するのはBなので、Bをプッシュします。
5.スタック{A} 出力[C,B]

●次にDを出力するので、Dをスタックするまでスタックし続けます。
5.スタック{A,D} 出力[C,B]

●全てのデータをスタックしたので、後はプッシュするだけです。
6.スタック{A} 出力[C,B,D]
7.スタック{} 出力[C,B,D,A] →ウの形になりました。

【エの検証】→[D,C,A,B]は出力可能?
●最初にDを出力するので、Dをスタックするまでスタックし続けます。
1.スタック{A} 出力[]
2.スタック{A,B} 出力[]
3.スタック{A,B,C} 出力[]
4.スタック{A,B,C,D} 出力[]

●全てのデータをスタックしたので、後はプッシュするだけです。
5.スタック{A,B,C} 出力[D]
6.スタック{A,B} 出力[D,C]
7.スタック{A} 出力[D,C,B] →この時点でエの形にはなりません。

よって、答えはウになります。