Comment mettre en place une file d'attente à l'aide de deux piles?

Question

Supposons que nous avons deux piles et aucune autre variable temporaire.

Est possible de "construire" une file d'attente de la structure de données à l'aide de seulement deux piles?

Answer 1

Garder 2 piles, appelons - inbox et outbox.

File d'attente:
- Pousser l'élément nouveau sur inbox

File d'attente:
- Si outbox est vide, remplissez-le en sautant chaque élément d' inbox et en le poussant sur outbox
- Pop et de retour, l'élément supérieur de outbox

En utilisant cette méthode, chaque élément sera dans chaque pile exactement une fois - ce qui signifie que chaque élément sera poussé à deux reprises et a sauté deux fois, donnant amorti de la constante de temps des opérations.

Voici une implémentation en Java:

public class Queue<E>
{

    private Stack<E> inbox = new Stack<E>();
    private Stack<E> outbox = new Stack<E>();

    public void queue(E item) {
        inbox.push(item);
    }

    public E dequeue() {
        if (outbox.isEmpty()) {
            while (!inbox.isEmpty()) {
               outbox.push(inbox.pop());
            }
        }
        return outbox.pop();
    }

}

Answer 2

Vous pouvez même simuler une file d'attente en utilisant une seule pile. La deuxième (temporaire) de la pile peut être simulé par la pile d'appel des appels récursifs à la méthode d'insertion.

Le principe reste le même lors de l'insertion d'un nouvel élément dans la file d'attente:

• Vous avez besoin de transférer des éléments d'une pile à une autre entreprise de la pile, à l'inverse de leur ordre.
• Ensuite, poussez le nouvel élément à insérer, sur la temporaire de la pile
• Puis de transférer les éléments à l'origine de la pile
• Le nouvel élément sera sur le bas de la pile, et le plus ancien élément est en haut (le premier à être sauté).

Une File d'attente de classe à l'aide d'une seule Pile, serait comme suit:

public class SimulatedQueue<E> {
    private java.util.Stack<E> stack = new java.util.Stack<E>();

    public void insert(E elem) {
        if (!stack.empty()) {
            E topElem = stack.pop();
            insert(elem);
            stack.push(topElem);
        }
        else
            stack.push(elem);
    }

    public E remove() {
        return stack.pop();
    }
}

Answer 3

Le temps complexités serait pire, si. Une bonne file d'attente de la mise en œuvre tout en temps constant.

Modifier

Je ne sais pas pourquoi ma réponse a été downvoted ici. Si l'on programme, nous nous soucions du temps de la complexité, et à l'aide de deux piles de faire une file d'attente est inefficace. C'est un très valable et pertinent point. Si quelqu'un d'autre se sent le besoin de downvote de cette de plus, je serais intéressé de savoir pourquoi.

Un peu plus de détail: pourquoi à l'aide de deux piles est pire qu'une file d'attente: si vous utilisez deux piles, et quelqu'un appelle la file d'attente, tandis que la boîte d'envoi est vide, vous devez linéaire du temps pour aller au fond de la boîte de réception (comme vous pouvez le voir dans Dave du code).

Vous pouvez mettre en place une file d'attente comme une liste liée individuellement (chaque élément pointe vers le prochain-élément inséré), la tenue d'un supplément de pointeur sur le dernier élément inséré pour la pousse (ou en faisant un mouvement cyclique de la liste). La mise en œuvre de la file d'attente et à retirer sur cette structure de données est très facile à faire en temps constant. C'est pire-cas de la constante de temps, n'est pas amorti. Et, comme les commentaires semblent poser pour cette clarification, dans le pire des cas, la constante de temps est strictement mieux que l'amorti de la constante de temps.

Answer 4

Brian est la réponse classique est correcte. En fait, c'est l'une des meilleures façons de mettre en œuvre persistante fonctionnelle files d'attente avec des amortis de la constante de temps. Il en est ainsi parce que, dans la programmation fonctionnelle, nous avons une très belle persistante de la pile (liste chaînée). À l'aide de deux listes dans la façon dont Brian décrit, il est possible de mettre en œuvre rapide de la file d'attente sans exiger un montant obscène de la copie.

Comme un mineur de côté, il est possible de prouver que vous pouvez faire quelque chose avec deux piles. C'est parce que les deux-pile complètement l'opération répond à la définition d'une machine de Turing universelle. Cependant, comme la Suite le montre, il n'est pas toujours facile. :-)

Answer 5

public class QueueUsingStacks<T>
{
    private LinkedListStack<T> stack1;
    private LinkedListStack<T> stack2;

    public QueueUsingStacks()
    {
        stack1=new LinkedListStack<T>();
        stack2 = new LinkedListStack<T>();

    }
    public void Copy(LinkedListStack<T> source,LinkedListStack<T> dest )
    {
        while(source.Head!=null)
        {
            dest.Push(source.Head.Data);
            source.Head = source.Head.Next;
        }
    }
    public void Enqueue(T entry)
    {

       stack1.Push(entry);
    }
    public T Dequeue()
    {
        T obj;
        if (stack2 != null)
        {
            Copy(stack1, stack2);
             obj = stack2.Pop();
            Copy(stack2, stack1);
        }
        else
        {
            throw new Exception("Stack is empty");
        }
        return obj;
    }

    public void Display()
    {
        stack1.Display();
    }


}

Pour chaque file de l'opération, nous ajouter en haut de la stack1. Pour chaque file d'attente, on vide le contenu de stack1 en stack2, et de supprimer l'élément au sommet de la pile.Le temps de la complexité est O(n) pour les retirer, il faut copier le stack1 à stack2. le temps de la complexité de mise en file d'attente est le même comme une pile