Piles et files d'attente

Vue d'ensemble

Dans le domaine de l'informatique, les piles et les files d'attente sont des structures de données courantes qui spécifient l'ordre dans lequel vous pouvez ajouter et supprimer des éléments. Vous pouvez les utiliser pour contrôler l'ordre dans lequel vous interagissez avec les données.

• Pile : conteneur dans lequel vous insérez et retirez des éléments dans l'ordre « premier entré, dernier sorti » (FILO), comme si vous preniez le premier ouvrage posé sur une pile de livres.

• File d'attente : conteneur dans lequel vous insérez et retirez des éléments dans l'ordre « premier entré, premier sorti » (FIFO), comme dans le cas de clients d'une cafétéria.

Bien que le code sous-jacent des piles et des files d'attente soit similaire, chaque code présente des différences essentielles et des atouts sur lesquels vous appuyer pour rendre votre expérience rapide, efficace et intuitive.

Piles

Prenons l'exemple d'une pile de crêpes. Supposons que vous soyez dans un hôtel pour prendre votre petit-déjeuner et que le serveur vous propose une pile infinie de crêpes. Par politesse, vous ne prendrez qu'une seule crêpe à la fois, en commençant par le haut de la pile. Vous pouvez demander à votre serveur de placer une nouvelle crêpe au sommet de la pile et, une fois votre crêpe terminée, dépiler celle du haut pour la mettre dans votre assiette en vue de la manger. Pour déguster une crêpe précise au milieu de la pile, vous devez continuer à les manger en partant du haut de la pile jusqu'à ce que vous arriviez à celle de votre choix. La première crêpe posée sera donc la dernière que vous retirerez. La pile est donc une structure de données FILO (premier entré, dernier sorti).

Quand les utiliser

Les piles sont utiles lorsque vous avez besoin de revenir en arrière ou de vous souvenir de l'ordre dans lequel vous avez déclenché des événements. Il peut s'agir d'une fonction d'annulation, d'une chaîne d'événements ou d'une série de choix. Par exemple, vous disposez d'un robot qui doit traverser un labyrinthe aux innombrables bifurcations. Lorsque le robot arrive à une bifurcation, il choisit un chemin et place ce choix sur la pile. Lorsqu'il se trouve dans une impasse, il revient en arrière dans la pile, dépilant ses choix jusqu'à ce qu'il trouve un nouveau chemin à emprunter.

Implémentation dans Verse

L'implémentation de piles n'est pas une fonction intégrée de l'API Verse, mais vous pouvez la créer.

Vous pouvez représenter les éléments d'une pile à l'aide de n'importe quelle structure de données ordonnée, comme une matrice ou une liste chaînée. Dans cet exemple, vous utiliserez une matrice, car elle vous permet d'accéder facilement au sommet de la pile.

stack<public>(t:type) := class:
    Elements<internal>:[]t = array{}

La matrice Elements stocke les objets de la pile, qui sont de type t. Autrement dit, vous pouvez initialiser une pile avec n'importe quel type d'élément, notamment int, float, stack, etc. L'utilisation de type comme argument de la classe de pile est un exemple de type paramétrique.

Définissons tout d'abord certaines fonctions d'aide. Vous devez savoir où se trouve le sommet de la pile pour pouvoir y placer (Push()) ou en retirer (Pop()) des éléments. Pour cela, vous avez besoin de trois fonctions : Size(), IsEmpty() et Peek().

# Returns the size of the stack.
    Size<public>()<transacts>:int=
        Elements.Length

    # Succeeds if the stack is empty.
    IsEmpty<public>()<decides><transacts>:void=
        Size() = 0

    # Returns the top element of the stack.
    Peek<public>()<decides><transacts>:t=

La fonction Size() renvoie simplement la longueur (Length) de la matrice Elements. La fonction IsEmpty() appelle la fonction Size() et possède le spécificateur <transacts>, ce qui signifie qu'elle échoue si Size() n'est pas égal à 0.

La fonction Peek() renvoie l'élément à l'index supérieur (Length - 1) de la matrice Elements. Cette fonction possède les spécificateurs <decides><transacts>, car l'accès à la matrice peut échouer si la matrice est vide.

Pour instancier une pile, vous pouvez utiliser une fonction de constructeur. Un constructeur est une fonction spéciale qui crée une instance de la classe à laquelle il est associé. Le constructeur définit les valeurs initiales d'un objet et vous permet d'accéder à la valeur d'Elements et de l'assigner à une matrice d'éléments initiale.

