基本情報技術者試験 2006年度 = 平成18年度・春期 午前 問12

 空の状態のキューとスタックの二つのデータ構造がある。次の手続を順に実行した場合、変数x に代入されるデータはどれか。ここで、
 データ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

解答



解説

 スタック(stack)は、データを後入れ先出し(LIFO = Last-In First-Out)で蓄えます。ちょうど、机の上に重ねた皿のように、最も上に重ねた皿を優先的に取り出すのと同様です。
 キュー(queue)は、データを先入れ先出し(FIFO = First-In First-Out)で蓄えます。ちょうど、銀行の待ち行列のように、より早く到着して待っているお客さんから、優先的に手続きが行われるのと同様です。

 まずaをプッシュします(左図はキュー、右図はスタックです)。

           a            ↓   │ │     ┐ ┌   ├─┤     ├─┤   │ │     │ │   ├─┤     ├─┤   │ │     │ │   ├─┤     ├─┤   │ │     │ │   ├─┤     ├─┤   │ │     │a│   └─┘     └─┘

 続いてbをプッシュします。

           b            ↓   │ │     ┐ ┌   ├─┤     ├─┤   │ │     │ │   ├─┤     ├─┤   │ │     │ │   ├─┤     ├─┤   │ │     │b│   ├─┤     ├─┤   │ │     │a│   └─┘     └─┘


 スタックから取り出したbを、キューにエンキューします。

    ←  b ←    ↓       ↑   │ │     ┐ ┌   ├─┤     ├─┤   │ │     │ │   ├─┤     ├─┤   │ │     │ │   ├─┤     ├─┤   │ │     │ │   ├─┤     ├─┤   │b│     │a│   └─┘     └─┘

 キューにcをエンキューします。

   c    ↓   │ │     ┐ ┌   ├─┤     ├─┤   │ │     │ │   ├─┤     ├─┤   │ │     │ │   ├─┤     ├─┤   │c│     │ │   ├─┤     ├─┤   │b│     │a│   └─┘     └─┘

 スタックにdを、プッシュします。

           d            ↓   │ │     ┐ ┌   ├─┤     ├─┤   │ │     │ │   ├─┤     ├─┤   │ │     │ │   ├─┤     ├─┤   │c│     │d│   ├─┤     ├─┤   │b│     │a│   └─┘     └─┘

 キューから取り出したbを、スタックにプッシュします。

         →              ↓   │ │  ↑  ┐ ┌   ├─┤     ├─┤   │ │     │ │   ├─┤  b  ├─┤   │ │     │b│   ├─┤     ├─┤   │ │  ↑  │d│   ├─┤     ├─┤   │c│     │a│   └─┘     └─┘    ↓   ↑      → 

 スタックからポップして得られる値はとなります。

           b            ↑   │ │     ┐ ┌   ├─┤     ├─┤   │ │     │ │   ├─┤     ├─┤   │ │     │ │   ├─┤     ├─┤   │ │     │d│   ├─┤     ├─┤   │c│     │a│   └─┘     └─┘


BohYoh.comトップページへ