it-swarm-fr.com

Comment implémenter une file d'attente à l'aide de deux piles?

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

Est-il possible de "construire" une structure de données en file d'attente en utilisant uniquement les deux piles?

362
Nitin

Conservez 2 piles, appelons-les inbox et outbox.

Enqueue :

  • Poussez le nouvel élément sur inbox

Dequeue :

  • Si outbox est vide, remplissez-le en sautant chaque élément de inbox et en le poussant sur outbox

  • Pop et retourne l'élément top 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 fois et sauté deux fois, donnant ainsi des opérations à temps constant amorties.

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();
    }

}
665
Dave L.

A - Comment inverser une pile

Pour comprendre comment construire une file d’attente à l’aide de deux piles, vous devez savoir comment inverser une pile de façon claire. Rappelez-vous comment fonctionne pile, il est très similaire à la pile de vaisselle dans votre cuisine. Le dernier plat lavé sera sur le dessus de la pile propre, appelée L ast I n F irst O ut (LIFO) en informatique.

Imaginons notre pile comme une bouteille comme ci-dessous;

 enter image description here

Si on pousse les entiers 1, 2, 3 respectivement, 3 sera au sommet de la pile. Parce que 1 sera poussé en premier, alors 2 sera placé en haut de 1. Enfin, 3 sera mis en haut de la pile et le dernier état de notre pile représenté par une bouteille sera comme ci-dessous;

 enter image description here

Maintenant, nous avons notre pile représentée comme une bouteille est remplie avec les valeurs 3,2,1. Et nous voulons inverser la pile pour que le haut de la pile soit 1 et que le bas de la pile soit 3. Que pouvons-nous faire? On peut prendre la bouteille et la tenir à l'envers pour que toutes les valeurs s'inversent dans l'ordre?

 enter image description here

Oui, nous pouvons le faire, mais c'est une bouteille. Pour faire le même processus, nous avons besoin d’une deuxième pile, celle qui stockera les premiers éléments de la pile dans l’ordre inverse. Mettons notre pile remplie à gauche et notre nouvelle pile vide à droite. Pour inverser l'ordre des éléments, nous allons extraire chaque élément de la pile de gauche et les pousser dans la pile de droite. Vous pouvez voir ce qui se passe comme nous le faisons sur l'image ci-dessous;

 enter image description here

Nous savons donc comment inverser une pile.

B - Utiliser deux piles en file d'attente

Dans la partie précédente, j'ai expliqué comment inverser l'ordre des éléments de la pile. C’était important, car si nous enfonçions des éléments dans la pile, la sortie serait exactement dans l’ordre inverse de la file d’attente. En pensant à un exemple, poussons le tableau d’entiers {1, 2, 3, 4, 5} dans une pile. Si nous ouvrons les éléments et les imprimons jusqu'à ce que la pile soit vide, nous obtiendrons le tableau dans l'ordre inverse de l'ordre de poussage, qui sera le suivant: {5, 4, 3, 2, 1} la sortie sera {1, 2, 3, 4, 5}. Il est donc évident que pour le même ordre d'entrée d'éléments, la sortie de la file d'attente est exactement l'inverse de la sortie d'une pile. Comme nous savons inverser une pile à l’aide d’une pile supplémentaire, nous pouvons construire une file d’attente à l’aide de deux piles.

