キュー

出す側と取る側を切り離す

後回しにした処理を、どこに置いておくかが問題になります。

置き場所がキューです。出す側は置くだけ、取る側は取るだけで、互いを待ちません。

予約の処理はメールの送信を待たず、キューに置いて次の予約へ進みます。

置き場所としては同じです。違うのは入り口に上限があることです。

上限が無いと、取る側が詰まったときに置き場所がいくらでも膨らみます。メモリを使い切ってから気づくことになります。

溢れたら断る

上限に達したら、新しいものは入れません。断ります。

# 入れる場所が3つ、すでに3つ入っている
# 4つ目 → 断る

断った件数を数えておくと、取る側が足りていないことが数字で分かります。

種類によります。位置情報のように新しいものだけが要るなら、古いのを捨てます。

予約の確認メールはどれも捨ててはいけないので、断って呼び出し側に判断させます。捨ててよいかどうかは、置くものの性質で決まります。

演習

出し入れの操作の並びと上限を受け取り、取れたもの・断ったもの・残りを返します。

1. put は、入っている数が capacity より少ないときだけ末尾に入れる。いっぱいなら item を rejected へ入れる
2. take は先頭から取り出して taken へ入れる。空なら何も取らず empty_takes を1増やす
3. remaining は最後に残っているものを先頭から並べたリスト