スタックでキューを作る

先日見かけて、面白かったのでメモ。
enque用、deque用のstackを２つ用意して実現できる。

template<typename T>
class Queue {
  std::stack<T> in, out;

  void enq(const T& v) { in.push(v); }

  T deq() {
    if (out.empty()) {
       if (in.empty()) throw "Empty";
       while (true) {
         if (in.empty()) break;
         out.push(in.top());
         in.pop();
       }
    }

    T res = out.top();
    out.pop();
    return res;
  }
};