File d'attente prioritaire à l'aide de la pile

Question

peut-on créer une file d'attente prioritaire à l'aide de piles, de sorte que la file d'attente prioritaire a la même complexité pour chaque opération. Pourrait-il être fait?Si c'est le cas, comment?Sinon, quelle est la meilleure solution qui puisse être faite?

Chaque opération d'une pile utilisant un tableau est $ o (1) $ alors que presque toutes les opérations de la file d'attente prioritaires sont $ O (logn) $ . Une implémentation peut être effectuée en utilisant 2D $ 2D $ Stacks, chaque élément de la pile est à nouveau une pile. Lorsque le premier élément de la pile principale est le premier élément des autres piles. L'opération de dequeuse prendra $ o (n) $ car c'est LIFO et la file d'attente prioritaire est FIFO.

Answer 1

pense à ce sujet.Vous pouvez trier un tableau en ajoutant tous les éléments à une file d'attente prioritaire, puis en supprimant les éléments dans la commande triée.

Si vous pouviez exécuter une file d'attente prioritaire en temps constant, vous pouvez trier le temps linéaire.Mais tu ne peux pas.