トークン管理アルゴリズム

Question

私はトークンのプールを持っています（数字1-N）。プロセスはトークンを処理することができます。プロセスにトークンがある間、他のプロセスはそのトークンを取得できません。しかし、しばらくすると、トークンの有効期限が切れ、その後は無料になります。たとえば、トークン1〜10があります。プロセスAがトークン1を取得し、プロセスBがトークン2を取得した。トークン2の有効性が期限切れになった。いくつかの時間の後にトークン配列に空きがあり、使用可能なトークンを検索するための空きとinorderとしてのトークンだけがあります。完全な配列を検索する必要があります。どのデータ構造/アルゴリズムが問題を最適に解決するために使用するか

Answer 1

リンクリスト番号ごとに1つのノードでリストを初期化します。トークンを割り当てる必要がある場合は、リストから頭を削除します。トークンの有効期限が切れたときにリストに戻します。リスト内のトークンは徐々に乱れますが、それはあなたの問題には関係ありません。（私はあなたが最小のトークンを入手する必要はないと仮定します）