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

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

Gardez 2 piles, appelons-les inboxet outbox.

Mettre en file d'attente :

• Poussez le nouvel élément sur inbox

Retrait de la file d'attente :

• Si outboxest vide, remplissez-le en sortant chaque élément inboxet en le poussant suroutbox

• Pop et retourner 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 fois et sauté deux fois, donnant 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();
    }

}

A - Comment inverser une pile

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

Imaginons notre pile comme une bouteille comme ci-dessous;

Si nous poussons les entiers 1,2,3 respectivement, alors 3 sera au sommet de la pile. Parce que 1 sera poussé en premier, puis 2 sera placé sur le dessus de 1. Enfin, 3 sera placé sur le dessus de la pile et le dernier état de notre pile représenté comme une bouteille sera comme ci-dessous;

Maintenant, nous avons notre pile représentée comme une bouteille est remplie de valeurs 3,2,1. Et nous voulons inverser la pile pour que l'élément supérieur de la pile soit 1 et l'élément inférieur de la pile 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?

Oui, nous pouvons le faire, mais c'est une bouteille. Pour faire le même processus, nous devons avoir une deuxième pile qui va stocker les premiers éléments de 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 faire sauter chaque élément de la pile de gauche et les pousser vers la pile de droite. Vous pouvez voir ce qui se passe comme nous le faisons sur l'image ci-dessous;

Nous savons donc comment inverser une pile.

B - Utilisation de deux piles comme 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 poussons et pop des éléments dans la pile, la sortie sera exactement dans l'ordre inverse d'une file d'attente. En réfléchissant à un exemple, poussons le tableau d'entiers {1, 2, 3, 4, 5}dans une pile. Si nous éclatons 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 poussée, qui sera {5, 4, 3, 2, 1}Rappelez-vous que pour la même entrée, si nous retirons la file d'attente jusqu'à ce qu'elle soit vide, 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 inverse de la sortie d'une pile. Comme nous savons inverser une pile en utilisant une pile supplémentaire, nous pouvons construire une file d'attente en utilisant deux piles.

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

Notre pseudo-code est comme ci-dessous;

Opération de mise en file d'attente

Push every input element to the Input Stack

Opération de retrait de file d'attente

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 la pile d'entrée ( pile n ° 1 ) qui se trouve à gauche;

Que se passera-t-il alors si nous exécutons une opération de retrait de file d'attente? Chaque fois qu'une opération de mise en file d'attente est exécutée, la file d'attente 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, alors la pile d'entrée va être extraite sur la sortie afin 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;

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 afin que la sortie soit la même que si nous étions retirés d'une file d'attente. Ainsi, si nous exécutons deux opérations de mise en 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 le suivant;

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

Encore une fois, si nous exécutons deux autres opérations de mise en file d'attente, lors de la première opération de mise en file d'attente, la file d'attente vérifie si la pile de sortie est vide, ce qui est vrai. Ensuite, sortez les éléments de la pile d'entrée et poussez-les vers la pile de sortie jusqu'à ce que la pile d'entrée soit vide, puis l'état de la file d'attente sera comme ci-dessous;

Facile à voir, la sortie des deux opérations de mise en file d'attente sera {4, 5}

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

Voici une implémentation en Java. Je ne vais pas utiliser l'implémentation existante de Stack donc l'exemple ici va réinventer la roue;

C - 1) Classe MyStack: une implémentation simple de la 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

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 vers une autre pile temporaire pour inverser leur ordre.
• Poussez ensuite le nouvel élément à insérer sur 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 l'élément le plus ancien sera au dessus (le premier à être sauté)

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

La complexité temporelle serait cependant pire. Une bonne implémentation de file d'attente fait tout en temps constant.

Éditer

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 voter plus bas, je serais intéressé de savoir pourquoi.

