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できる。