Notre modèle de file d'attente sera composé de deux piles. Une pile sera utilisée pour l'opération enqueue (la pile n ° 1 à gauche sera appelée pile d'entrée), une autre pile sera utilisée pour l'opération dequeue (la pile n ° 2 à droite sera appelée pile de sortie). Regardez l'image ci-dessous;

 enter image description here

Notre pseudo-code est comme ci-dessous;


Opération En file d'attente

Push every input element to the Input Stack

Opération de retrait

If ( Output Stack is Empty)
    pop every element in the Input Stack
    and Push them to the Output Stack until Input Stack is Empty

pop from Output Stack

Mettons en file d'attente les entiers {1, 2, 3} respectivement. Les entiers seront poussés sur le Input Stack (Stack # 1) qui se trouve à gauche;

 enter image description here

Alors que se passera-t-il si nous exécutons une opération de retrait de la file d'attente? Chaque fois qu'une opération de retrait de file est exécutée, la file va vérifier si la pile de sortie est vide ou non (voir le pseudo-code ci-dessus). Si la pile de sortie est vide, la pile d'entrée sera alors extraite sur la sortie pour que les éléments de la pile d’entrée sera inversée. Avant de renvoyer une valeur, l'état de la file d'attente sera comme ci-dessous;

 enter image description here

Vérifiez l'ordre des éléments dans la pile de sortie (pile n ° 2). Il est évident que nous pouvons extraire les éléments de la pile de sortie pour que la sortie soit la même que si nous avions retiré de la file d'attente. Ainsi, si nous exécutons deux opérations de retrait de la file d'attente, nous obtiendrons d'abord {1, 2} respectivement. L'élément 3 sera alors le seul élément de la pile de sortie et la pile d'entrée sera vide. Si nous mettons en file d'attente les éléments 4 et 5, alors l'état de la file d'attente sera comme suit;

 enter image description here

Maintenant, la pile de sortie n'est pas vide et si nous exécutons une opération de retrait de la file d'attente, seuls 3 seront sortis de la pile de sortie. Ensuite, l'état sera vu comme ci-dessous;

 enter image description here

De nouveau, si nous exécutons deux autres opérations de retrait de la file d'attente, lors de la première opération, la file d'attente vérifiera si la pile de sortie est vide, ce qui est vrai. Ensuite, sortez les éléments de la pile d’entrée et placez-les dans la pile de sortie jusqu’à ce que la pile d’entrée soit vide, l’état de la file d’attente sera comme ci-dessous;

 enter image description here

Facile à voir, la sortie des deux opérations de retrait de la file sera {4, 5}

C - Implémentation d'une file d'attente construite avec deux piles

Voici une implémentation en Java. Je ne vais pas utiliser la mise en œuvre existante de Stack, l'exemple ci-dessous va réinventer la roue;

C - 1) Classe MyStack: une implémentation simple de pile

public class MyStack<T> {

    // inner generic Node class
    private class Node<T> {
        T data;
        Node<T> next;

        public Node(T data) {
            this.data = data;
        }
    }

    private Node<T> head;
    private int size;

    public void Push(T e) {
        Node<T> newElem = new Node(e);

        if(head == null) {
            head = newElem;
        } else {
            newElem.next = head;
            head = newElem;     // new elem on the top of the stack
        }

        size++;
    }

    public T pop() {
        if(head == null)
            return null;

        T elem = head.data;
        head = head.next;   // top of the stack is head.next

        size--;

        return elem;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void printStack() {
        System.out.print("Stack: ");

        if(size == 0)
            System.out.print("Empty !");
        else
            for(Node<T> temp = head; temp != null; temp = temp.next)
                System.out.printf("%s ", temp.data);

        System.out.printf("\n");
    }
}

C - 2) Classe MyQueue: implémentation de la file d'attente à l'aide de deux piles

public class MyQueue<T> {

    private MyStack<T> inputStack;      // for enqueue
    private MyStack<T> outputStack;     // for dequeue
    private int size;

    public MyQueue() {
        inputStack = new MyStack<>();
        outputStack = new MyStack<>();
    }

    public void enqueue(T e) {
        inputStack.Push(e);
        size++;
    }

    public T dequeue() {
        // fill out all the Input if output stack is empty
        if(outputStack.isEmpty())
            while(!inputStack.isEmpty())
                outputStack.Push(inputStack.pop());

        T temp = null;
        if(!outputStack.isEmpty()) {
            temp = outputStack.pop();
            size--;
        }

        return temp;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

}

C - 3) Code de démonstration

public class TestMyQueue {

