The Israeli queue. Like a regular queue, but if something new that comes in sees its friend in the queue already, it can jump the queue and go and stand next to her. Useful for when something has a big overhead on top of its own processing, but the overhead can be shared between several similar entries. If you're doing it anyway for the one already in the queue, you get to make the most of it for its friends too. I c…
Reminds me a little bit of a "delta queue" used in efficient discrete time based scheduling, for example, in an OS scheduler. Imagine you want to implement a scheduler that accepts jobs and runs them at some point in the future. Instead of keeping a list and scanning through the list at each clock tick, implement a linked list with (time delta, job) at each node. Now, handling a tick() simply requires decrementing the head node and popping items until you see a non-zero delta. Inserting is done like a normal list, except as you iterate through the list, you decrement the desired time interval as you see deltas in the list. It goes like this:
insert(job1, 1) # (job1, 1) -> null insert(job2, 1) # (job1, 1) -> (job2, 0) -> null insert(job3, 2) # (job1, 1) -> (job2, 0) -> (job3, 1) -> null tick() -> job1, job2 # (job3, 0) -> null tick -> job3 # -> null