キューとスタックのコレクションはありますか？

Question

FIFOまたはLIFOコレクション（基本的にはpush、pop、front/back）が必要な場合、Rustではどうすればよいですか？ C++のstd::queueやstd::stackのようなもの。

Answer 1

まず、錆はが要素を追加するための保証レイテンシのいずれかのライブラリが（標準ライブラリに）提供していません最悪の場合。

• スタックはVecの上又はLinkedListいずれかで実装することができる（いずれもpop_backとpush_backが備わり）
• キューのいずれかに実装されてもよい：言われ、それぞれの場合のための2つの候補が存在すること

  VecDeque又はLinkedListの上に（両方の機能pop_frontとpush_back）

差分Vec*とLinkedListの間には、後者が単純であることがあります。push_backを呼び出すたびにメモリが割り当てられます。一方で、これは、push_backのコストが既にコレクション内の要素の数とは無関係であることを意味するため、これは素晴らしいことです。一方で、メモリ割り当てには本当に時間がかかることがあります。

前者は少し複雑です：

• それはより多くのキャッシュフレンドリー
• さのおかげで、それは限り余分な容量があるように、非割り当てpush_backを保証し、追加の容量を持ち、優れたスループットを持っています
• それはまだは前もって

余剰能力を確保いない場合でも、 O（1） push_backを償却維持

一般的には、スタックにはVec、キューにはVecDequeを使用することをお勧めします。

Answer 2

両方VecDequeとLinkedListはpush/pop _ front/backを持っています。錆のコレクションに新しい要素を追加する際、一般的にメモリを割り当てることができ、メモリを割り当てることは、時間の無制限の量を取ることがあります。