    public static void main(String[] args) {
        MyQueue<Integer> queue = new MyQueue<>();

        // enqueue integers 1..3
        for(int i = 1; i <= 3; i++)
            queue.enqueue(i);

        // execute 2 dequeue operations 
        for(int i = 0; i < 2; i++)
            System.out.println("Dequeued: " + queue.dequeue());

        // enqueue integers 4..5
        for(int i = 4; i <= 5; i++)
            queue.enqueue(i);

        // dequeue the rest
        while(!queue.isEmpty())
            System.out.println("Dequeued: " + queue.dequeue());
    }

}

C - 4) Exemple de sortie

Dequeued: 1
Dequeued: 2
Dequeued: 3
Dequeued: 4
Dequeued: 5
185
Levent Divilioglu

Vous pouvez même simuler une file d'attente en utilisant une seule pile. La deuxième pile (temporaire) peut être simulée par la pile d'appels d'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 devez transférer des éléments d'une pile à une autre pile temporaire pour inverser leur ordre. 
  • Puis poussez le nouvel élément à insérer dans la pile temporaire
  • Transférez ensuite les éléments dans la pile d'origine
  • Le nouvel élément sera au bas de la pile et le plus ancien en haut (le premier à apparaître)

Une classe de file d'attente utilisant une seule pile serait la suivante:

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();
    }
}
79
pythonquick

Les complexités temporelles seraient toutefois pires. Une bonne mise en œuvre de la file d'attente fait tout en temps constant.

Modifier

Je ne sais pas pourquoi ma réponse a été rejetée ici. Si nous programmons, nous nous soucions de la complexité du temps et l'utilisation de deux piles standard pour créer une file d'attente est inefficace. C'est un point très valable et pertinent. Si quelqu'un d'autre ressent le besoin de réduire davantage ce nombre, je serais intéressé de savoir pourquoi.

Un peu plus de détails: pourquoi l'utilisation de deux piles est pire qu'une file d'attente: si vous utilisez deux piles et que quelqu'un appelle la file d'attente pendant que la boîte d'envoi est vide, vous avez besoin de temps linéaire pour aller au bas de la boîte de réception ( comme vous pouvez le voir dans le code de Dave).

Vous pouvez implémenter une file d'attente en tant que liste à lien unique (chaque élément pointe sur l'élément inséré suivant), en conservant un pointeur supplémentaire sur le dernier élément inséré pour les poussées (ou en en faisant une liste cyclique). L'implémentation de la file d'attente et de la file d'attente sur cette structure de données est très facile à effectuer en temps constant. C'est le pire des cas, temps constant, non amorti. Et, comme les commentaires semblent demander cette clarification, le temps constant dans le pire des cas est strictement meilleur que le temps constant amorti.

11
Tyler

Laissez la file d'attente à implémenter être q et les piles utilisées pour implémenter q seront stack1 et stack2. 

q peut être implémenté de deux façons:

Méthode 1 (en rendant l'opération enQueue coûteuse)

Cette méthode permet de s’assurer que le nouvel élément entré est toujours au sommet de la pile 1, de sorte que l’opération deQueue saute de la pile1. Pour placer l'élément en haut de stack1, stack2 est utilisé.

enQueue(q, x)
1) While stack1 is not empty, Push everything from stack1 to stack2.
2) Push x to stack1 (assuming size of stacks is unlimited).
3) Push everything back to stack1.
deQueue(q)
1) If stack1 is empty then error
2) Pop an item from stack1 and return it.

Méthode 2 (En rendant le fonctionnement de deQueue coûteux)

Dans cette méthode, en opération de file d'attente, le nouvel élément est entré en haut de pile1. En opération de file d'attente, si pile2 est vide, tous les éléments sont déplacés vers pile2 et finalement, le haut de pile2 est renvoyé.

enQueue(q,  x)
 1) Push x to stack1 (assuming size of stacks is unlimited).

deQueue(q)
 1) If both stacks are empty then error.
 2) If stack2 is empty
   While stack1 is not empty, Push everything from stack1 to stack2.
 3) Pop the element from stack2 and return it.

