一般的な、アルゴリズムの説明で出てくるスタックの概念

• スタック(Stack)：LIFO（Last-in First-out)なデータ構造
  • Push：データを１つスタックに格納する操作
  • Pop：スタックの一番上のデータを取り出す操作

（取り出したデータはスタックからは削除される）
例：

整数を保存できるスタックがあるとする（大きさは考えなくていいよ（溢れない））\\
 PUSH(1) 
 PUSH(5)
 POP
 PUSH(7)
 PUSH(6)
 PUSH(4)
 POP
 POP
 PUSH(3)

        | - | - | - | - | - | - |  空のスタック
​    　  | 1 | - | - | - | - | - |　Push(1)
　      | 5 | 1 | - | - | - | - |　Push(5)
    5 ← | 1 | - | - | - | - | - |　Pop
        | 7 | 1 | - | - | - | - |　Push(7)
        | 6 | 7 | 1 | - | - | - |　Push(6)
        | 4 | 6 | 7 | 1 | - | - |　Push(4)
    4 ← | 6 | 7 | 1 | - | - | - |　Pop
    6 ← | 7 | 1 | - | - | - | - |　Pop
        | 3 | 7 | 1 | - | - | - |  Push(3)　
        で最後はこうなるよ

• キュー(Que)：FIFO(First-in First-out)なデータ構造
  • en-que（エンキュー)：キューにデータを一個格納する操作
  • de-que（デキュー）：キューから１個データを取り出す操作

例：

 en-que(1) 
 en-que(5)
 de-que 
 en-que(7)
 en-que(6)
 en-que(4)
 de-que 
 de-que 
 en-que(3)

en-que | - | - | - | - | - | - |→ | - |  de-que
       | - | - | - | - | - | - |→ | 1 |       en-que(1)   
       | - | - | - | - | - | 5 |→ | 1 |       en-que(5)  
       | - | - | - | - | - | - |→ | 5 |　→1   de-que 
       | - | - | - | - | - | 7 |→ | 5 |       en-que(7) 
​       | - | - | - | - | 6 | 7 |→ | 5 |       en-que(6) 
​       | - | - | - | 4 | 6 | 7 |→ | 5 |       en-que(4) 
       | - | - | - | - | 4 | 6 |→ | 7 |  →5   de-que 
       | - | - | - | - | - | 4 |→ | 6 |  →7   de-que
       | - | - | - | - | 3 | 4 |→ | 6 |       en-que(4)

空の状態のキューとスタックの二つのデータ構造がある。
次の手続を順に実行した場合，変数xに代入されるデータはどれか。
ここで，
　データ y をスタックに挿入すること → push(y)
　スタックからデータを取り出すこと →→ pop()
　データ y をキューに挿入すること →→→ enq(y)
　キューからデータを取り出すこと →→→→ deq()
とそれぞれ表す。

　　　1.  push( a )
　　　2.  push( b )
　　　3.  enq( pop() )
　　　4.  enq( c )
　　　5.  push( d )
　　　6.  push( deq() )
　　　7.  *x* ← pop()

S| - | - | - | - | - | - |
Q| - | - | - | - | - | - |→ | - |

1．push( a )
S| a | - | - | - | - | - |
Q| - | - | - | - | - | - |→ | - |

2．push( b )
S| b | a | - | - | - | - |
Q| - | - | - | - | - | - |→ | - |

3． enq( pop() )
S| a | - | - | - | - | - |
Q| - | - | - | - | - | - |→ | b |

4． enq( c )
S| a | - | - | - | - | - |
Q| - | - | - | - | - | c |→ | b |

5． push( d )
S| d | a | - | - | - | - |
Q| - | - | - | - | - | c |→ | b |

6．push( deq() )
S| b | d | a | - | - | - |
Q| - | - | - | - | - | - |→ | c | →b
de-queしてSにpush

7． *x* ← pop()
b(pop)←S| d | a | - | - | - | - |
       Q| - | - | - | - | - | - |→ | c |

      x ← b
__答え）xにはbが代入される__