Stackを使ってQueueを作る

有名な話かと思ったら意外と知られていなかったのでメモ。
FILOを使ってFIFOを作るとも言います。StackでQueue作れてもQueueでStackを作る方法が思いつかないので誰か教えて下さい。もしくはこういう学問があったら紹介して頂けると嬉しいです。

簡単な説明としては、2つのStackを用意して、enqueueするときには1つ目にpush()し、dequeueするときには2つ目からpop()するだけ。
ただし2つ目のStackが空の場合は1つ目のスタックが空になるまで2つ目のスタックに移し替える。

template<typename T>
class MyQueue {
  std::stack<T> in, out;
  MyQueue(){}
  
  void enqueue(const T& v) {
    in.push(v);
  }

  T dequeue() {
    if (out.empty()) {
       if (in.empty()) {
         throw std::exception("Queue is empty!");
       }
       while (!in.empty()) {
         out.push(in.top());
         in.pop();
       }
    }
    T result = out.top();
    out.pop();
    return result;
  }
};

図に書くとこんな感じ。

実際にデータを貯めてみる。enqueue(1);enqueue(2);enqueue(3);

Stackなので最初に入れたデータが一番底に沈む。
ここからdequeueしてみる。out側のstackが空なのでin側から持って来る必要がある。

これでout側のstackを見るとあら不思議、最初に入れたものがStackの一番上に。これをpop()すればdequeueできる。