Queues

Reading time10 min

En bref

Résumé de l’article

Dans cet article, nous vous présentons une structure de données appelée “queue” (file d’attente). Avec cette structure, les éléments sont retirés dans l’ordre dans lequel ils ont été ajoutés.

Deux implémentations possibles d’une queue sont discutées. L’une est introduite ici, et l’autre fait l’objet de la séance pratique. Il est montré qu’elles peuvent être utilisées indépendamment si les primitives abstraient les détails.

Points clés

  • Les queues sont des structures de données où le premier élément ajouté est le premier élément retiré.

  • Selon l’implémentation de la queue, certaines opérations peuvent prendre plus de temps que d’autres.

  • L’utilisation de primitives permet de cacher les détails d’implémentation.

Contenu de l’article

1 — Qu’est-ce qu’une queue ?

Une queue est une structure de données à accès restreint où le premier élément entré est le premier élément sorti. Cette méthode d’accès est appelée FIFO (First In, First Out). Gérer une queue consiste à ajouter des éléments à la fin de la queue (enqueue) et à retirer des éléments au début (dequeue).

Opérations sur une queue

Les queues sont moins courantes en algorithmique que les piles car leur champ d’application est moins étendu. Cependant, il existe des domaines où elles sont utiles, comme la gestion du flux de personnes à un guichet, où le premier arrivé est le premier servi.

2 — Primitives

Dans un programme utilisant une queue, les détails d’implémentation des données sont abstraits. Le programme se contente d’enfiler ou de défiler des éléments de la queue en utilisant des sous-programmes appelés “primitives de gestion”. Les principales primitives pour les opérations sur une queue sont :

  • initialize – Initialise la queue.
  • push – Ajoute un élément à la fin de la queue.
  • pop – Retire le premier élément de la queue.
  • is_empty – Renvoie true si la queue est vide, et false sinon.

Comme pour les piles, les queues peuvent être implémentées sous forme de “tableaux” ou de “listes chaînées”.

3 — Implémentation des queues

En pratique, chaque langage de programmation offre une implémentation adéquate d’une queue. Ici, nous montrons des implémentations possibles à des fins pédagogiques.

3.1 — Utilisation d’une liste

Gérer une queue peut se faire en ajoutant des éléments au début de la liste (enfiler) et en retirant des éléments à la fin de la liste (défiler), ou vice versa.

Voici une implémentation possible d’une queue, utilisant une liste pour stocker les informations :

​
"""
    This module provides an implementation of the primitives to handle a queue of values. 
    The queue is materialized by means of a list with a size limit to simulate an array.

"""

# Needed imports
from typing import List,Any

# Define your own custom type
Queue = List[Any]



def initialize() -> Queue:

    """
        Initializes an empty queue.
        In:
            * None.
        Out:
            * An empty queue.
    """

    # We use lists to represent queues
    return []



def is_empty (queue: Queue) -> bool:

    """
        This function checks if the queue is empty.
        In:
            * queue: Queue to check.
        Out:
            * True if the queue is empty, False otherwise.
    """

    # Check list length
    return len(queue) == 0



def push (queue: Queue, item: Any) -> None:

    """
        This function adds an element to the queue.
        The element is added at the last position of the storage structure.
        In:
            * queue: Queue to modify.
            * item:  Element to add.
    """

    # Add the element to the end of the list
    queue.append(item)



def pop (queue: Queue) -> Any:
    
    """
        This function removes the next element of the queue.
        In:
            * queue: Queue to modify.
        Out:
            * The next element of the queue.
    """
    
    # Extract and return the first element of the list
    return queue.pop(0)



def display (queue: Queue) -> None:
    
    """
        This function displays the content of the queue.
        In:
            * queue: Queue to display.
        Out:
            * None.
    """

    # Shows the list
    print(queue)
import java.util.ArrayList;
import java.util.List;

public class ListQueue {
    private List<Object> queue;

    public ListQueue() {
        this.queue = new ArrayList<>();
    }

    public boolean isEmpty() {
        /**
         * This function checks if the queue is empty.
         * @return True if the queue is empty, False otherwise.
         */
        return this.queue.isEmpty();
    }

    public void push(Object item) {
        /**
         * This function adds an element to the queue.
         * The element is added at the beginning of the list.
         * @param item Element to add.
         */
        this.queue.add(0, item);
    }

    public Object pop() {
        /**
         * This function removes the last element of the queue.
         * @return The removed element.
         */
        if (this.queue.isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        return this.queue.remove(this.queue.size() - 1);
    }
}

3.2 — Utilisation de listes doublement chaînées

Une liste doublement chaînée peut être utilisée pour implémenter une pile ou une queue. Enfiler crée un nouvel élément qui est ajouté au début de la liste doublement chaînée, comme avec une pile. Mais défiler consiste, dans le cas d’une queue, à retirer l’élément à sa queue, alors que c’est l’élément à sa tête dans le cas d’une pile.

L’implémentation d’une queue utilisant une liste doublement chaînée est laissée à l’activité pratique.

4 — Un usage pratique

Voici un exemple simple de programme qui utilise une queue pour traiter une chaîne de caractères.

​
# Ask for a string
s = input("Enter a string: ")

# Initialize a queue with the length of the string
my_queue = initialize()
for i in range(len(s)):
    push(my_queue, s[i])

# Process the elements one by one
result = ""
while not is_empty(my_queue):
    result += pop(my_queue)

# Show the result
print(f"Characters of {s} processed in order using a queue:")
display(result)
/**
 * Three elements processed in order using a queue
 **/
public static void main(String[] args) {
        ListQueue queue = new ListQueue();
        queue.push(1);
        queue.push(2);
        queue.push(3);
        System.out.println("Queue after pushes: " + queue.queue);
        System.out.println("Popped element: " + queue.pop());
        System.out.println("Queue after pop: " + queue.queue);
    }

Pour aller plus loin

Rappelez-vous que tous les exemples ci-dessus sont pédagogiques, et faits pour comprendre comment créer des structures. Pour de telles structures simples, vous devriez utiliser les implémentations par défaut.

Par exemple, il est plus approprié d’utiliser la classe deque de Python dans le package collections, qui fournit des opérations optimales pour enfiler et défiler.

Un exercice dans l’activité pratique illustrera le gain d’efficacité lorsque des structures de données appropriées et optimisées sont utilisées.

Pour aller encore plus loin