Un peu plus de détails : pourquoi utiliser deux piles est pire qu'une simple file d'attente: si vous utilisez deux piles et que quelqu'un appelle la file d'attente alors que la boîte d'envoi est vide, vous avez besoin d'un temps linéaire pour atteindre le 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 à liaison unique (chaque élément pointe vers l'élément inséré suivant), en gardant un pointeur supplémentaire sur le dernier élément inséré pour les push (ou en en faisant une liste cyclique). L'implémentation de file d'attente et de retrait de file d'attente sur cette structure de données est très facile à faire en temps constant. C'est le pire temps constant, non amorti. Et, comme les commentaires semblent demander cette clarification, le pire temps constant est strictement meilleur que le temps constant amorti.

Soit file d'attente à implémenter q et piles utilisées pour implémenter q be stack1 et stack2.

q peut être implémenté de deux manières:

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

Cette méthode garantit que l'élément nouvellement entré est toujours en haut de la pile 1, de sorte que l'opération deQueue apparaît simplement à partir de stack1. 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 l'opération deQueue coûteuse)

Dans cette méthode, en opération en file d'attente, le nouvel élément est entré en haut de stack1. En opération de mise en file d'attente, si stack2 est vide, tous les éléments sont déplacés vers stack2 et enfin le haut de stack2 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 nettement meilleure que la méthode 1. La méthode 1 déplace tous les éléments deux fois dans l'opération enQueue, tandis que la méthode 2 (dans l'opération deQueue) déplace les éléments une fois et déplace les éléments uniquement si stack2 est vide.

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

Deux piles dans la file d'attente sont définies comme pile1 et pile2 .

Enqueue: les éléments mis en file d' attente sont toujours poussés dans stack1

Dequeue: le haut de stack2 peut être sorti car il s'agit du premier élément inséré dans la file d'attente lorsque stack2 n'est pas vide. Lorsque stack2 est vide, nous extrayons tous les éléments de stack1 et les poussons dans stack2 un par un. Le premier élément d'une file d'attente est poussé au bas de stack1 . Il peut être sorti directement après les opérations de saut et de poussée, car il se trouve au sommet de stack2 .

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 étape par étape est disponible sur ma page Web de blog.

Vous devrez tout sauter de la première pile pour obtenir l'élément du bas. Ensuite, remettez-les tous sur la deuxième pile pour chaque opération de «retrait».

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

Implémentez les opérations suivantes d'une file d'attente à l'aide de piles.

push (x) - Poussez l'élément x à l'arrière de la file d'attente.

pop () - Supprime l'élément devant la file d'attente.

peek () - Récupère l'élément frontal.

empty () - Retourne si la file d'attente est vide.

class MyQueue {

  Stack<Integer> input;
  Stack<Integer> output;

  /** Initialize your data structure here. */
  public MyQueue() {
    input = new Stack<Integer>();
    output = new Stack<Integer>();
  }

  /** Push element x to the back of queue. */
  public void push(int x) {
    input.push(x);
  }

  /** Removes the element from in front of queue and returns that element. */
  public int pop() {
    peek();
    return output.pop();
  }

  /** Get the front element. */
  public int peek() {
    if(output.isEmpty()) {
        while(!input.isEmpty()) {
            output.push(input.pop());
        }
    }
    return output.peek();
  }

  /** Returns whether the queue is empty. */
  public boolean empty() {
    return input.isEmpty() && output.isEmpty();
  }
}

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

        }
    }

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

Bien que vous obtiendrez de nombreux articles liés à 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/

Un moyen important que j'ai découvert dans le post ci-dessus était de construire une file d'attente avec uniquement la structure de données de la pile et la pile des appels de récursivité.

Bien que l'on puisse affirmer que cela utilise littéralement deux piles, mais dans l'idéal, cela n'utilise qu'une seule structure de données de pile.

Voici l'explication du problème:

1. Déclarez une seule pile pour la mise en file d'attente et la suppression des données et poussez les données dans la pile.

2. tandis que deQueueing a une condition de base où l'élément de la pile est déplacé lorsque la taille de la pile est de 1. Cela garantira qu'il n'y aura pas de débordement de pile pendant la récursivité deQueue.