La méthode 2 est définitivement meilleure que la méthode 1. La méthode 1 déplace tous les éléments deux fois en opération enQueue, tandis que la méthode 2 (en opération deQueue) déplace les éléments une fois et ne déplace les éléments que si pile2 est vide.

7
Rahul Gandhi

Une solution en c #

 public class Queue<T> where T : class
    {
        private Stack<T> input = new Stack<T>();
        private Stack<T> output = new Stack<T>();
        public void Enqueue(T t)
        {
            input.Push(t);
        }

        public T Dequeue()
        {
            if (output.Count == 0)
            {
                while (input.Count != 0)
                {
                    output.Push(input.Pop());
                }
            }
            return output.Pop();
        }
}
3
Santhosh

Vous devrez tout extraire de la première pile pour obtenir l'élément du bas. Ensuite, remettez-les tous dans la deuxième pile pour chaque opération de "retrait de la file d'attente".

2
user11055

pour le développeur c #, voici le programme complet:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace QueueImplimentationUsingStack
{
    class Program
    {
        public class Stack<T>
        {
            public int size;
            public Node<T> head;
            public void Push(T data)
            {
                Node<T> node = new Node<T>();
                node.data = data;
                if (head == null)
                    head = node;
                else
                {
                    node.link = head;
                    head = node;
                }
                size++;
                Display();
            }
            public Node<T> Pop()
            {
                if (head == null)
                    return null;
                else
                {
                    Node<T> temp = head;
                    //temp.link = null;
                    head = head.link;
                    size--;
                    Display();
                    return temp;
                }
            }
            public void Display()
            {
                if (size == 0)
                    Console.WriteLine("Empty");
                else
                {
                    Console.Clear();
                    Node<T> temp = head;
                    while (temp!= null)
                    {
                        Console.WriteLine(temp.data);
                        temp = temp.link;
                    }
                }
            }
        }

        public class Queue<T>
        {
            public int size;
            public Stack<T> inbox;
            public Stack<T> outbox;
            public Queue()
            {
                inbox = new Stack<T>();
                outbox = new Stack<T>();
            }
            public void EnQueue(T data)
            {
                inbox.Push(data);
                size++;
            }
            public Node<T> DeQueue()
            {
                if (outbox.size == 0)
                {
                    while (inbox.size != 0)
                    {
                        outbox.Push(inbox.Pop().data);
                    }
                }
                Node<T> temp = new Node<T>();
                if (outbox.size != 0)
                {
                    temp = outbox.Pop();
                    size--;
                }
                return temp;
            }

        }
        public class Node<T>
        {
            public T data;
            public Node<T> link;
        }

        static void Main(string[] args)
        {
            Queue<int> q = new Queue<int>();
            for (int i = 1; i <= 3; i++)
                q.EnQueue(i);
           // q.Display();
            for (int i = 1; i < 3; i++)
                q.DeQueue();
            //q.Display();
            Console.ReadKey();
        }
    }
}
2
Jaydeep Shil

Deux piles de la file sont définies comme suit: pile1 et pile2.

Enqueue: Les éléments euqueued sont toujours poussés dans pile1

Dequeue: Le haut de pile2 peut être sauté puisqu'il s'agit du premier élément inséré dans la file d'attente lorsque pile2 n'est pas vide. Quand pile2 est vide, nous sautons tous les éléments de pile1 et les pousser dans pile2 un par un. Le premier élément d'une file d'attente est placé au bas de pile1. Il peut être sorti directement après les opérations de popping et de push puisqu'il se trouve au sommet de pile2.

Voici le même exemple de code C++:

template <typename T> class CQueue
{
public:
    CQueue(void);
    ~CQueue(void);

    void appendTail(const T& node); 
    T deleteHead();                 

private:
    stack<T> stack1;
    stack<T> stack2;
};

template<typename T> void CQueue<T>::appendTail(const T& element) {
    stack1.Push(element);
} 