# Creates and returns a stack from an initial array of elements InitialElements.
CreateStack<public><constructor>(InitialElements:[]t where t:type) := stack(t):
    Elements := InitialElements

Placer et dépiler

Pour ajouter ou retirer des éléments de la pile, vous devez soit placer (fonction push) le nouvel élément au sommet de la pile, soit le dépiler (fonction pop) du sommet.

# Adds NewElement to the top of the stack by returning a new
# stack with NewElement as the top
Push<public>(NewElement:t):stack(t)=
    stack(t){Elements := Elements + array{NewElement}}

# Removes the element on top of the stack and returns a tuple of both a new
# stack with the top element removed and the removed element.
Pop<public>()<decides><transacts>:tuple(stack(t),t)=
    FirstElement := Peek[]
    (stack(t){Elements := Elements.RemoveElement[Elements.Length - 1]}, FirstElement)

La fonction Push() prend l'élément que vous souhaitez placer au sommet de la pile et renvoie une nouvelle pile avec l'élément au sommet. Renvoyer une nouvelle pile plutôt que de modifier la pile actuelle est un exemple de programmation fonctionnelle, qui permet de réduire le risque d'effets secondaires.

Pour implémenter la fonction Pop(), vous devez tout d'abord rechercher l'élément au sommet de la pile en utilisant Peek(). Vous devez ensuite retirer l'élément du sommet (en utilisant la fonction RemoveElement[]) et renvoyer une nouvelle pile sans l'élément. Vous pouvez utiliser un tuple pour renvoyer simultanément la nouvelle pile et l'élément retiré. En raison des expressions faillibles pour l'accès à la matrice et de l'appel à Peek(), Pop() doit avoir les spécificateurs <decides><transacts>.

Code complet

Le code complet de la classe de pile est fourni ci-dessous.

stack<public>(t:type) := class:
    Elements<internal>:[]t = array{}

    # Adds NewElement to the top of the stack by returning a new
    # stack with NewElement as the top
    Push<public>(NewElement:t):stack(t)=
        stack(t){Elements := Elements + array{NewElement}}

    # Removes the element on top of the stack and returns a tuple of both a new
    # stack with the top element removed and the removed element.

Files d'attente

Considérons une file d'attente comme un tapis roulant de sushis. Supposons que vous soyez dans un restaurant de sushis. Vous recevez les assiettes de sushis une par une sur un tapis roulant dans l'ordre où vous les avez commandées. Vous pouvez dépiler (fonction dequeue) l'assiette qui se trouve au début de la ligne pour la prendre et manger son contenu, mais vous ne pouvez prendre qu'une assiette à la fois. Lorsque vous souhaitez commander une nouvelle assiette, vous demandez au chef d'empiler (fonction enqueue) une assiette et de la poser à la fin. Si la liste de commandes comporte déjà d'autres assiettes de sushis, vous devrez continuer à manger le contenu des assiettes placées les premières sur le tapis avant d'arriver à la dernière assiette. La première assiette de sushi placée sur le tapis est la première que vous retirez. La file d'attente est donc une structure de données FIFO, c'est-à-dire premier entré, premier sorti.

Quand les utiliser

Les files d'attente sont utiles lorsque vous devez traiter des données selon leur ordre de réception. Il peut s'agir de servir des clients à un drive-in, de mettre les appels d'un centre d'appels en attente ou de poser une série de questions à un joueur lors d'un entretien. Par exemple, si vous devez créer une salle d'attente pour des joueurs qui effectuent une tâche ou vivent une expérience chacun à leur tour, vous pouvez utiliser une file d'attente pour classer les joueurs en fonction de leur arrivée, selon le principe du premier arrivé, premier servi.

Implémentation dans Verse

L'implémentation de files d'attente n'est pas une fonction intégrée de l'API Verse, mais vous pouvez la créer.

Comme pour les piles, vous pouvez représenter les éléments d'une file d'attente à l'aide de n'importe quelle structure de données ordonnée, comme une matrice ou une liste chaînée. Dans cet exemple, vous utiliserez une matrice, car elle vous permet d'accéder facilement au début et à la fin de la file d'attente. Pour implémenter une file d'attente à l'aide d'une liste chaînée, consultez cet extrait de code.

queue<public>(t:type) := class:
    Elements<internal>:[]t = array{}

