data-structures - 固定サイズのFIFOキューの正しい用語は何ですか？

Question

次のデータ構造の正しい名前は何ですか？それは：

• 固定サイズのキュー
• 新しい要素が先頭に追加されます
• キューが特定のサイズを超えると、いくつかの要素が最後から削除されます

Answer 1

「固定サイズのFIFOキュー」

バッファの場合もあれば、リングバッファの場合もあります（これが通常の実装方法です）。珍しいことではありませんが、アイテムをバッチで削除するための戦略を示すものは何も知りません。

Answer 2

循環バッファです

Answer 3

これの実際の実装に依存するかもしれないと思います。説明する内容の実際的な例は、バッファがいっぱいになると最も古いデータが新しいデータで上書きされる循環バッファまたはリングバッファです。これは、Cのようなものでそのようなデータ構造を実装する従来の方法の1つです。

編集：わかりました、それで循環バッファは完全に適合しません。有限バッファキュー、または有限容量キューはどうですか？しかし、それらは実際には自己制限的な側面をカバーしていません...

自己制限的な有限容量のブラットキュー。

自動ポップ...

私のポイントは、あなたが言及した正確なプロパティを持つデータ構造の正式な名前はないと思うので、それに最も近いデータ構造に基づいて、おそらくあなたの構造のいくつかと組み合わせて作成する方がよいということですユニークなプロパティ。それはおそらくかなり言葉になるでしょう...

編集：またはおそらくそれは循環キューです。記事はそれを次のように説明しています：

この記事では、バッファサイズが固定されていることを除けば、System.Collections.Queueと同様のキューについて説明します。もちろん、これは、キューに追加されたすべてのアイテムを保持するのに十分な大きさのバッファがないことを意味します。この場合、最も古いアイテムが削除されます。

...これはあなたのように聞こえます。素晴らしく、簡潔でもあります。

Answer 4

ハードウェアでは、同様の構造がシフトレジスタと呼ばれます。

Answer 5

組み込みシステムでは、これはほぼ一般的に循環バッファと呼ばれます。