template<typename T> T CQueue<T>::deleteHead() {
    if(stack2.size()<= 0) {
        while(stack1.size()>0) {
            T& data = stack1.top();
            stack1.pop();
            stack2.Push(data);
        }
    }


    if(stack2.size() == 0)
        throw new exception("queue is empty");


    T head = stack2.top();
    stack2.pop();


    return head;
}

Cette solution est empruntée à mon blog . Une analyse plus détaillée avec des simulations de fonctionnement pas à pas est disponible sur la page Web de mon blog.

2
Harry He
// Two stacks s1 Original and s2 as Temp one
    private Stack<Integer> s1 = new Stack<Integer>();
    private Stack<Integer> s2 = new Stack<Integer>();

    /*
     * Here we insert the data into the stack and if data all ready exist on
     * stack than we copy the entire stack s1 to s2 recursively and Push the new
     * element data onto s1 and than again recursively call the s2 to pop on s1.
     * 
     * Note here we can use either way ie We can keep pushing on s1 and than
     * while popping we can remove the first element from s2 by copying
     * recursively the data and removing the first index element.
     */
    public void insert( int data )
    {
        if( s1.size() == 0 )
        {
            s1.Push( data );
        }
        else
        {
            while( !s1.isEmpty() )
            {
                s2.Push( s1.pop() );
            }
            s1.Push( data );
            while( !s2.isEmpty() )
            {
                s1.Push( s2.pop() );
            }
        }
    }

    public void remove()
    {
        if( s1.isEmpty() )
        {
            System.out.println( "Empty" );
        }
        else
        {
            s1.pop();

        }
    }
1
imvp

Une implémentation d'une file d'attente utilisant deux piles dans Swift:

struct Stack<Element> {
    var items = [Element]()

    var count : Int {
        return items.count
    }

    mutating func Push(_ item: Element) {
        items.append(item)
    }

    mutating func pop() -> Element? {
        return items.removeLast()
    }

    func peek() -> Element? {
        return items.last
    }
}

struct Queue<Element> {
    var inStack = Stack<Element>()
    var outStack = Stack<Element>()

    mutating func enqueue(_ item: Element) {
        inStack.Push(item)
    }

    mutating func dequeue() -> Element? {
        fillOutStack() 
        return outStack.pop()
    }

    mutating func peek() -> Element? {
        fillOutStack()
        return outStack.peek()
    }

    private mutating func fillOutStack() {
        if outStack.count == 0 {
            while inStack.count != 0 {
                outStack.Push(inStack.pop()!)
            }
        }
    }
}
1
davejlin

Bien que vous ayez beaucoup de publications sur l’implémentation d’une file d’attente avec deux piles: 1. Soit en rendant le processus enQueue beaucoup plus coûteux 2. Ou en rendant le processus deQueue beaucoup plus coûteux

https://www.geeksforgeeks.org/queue-using-stacks/

L'un des moyens importants que j'ai découverts dans l'article précédent est la construction d'une file d'attente avec uniquement la structure de données de pile et la pile d'appels de récursivité.

Bien que l’on puisse affirmer que cela utilise toujours deux piles, mais qu’il ne faut idéalement utiliser qu’une seule structure de données.

Ci-dessous l'explication du problème:

  1. Déclarez une seule pile pour enQueuing et dQueing les données et poussez les données dans la pile.

  2. pendant que deQueueing a une condition de base dans laquelle l'élément de la pile est affiché lorsque la taille de la pile est 1. Cela garantit qu'il n'y a pas de dépassement de capacité de la pile pendant la récursion deQueue.

  3. Pendant que deQueueing commence par extraire les données du haut de la pile. Idéalement, cet élément sera l’élément présent au sommet de la pile. Maintenant, une fois que cela est fait, appelez la fonction deQueue de manière récursive, puis poussez l'élément sauté au-dessus dans la pile.

Le code ressemblera à celui ci-dessous:

if (s1.isEmpty())
System.out.println("The Queue is empty");
        else if (s1.size() == 1)
            return s1.pop();
        else {
            int x = s1.pop();
            int result = deQueue();
            s1.Push(x);
            return result;

De cette façon, vous pouvez créer une file d'attente à l'aide d'une structure de données à pile unique et de la pile d'appels récursifs.

1
Radioactive

voici ma solution en Java en utilisant linkedlist.

class queue<T>{
static class Node<T>{
    private T data;
    private Node<T> next;
    Node(T data){
        this.data = data;
        next = null;
    }
}
Node firstTop;
Node secondTop;

void Push(T data){
    Node temp = new Node(data);
    temp.next = firstTop;
    firstTop = temp;
}

void pop(){
    if(firstTop == null){
        return;
    }
    Node temp = firstTop;
    while(temp != null){
        Node temp1 = new Node(temp.data);
        temp1.next = secondTop;
        secondTop = temp1;
        temp = temp.next;
    }
    secondTop = secondTop.next;
    firstTop = null;
    while(secondTop != null){
        Node temp3 = new Node(secondTop.data);
        temp3.next = firstTop;
        firstTop = temp3;
        secondTop = secondTop.next;
    }
}

}

Remarque: Dans ce cas, l'opération pop prend beaucoup de temps. Donc, je ne suggère pas de créer une file d'attente en utilisant deux piles. 

0
Irshad ck

Je vais répondre à cette question dans Go car Go ne contient pas beaucoup de collections dans sa bibliothèque standard.

Puisqu'une pile est vraiment facile à implémenter, j'ai décidé d'utiliser deux piles pour réaliser une file d'attente double. Pour mieux comprendre comment je suis arrivé à ma réponse, j'ai divisé la mise en œuvre en deux parties. La première partie est, espérons-le, plus facile à comprendre, mais elle est incomplète.

type IntQueue struct {
    front       []int
    back        []int
}

func (q *IntQueue) PushFront(v int) {
    q.front = append(q.front, v)
}

func (q *IntQueue) Front() int {
    if len(q.front) > 0 {
        return q.front[len(q.front)-1]
    } else {
        return q.back[0]
    }
}

func (q *IntQueue) PopFront() {
    if len(q.front) > 0 {
        q.front = q.front[:len(q.front)-1]
    } else {
        q.back = q.back[1:]
    }
}

func (q *IntQueue) PushBack(v int) {
    q.back = append(q.back, v)
}

func (q *IntQueue) Back() int {
    if len(q.back) > 0 {
        return q.back[len(q.back)-1]
    } else {
        return q.front[0]
    }
}

func (q *IntQueue) PopBack() {
    if len(q.back) > 0 {
        q.back = q.back[:len(q.back)-1]
    } else {
        q.front = q.front[1:]
    }
}

Il s’agit essentiellement de deux piles pour lesquelles nous permettons au fond des piles d’être manipulées les unes par les autres. J'ai également utilisé les conventions de nommage STL, dans lesquelles les opérations traditionnelles de pile d'une pile ont un préfixe avant/arrière, qu'elles se rapportent à l'avant ou à l'arrière de la file d'attente.

Le problème avec le code ci-dessus est qu'il n'utilise pas la mémoire de manière très efficace. En fait, il se développe sans cesse jusqu'à ce que vous manquiez d'espace. C'est vraiment mauvais. La solution à cela est de simplement réutiliser le bas de la pile autant que possible. Nous devons introduire un décalage pour suivre cela, car une tranche dans Go ne peut pas croître à l'avant une fois réduite.

type IntQueue struct {
    front       []int
    frontOffset int
    back        []int
    backOffset  int
}

func (q *IntQueue) PushFront(v int) {
    if q.backOffset > 0 {
        i := q.backOffset - 1
        q.back[i] = v
        q.backOffset = i
    } else {
        q.front = append(q.front, v)
    }
}

func (q *IntQueue) Front() int {
    if len(q.front) > 0 {
        return q.front[len(q.front)-1]
    } else {
        return q.back[q.backOffset]
    }
}

func (q *IntQueue) PopFront() {
    if len(q.front) > 0 {
        q.front = q.front[:len(q.front)-1]
    } else {
        if len(q.back) > 0 {
            q.backOffset++
        } else {
            panic("Cannot pop front of empty queue.")
        }
    }
}

func (q *IntQueue) PushBack(v int) {
    if q.frontOffset > 0 {
        i := q.frontOffset - 1
        q.front[i] = v
        q.frontOffset = i
    } else {
        q.back = append(q.back, v)
    }
}

func (q *IntQueue) Back() int {
    if len(q.back) > 0 {
        return q.back[len(q.back)-1]
    } else {
        return q.front[q.frontOffset]
    }
}

func (q *IntQueue) PopBack() {
    if len(q.back) > 0 {
        q.back = q.back[:len(q.back)-1]
    } else {
        if len(q.front) > 0 {
            q.frontOffset++
        } else {
            panic("Cannot pop back of empty queue.")
        }
    }
}

C'est beaucoup de petites fonctions mais des 6 fonctions, 3 d'entre elles ne sont que des miroirs de l'autre.

0
John Leidegren

Vous trouverez ci-dessous la solution en langage javascript utilisant la syntaxe ES6.

Stack.js

//stack using array
class Stack {
  constructor() {
    this.data = [];
  }

  Push(data) {
    this.data.Push(data);
  }

  pop() {
    return this.data.pop();
  }

  peek() {
    return this.data[this.data.length - 1];
  }

  size(){
    return this.data.length;
  }
}

export { Stack };

QueueUsingTwoStacks.js

import { Stack } from "./Stack";

class QueueUsingTwoStacks {
  constructor() {
    this.stack1 = new Stack();
    this.stack2 = new Stack();
  }

  enqueue(data) {
    this.stack1.Push(data);
  }

  dequeue() {
    //if both stacks are empty, return undefined
    if (this.stack1.size() === 0 && this.stack2.size() === 0)
      return undefined;

    //if stack2 is empty, pop all elements from stack1 to stack2 till stack1 is empty
    if (this.stack2.size() === 0) {
      while (this.stack1.size() !== 0) {
        this.stack2.Push(this.stack1.pop());
      }
    }

    //pop and return the element from stack 2
    return this.stack2.pop();
  }
}

export { QueueUsingTwoStacks };

Ci-dessous est l'utilisation:

index.js

import { StackUsingTwoQueues } from './StackUsingTwoQueues';

let que = new QueueUsingTwoStacks();
que.enqueue("A");
que.enqueue("B");
que.enqueue("C");

console.log(que.dequeue());  //output: "A"
0
Jyoti Prasad Pal
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 opération de mise en file d'attente, nous ajoutons au sommet de la pile1. Pour chaque file d'attente, nous viderons le contenu de stack1 dans stack2 et supprimerons l'élément situé en haut de la pile. La complexité temporelle est O(n) pour la file d'attente, car nous devons copier stack1 dans stack2. la complexité temporelle de la mise en file d'attente est identique à celle d'une pile normale

0
PradGar

Avec O(1)dequeue(), qui est identique à answer : de pythonquick

// time: O(n), space: O(n)
enqueue(x):
    if stack.isEmpty():
        stack.Push(x)
        return
    temp = stack.pop()
    enqueue(x)
    stack.Push(temp)

// time: O(1)
x dequeue():
    return stack.pop()

Avec O(1)enqueue() (ceci n'est pas mentionné dans ce message, donc cette réponse), qui utilise également le retour en arrière pour faire des bulles et renvoyer l'élément le plus bas.

// O(1)
enqueue(x):
    stack.Push(x)

// time: O(n), space: O(n)
x dequeue():
    temp = stack.pop()
    if stack.isEmpty():
        x = temp
    else:
        x = dequeue()
        stack.Push(temp)
    return x

De toute évidence, c’est un bon exercice de codage, car il est néanmoins inefficace mais élégant.

0
hIpPy