Очередная очередь с использованием стека

Question

Может ли один построить очередь приоритета, используя стеки, так что в очередь приоритета одинаковая сложность для каждой операции. Это может быть сделано?Если так, как?Если нет, что лучшее решение, которое можно сделать?

Каждая работа стека с использованием массива - $ o (1) $ , тогда как почти вся операция очереди приоритета $ O (logn) $ . Реализация может быть выполнена с использованием 2D $ $ $ Стеки, каждый элемент стека снова является стеком. Когда первый элемент основного стека является первым элементом других стеков. Работа с учетом DEQUEUE вознаграждает $ O (N) $ , так как он является Lifo, а в очередь приоритета - FIFO.

Answer 1

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

Если вы можете запустить очередь приоритета в постоянное время, вы можете отсортировать в линейном времени.Но вы не можете.