La matrice Elements stocke les objets de la file d'attente de type t. En d'autres termes, vous pouvez initialiser une file d'attente avec n'importe quel type d'élément, notamment int, float, queue, etc. L'utilisation de type comme argument de la classe de pile est un exemple de type paramétrique.

Comme les piles, les files d'attente nécessitent certaines fonctions d'aide. Vous devez savoir où se trouvent le début et la fin de la file d'attente pour pouvoir utiliser les fonctions Enqueue() et Dequeue(). Il est également utile de connaître la taille de la file d'attente et de savoir si elle est vide. Les quatre fonctions Size(), IsEmpty(), Front() et Back() vous seront utiles à cet effet.

# Returns the size of the queue
Size<public>()<transacts>:int=
    Elements.Length

# Succeeds if the queue is empty
IsEmpty<public>()<decides><transacts>:void=
    Size() = 0

# Returns the element at the front of the queue.
Front<public>()<decides><transacts>:t=

La fonction Size() renvoie la longueur (Length) de la matrice Elements. La fonction IsEmpty() appelle la fonction Size() et possède le spécificateur <transacts>, ce qui signifie qu'elle échoue si Size() n'est pas égal à 0.

Les fonctions Front() et Rear() renvoient l'élément à l'index de début (index 0) et de fin (Length - 1) de la matrice `Elements`. Ces deux fonctions ont les spécificateurs <decides><transacts>, car l'accès à la matrice peut échouer si la matrice est vide.

À l'instar de la classe stack, la classe queue doit utiliser une fonction de constructeur pour assigner la matrice Elements. La fonction de constructeur vous permet d'accéder à la valeur d'Elements et de l'assigner à une matrice d'éléments initiale.

# Creates and returns a queue from an initial array of elements InitialElements.
CreateQueue<public><constructor>(InitialElements:[]t where t:type) := queue(t):
    Elements := InitialElements

Empiler et dépiler

Pour ajouter ou retirer des éléments de la file d'attente, vous devez empiler (fonction Enqueue) le nouvel élément à la fin de la file d'attente ou dépiler (fonction Dequeue) un élément du haut de la file.

# Adds a new element to the back of the queue by returning a
# new queue with NewElement at the back.
Enqueue<public>(NewElement:t):queue(t)=
    queue(t){Elements := Elements + array{NewElement}}

# Removes the element at the front of the queue and returns a tuple of
# both a new queue with the element removed and the removed element.
Dequeue<public>()<decides><transacts>:tuple(queue(t),t)=
    FirstElement := Front[]
    (queue(t){Elements := Elements.RemoveElement[0]}, FirstElement)

La fonction Enqueue() prend l'élément que vous souhaitez insérer dans la file d'attente et renvoie une nouvelle file d'attente avec le nouvel élément à la fin. Renvoyer une nouvelle file d'attente plutôt que de modifier la file d'attente actuelle est un exemple de programmation fonctionnelle, qui permet de réduire le risque d'effets secondaires.

Pour la fonction Dequeue(), vous devez supprimer et renvoyer l'élément en tête de la file d'attente et renvoyer une nouvelle file d'attente avec le premier élément supprimé (en utilisant la fonction RemoveElement[]). En raison des expressions faillibles pour l'accès à la matrice et de l'appel à Front(), Dequeue() doit avoir les spécificateurs <decides><transacts>.

Code complet

Le code complet de la classe File d'attente est fourni ci-dessous.

queue<public>(t:type) := class:
    Elements<internal>:[]t = array{}

    # Adds a new element to the back of the queue by returning a
    # new queue with NewElement at the back.
    Enqueue<public>(NewElement:t):queue(t)=
        queue(t){Elements := Elements + array{NewElement}}

    # Removes the element at the front of the queue and returns a tuple of
    # both a new queue with the element removed and the removed element.

À vous de jouer

Il existe de nombreuses façons d'itérer et d'améliorer les piles et les files d'attente. Découvrez et expérimentez les différentes façons d'ajouter des fonctionnalités. Voici quelques idées pour vous aider à vous lancer :

• Pouvez-vous convertir une file d'attente en file d'attente circulaire, où le dernier élément est connecté au premier élément et où la file d'attente s'exécute en boucle ?

• Que diriez-vous de programmer une file d'attente comportant des priorités, où les objets sont classés en fonction de leur entrée dans la file d'attente ET d'une autre valeur ?

• Pouvez-vous créer des jeux de type Tours de Hanoï à l'aide d'une pile ? Sauriez-vous créer un jeu de type restaurant, dans lequel les clients doivent attendre dans une file ?