3. Pendant que deQueueing fait d'abord apparaître les données du haut de la pile. Idéalement, cet élément sera l'élément présent en haut de la pile. Maintenant, une fois cela fait, appelez récursivement la fonction deQueue, puis repoussez l'élément sauté ci-dessus dans la pile.

Le code ressemblera à 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 de pile unique et de la pile d'appels de récursivité.

Voici 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 };

Voici 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"

Je répondrai à cette question dans Go parce que Go n'a pas beaucoup de collections riches dans sa bibliothèque standard.

Puisqu'une pile est vraiment facile à implémenter, j'ai pensé essayer d'utiliser deux piles pour accomplir une file d'attente à double extrémité. Pour mieux comprendre comment je suis arrivé à ma réponse, j'ai divisé l'implémentation en deux parties, la première partie est, je l'espère, 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 où nous permettons au bas des piles d'être manipulées l'une par l'autre. J'ai également utilisé les conventions de dénomination STL, où les opérations traditionnelles push, pop, peek d'une pile ont un préfixe avant / arrière, qu'elles se réfèrent à 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 très efficacement. En fait, il se développe sans cesse jusqu'à ce que vous manquiez d'espace. C'est vraiment mauvais. La solution consiste à réutiliser simplement le bas de l'espace de pile chaque fois 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étrécie.

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 sur les 6 fonctions, 3 d'entre elles ne sont que des miroirs de l'autre.

voici ma solution en java en utilisant une liste liée.

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. Je ne suggère donc pas de créer une file d'attente en utilisant deux piles.

Avec O(1) dequeue(), qui est identique à la réponse 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()(cela n'est pas mentionné dans cet article, donc cette réponse), qui utilise également le retour arrière pour faire bouillonner et renvoyer l'article 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 inefficace mais élégant néanmoins.

** Solution JS facile **

• Remarque: j'ai pris des idées de commentaires d'autres personnes

/*

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.

*/
class myQueue {
    constructor() {
        this.stack1 = [];
        this.stack2 = [];
    }

    push(item) {
        this.stack1.push(item)
    }

    remove() {
        if (this.stack1.length == 0 && this.stack2.length == 0) {
            return "Stack are empty"
        }

        if (this.stack2.length == 0) {

            while (this.stack1.length != 0) {
                this.stack2.push(this.stack1.pop())
            }
        }
        return this.stack2.pop()
    }


    peek() {
        if (this.stack2.length == 0 && this.stack1.length == 0) {
            return 'Empty list'
        }

        if (this.stack2.length == 0) {
            while (this.stack1.length != 0) {
                this.stack2.push(this.stack1.pop())
            }
        }

        return this.stack2[0]
    }

    isEmpty() {
        return this.stack2.length === 0 && this.stack1.length === 0;
    }

}

const q = new myQueue();
q.push(1);
q.push(2);
q.push(3);
q.remove()

console.log(q)

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 en haut de la pile1. Pour chaque file d'attente, nous vidons le contenu de stack1 dans stack2 et supprimons l'élément en haut de la pile. La complexité du temps 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 la même qu'une pile régulière

Implémentation de la file d'attente à l'aide de deux objets java.util.Stack:

public final class QueueUsingStacks<E> {

        private final Stack<E> iStack = new Stack<>();
        private final Stack<E> oStack = new Stack<>();

        public void enqueue(E e) {
            iStack.push(e);
        }

        public E dequeue() {
            if (oStack.isEmpty()) {
                if (iStack.isEmpty()) {
                    throw new NoSuchElementException("No elements present in Queue");
                }
                while (!iStack.isEmpty()) {
                    oStack.push(iStack.pop());
                }
            }
            return oStack.pop();
        }

        public boolean isEmpty() {
            if (oStack.isEmpty() && iStack.isEmpty()) {
                return true;
            }
            return false;
        }

        public int size() {
            return iStack.size() + oStack.size();
        }

}