pile en utilisant deux files d'attente

Question

Possible en double:
Implement Stack using Two Queues

Je veux que le moyen le plus efficace en termes de complexité de temps pour mettre en œuvre la pile en utilisant deux files d'attente

Answer 1

Je ne comprends pas pourquoi vous auriez besoin de deux files d'attente. J'ai vu les réponses ici et dans le fil de dupe, et vous pouvez le faire avec une seule file d'attente.

Du fil dupe, il existe deux versions, une qui optimise la poussée, et une qui optimise la pop.

poussoir optimisé:

push: 
    enqueue in queue 
pop: 
    n = queue size. 
    dequeue an object, and enqueue it immediately after. Do this n - 1 times. 
    dequeue object, and return this. 

Pop optimisé:

push: 
    enqueue in queue 
    n = queue size. 
    dequeue an object, and enqueue it immediately after. Do this n - 1 times. 
pop: 
    dequeue from queue and return. 

Là encore, je ne comprends pas pourquoi vous avez envie de le faire jamais. Lambast votre professeur pour vous faire perdre votre temps avec des questions de programmation inutile.

Answer 2

Je peux me tromper , mais pour moi cela ne calcule pas.

Une file d'attente est (généralement) une structure FIFO, une pile est une structure LIFO. Je ne peux pas m'empêcher d'imaginer une combinaison simple de 2 FIFO qui donneront un LIFO, bien que je n'aie peut-être pas encore eu assez de café aujourd'hui.

C'est peut-être possible, mais je soupçonne que la mise en œuvre d'une pile impliquant 2 files d'attente va certainement prendre plus de temps à implémenter et être plus sujette aux erreurs qu'une simple implémentation d'une pile.

Cependant, après avoir dit que ...

Si vous avez déjà une implémentation de file d'attente et si cette file d'attente vous permet de supprimer des éléments de sa queue (dans votre mise en œuvre peut différer termes réels) plutôt que de la tête puis vous pouvez simplement utiliser la file d'attente comme s'il s'agissait d'une pile en récupérant des éléments du TAIL.

Answer 3

Il est simple, Disons que vous avez la file d'attente A et la file d'attente B u utiliser une file d'attente pour stocker des données, et d'autres comme un conteneur temporaire ... MAIS A et les rôles d'échange B tout le temps:

Lorsque vous insérez des données pour la première fois, vous insérez dans la file d'attente A. Pour POP le dernier élément que vous avez inséré, vous DEQUE tous les éléments de la file d'attente sauf le dernier et les ENQUEUE dans la file B. DEQUEUE le seul élément de la file d'attente A et vous ' Vous avez ce que vous voulez: Le TOP de la pile, le dernier élément ... etc ...

Maintenant à POP le dernier article, vous refaites le même travail mais Rôles d'échange A et B