Pile ou file

• Pile. La dernière parenthèse ouverte est la première à devoir se fermer : la structure du problème est la discipline lifo. Ce n'est pas un choix d'ingénieur, c'est une constatation.
• File. « Dans l'ordre d'arrivée » est la définition de fifo. Une pile servirait les derniers arrivés d'abord, et les premiers pourraient attendre indéfiniment — c'est ce qu'on appelle la famine.
• Pile. On annule la dernière action faite. Et pour offrir aussi un « refaire », il faut deux piles : l'action dépilée de la pile d'annulation est empilée sur celle de rétablissement, laquelle est vidée dès qu'une action neuve est faite.
• File. Et c'est le cas le moins évident. Une pile explore aussi tout le labyrinthe, mais elle plonge dans un couloir jusqu'au bout avant d'essayer le suivant : les cases sont atteintes par un chemin quelconque. La file, elle, traite les cases par distance croissante à l'origine, donc la première fois qu'elle atteint une case, c'est par un plus court chemin. Le troisième problème de ce chapitre le mesure sur une grille.

Le critère général, et il vaut pour tout le livre : demandez-vous dans quel ordre les éléments doivent ressortir. Si le dernier entré doit sortir en premier — parce qu'il faut « défaire » ce qu'on vient de faire, ou parce qu'on suit une imbrication — c'est une pile. Si l'ordre d'entrée doit être respecté — équité, distance, ancienneté — c'est une file. Toutes les autres considérations (tableau ou maillons, capacité, coût) viennent après ce choix, et ne le remettent jamais en cause.