Problématique

232. Implémenter une file d'attente avec des piles

Utilisez deux piles pour implémenter une file d'attente de premier entré, premier sorti (FIFO). Votre file d'attente doit prendre en charge toutes les opérations standard (ajouter, retirer, consulter, vérifier si vide) :

Implémentez la classe FileAttente :

• void ajouter(int x) : ajoute un élément x à la fin de la file
• int retirer() : supprime et retourne l'élément au début de la file
• int premier() : retourne l'élément au début de la file sans le supprimer
• boolean estVide() : retourne vrai si la file est vide, sinon faux

Spécifications :

• Vous ne pouvez utiliser que les opérations standard des piles : empiler en sommet, dépiler/consulter sommet, taille, et est vide.
• Votre langage de programmation peut ne pas avoir de structure de pile native. Vous pouvez utiliser une liste ou une deque pour simuler une pile, tant que vous respectez les opérations standard.

Exemple 1 :

<strong>Entrée :</strong>
["FileAttente", "ajouter", "ajouter", "premier", "retirer", "estVide"]
[[], [1], [2], [], [], []]
<strong>Sortie :</strong>
[null, null, null, 1, 1, false]

Solution

L'utilisation de deux piles pour simuler une file d'attente repose sur le principe d'inversion d'ordre. Une pile suit le principe dernier entré, premier sorti (LIFO), alors qu'une file suit le principe premier entré, premier sorti (FIFO).

La première pile sert à stocker les éléments entrants. Lorsqu'on doit retirer un élément, on transfert tous les éléments de la première pile vers la deuxième pile, ce qui inverse leur ordre. Les éléments peuvent ensuite être retirés de la deuxième pile dans l'ordre d'origine.

Voici l'implémentation :

type FileAttente struct {
    entree []int
    sortie []int
}

func Constructeur() FileAttente {
    return FileAttente{}
}

func (c *FileAttente) Ajouter(x int) {
    c.entree = append(c.entree, x)
}

func (c *FileAttente) transferer() {
    for len(c.entree) > 0 {
        element := c.entree[len(c.entree)-1]
        c.entree = c.entree[:len(c.entree)-1]
        c.sortie = append(c.sortie, element)
    }
}

func (c *FileAttente) Retirer() int {
    if len(c.sortie) == 0 {
        if len(c.entree) == 0 {
            return -1
        }
        c.transferer()
    }
    
    element := c.sortie[len(c.sortie)-1]
    c.sortie = c.sortie[:len(c.sortie)-1]
    return element
}

func (c *FileAttente) Premier() int {
    if len(c.sortie) == 0 {
        if len(c.entree) == 0 {
            return -1
        }
        c.transferer()
    }
    return c.sortie[len(c.sortie)-1]
}

func (c *FileAttente) EstVide() bool {
    return len(c.entree) == 0 && len(c.sortie) == 0
}

/**
 * Votre objet FileAttente sera instancié et appelé comme suit :
 * obj := Constructeur();
 * obj.Ajouter(x);
 * param_2 := obj.Retirer();
 * param_3 := obj.Premier();
 * param_4 := obj.EstVide();
 */

L'aspect crucial à retenir est que lors des opérations premier et retirer, il faut vérifier si la pile de sortie est vide. Si c'est le cas, on transfère les éléments de la pile d'antrée vers la pile de sortie avant d'effectuer l'opération. Cette approche garantit que la file d'attente fonctionne correctement selon le principe FIFO.