Ну вот о чем-то подобном и приходили мысли, после чего появилась идея вообще отказаться от этого списка очереди и просто через setTimeout проверять доступность выполнения запроса (в случае если он сразу не выполнился), что, как выяснилось, тоже может привести к негативным последствиям.

У вас есть идеи?)

А если представить, что попросту нет возможности использовать списки/мапы и тому подобное. Как бы тогда это могло разрешаться?)

Трудно представить. Список можно сделать всегда и на чем угодно.
А всякие варианты с timeout мне не нравятся из-за непонятно какого подбора времен. А если ситуация хоть временно изменится, то эти подобранные для среднего случая времена будут ни на что не годится.

Ну, имелось ввиду и не списки, и не timeout. Потому что с timeout мне тоже до конца не нравится. Это как long-polling вместо websocket

Тут такая ситуация.
Приходят запросы. Некоторые запросы не могут быть сразу выполнены. Что с ними делать? Варианта 2:
1 - отправлять отказ клиенту, сейчас не могу, попробуй снова прислать запрос позже. Не самый лучший вариант, т.к. может случиться так, что клиент долго и много раз посылать свой запрос.
2 - хранить такие запросы на сервере до тех пор пока они не смогут быть исполнены.
Осталось продумать реализацию такого хранилища. Должна быть возможность помещать туда запрос. И просматривать запросы, что бы выяснить какие могут быть исполнены. И удалять запросы, которые отправляются на выполнение.
Как реализовать такое хранилище можно долго рассуждать. Очередь напрашивается как бы сама собой (ну не совсем очередь "первый пришел - первый обслужен".
Хотелось бы, что бы запросы там не застревали надолго. Т.е не было ситуации, что какой то запрос там долго находится, хотя позже пришедшие запросы с этими же пользователями уже выполнились. Для этого из множества запросов, которые могут быть выполнены в данный момент, первыми надо выбирать те, которые раньше пришли.
Вот такое должно быть хранилище. Как его называть - списком или еще как не суть. Вот как реализовывать действительно стоит думать
Я придумал списки, вы map. И то и то работает и примерно одинаково по времени. Где и как можно оптимизировать время просмотра - не очень понятно. Если бы надо было там искать каких то определенных членов операций. можно еще было бы придумать списки для каждого члена и т.п. Только боюсь, что таких списков будет слишком много, и работа с ними не слишком оптимизирует, т.к их тоже надо как то просматривать. Но нам приходится искать и запросы, членов которых нет в буфере. Как это оптимизировать - совсем не понятно.
В любом случае, если за единицу времени постоянно приходит больше запросов, чем может быть обработано за это же время - любое хранилище будет расти. И тут уже надо думать, не о том, как его организовать, а как увеличить количество запросов обрабатываемых в единицу времени.
Ну или уменьшать количество запросов - давать отказ клиенту если количество необработанных запросов в хранилище превышает определенную величину. Так и говорить "система перегружена, попробуй минут через 10 (20, 30)"

Я именно это и предлагал. Такой вариант позволит быстро находить одну или две новые задачи под выполнение, если освободится очередная пара участников.

Тогда хранить и вести списки для участников, которые находятся в буфере, и тех, которые в очереди. Удалять пустые списки. Просматривать эти списки.
Это же тоже работа.

voraa,
это копеечная работа, которая не зависит от размера очереди. Зато вместо одного большого списка для всех, надо будет смотреть два маленьких списка для освободившихся участников. А если таки понадобится соблюдать очередность действий для каждого участника, бонусом имеем быструю проверку на присутствие в очереди.

Если различных участников много, то выигрыш весьма изрядный.

А если мало, но может быть много задач на одни и те же пары участников, то можно добавить в персональные списки ещё группировку по партнеру. Впрочем, пока нет смысла упарываться до такой степени..

Что-то я догнать не могу логику... Можете попунктно описать порядок действий?)

Вот начало:
1. На сервер приходит запрос <Петя> хочет передать <Васе>
2. Проверяем Петю и Васю в buffer
3. Если хотя бы один есть в buffer, то ...

[... что дальше должно быть исходя из ваших маленьких списков?]

Или у вас вообще иная логика подразумевается? (если да, то какая?)

/*
 *
 Ситуация, когда большое множество различных участников хотят провести операцию с участником <X> — очень актуальная. 
 *
 */

И исходя из ваших маленьких списков непонятно как участнику X что-то сделать в промежутке этих бесчисленных операций. В примере с 1 списком это понятно — операция вставляется в очередь и при достижении выполняется. А как это делается в вашем случае?