Если вы действительно можете разрешить O (log n) для pop, dequeue и insert, тогда вполне достаточно простого сбалансированного дерева поиска, такого как красно-черное дерево.
Конечно, вы можете оптимизировать это, поддерживая прямой указатель на самый маленький и самый большой элемент в дереве, а затем обновляя его, когда вы (1) вставляете элементы в дерево или (2) всплывающее окно или удаление из очереди, что, конечно, делает недействительным соотв. указатель. Но поскольку дерево сбалансировано, в любом случае происходит некоторая перестановка, и вы можете обновить код. указатель одновременно.
Существует также то, что называется min-max heap (см. Запись Binary Heap в Википедии), которая реализует в точности «двустороннюю приоритетную очередь», то есть очередь, в которую можно извлекать как с внешнего, так и с заднего конца. Однако там вы не можете получить доступ ко всему списку объектов по порядку, тогда как дерево поиска может быть эффективно итерировано в течение O (n) времени.
Преимущество кучи min-max состоит в том, что объекты current min и max могут быть прочитаны за O (1) время, а для поиска по дереву требуется O (log (n)) только для чтения объект min или max, если у вас нет кэшированных указателей, как я упоминал выше.