C++の基本的なスタックとキューにはどのデータ構造が最適ですか？

Question

私はC++で初心者のHackerRankの問題をやっていますが、私はこの問題を解決する方法がいくつかあるようですが、どの方法が最も広く使われているか、最も効率的であるか疑問に思っています。問題は、stackとqueueの両方の変数と、stack_push/stack_popとqueue_push/queue_popの関数を含むクラスを作成する必要があります。

から私は私がstd::vector、std::stackとstd::queue、またはstd::deque、そしておそらく他の人を使用することができますどちらかと思われるGoogleで検索した内容。

どちらを使用するのが最適かを判断する方法がわかりません。助言がありますか？

EDIT： 私は両方のためstd::vectorを用いて実装した後、std::queueと共にstd::stackを使用して、私は小風テストケースの両方と全く同じ性能を見ました。 EDIT2： 非常に大きなテストケースの場合、のように、std:stack/std:queueのように見えます。私はこれがベクトルキューで効率的でないFIFOキューのためだと推測していますが、これをさらにテストする必要があります。

Answer 1

std::stackは、基礎容器としてstd::dequeを使用します。それでstd::queueもそうです。 http://en.cppreference.com/w/cpp/container/stackと

http://en.cppreference.com/w/cpp/container/queue参照ページ

template< 
    class T, 
    class Container = std::deque<T> 
> class stack; 

コンテナから参照してください - 基本となる容器の種類が 要素を格納するために使用します。コンテナは、 SequenceContainerの要件を満たしている必要があります。さらに、標準のコンテナstd :: vector、std :: dequeおよびstd :: list は、これらの要件を満たすために、 関数に通常のセマンティクスを使用する必要があります。back（）push_back（）pop_back（）

状況が許すならば、私は、根本的な細部を気にせずにstd::stackまたはstd::queueを使用します。私がもっとコントロールしなければならない場合は、std::dequeを選択します。

Answer 2

サムルールは、まずすべての要件を識別し、すべての要件を満たしている最も単純なデータ構造を使用します。検索要件がないので、Cスタイルのリンクリストを実装するのが最善の方法です。スタックの場合、フロント要素へのポインターは1つだけ必要ですが、キューの場合は、フロント要素と最後の要素を追跡するために2つのポインタを維持する必要があります。これはおそらく最速の実装になります。