I wonder if 'queues' like this are the reason people still stand as close as possible to each other in queues. In some locations this is not a case at all, while in others you will always have somebody breathing down your neck.
These comments stink. Maybe the name of the data structure stinks.
Anyway I was confused by the comment about starvation. I thought a friendless element should always be making progress toward the front batch even if there's regress in terms of how many items are in front of it. This is unlike a priority queue which can starve an element indefinitely by things coming in at the same rate they're processed.
Then I realized the error in my thinking: new elements can be added to the front batch while it is currently being processed. So the front batch can starve all later batches indefinitely.
You could prohibit adding to the current batch I suppose, without complicating the data structure too much.
It's a queue placed on an area they own on a daily basis as the Israelis bypass them. Old, sick, young? Yes you'll stand in the heat to school, hospital, friends, family, work, shops.
