Fiche de révision : NSI piles et files

Qu'est-ce qu'une pile ?

Une pile est une structure de données qui suit le principe LIFO (Last In, First Out).

Opérations principales sur une pile ?

- push : ajouter un élément - pop : retirer un élément - peek : consulter le sommet

Vrai ou faux : Les piles permettent un accès aléatoire.

Faux. Les piles ne permettent qu'un accès séquentiel, uniquement au sommet.

Remplissez le vide : Une pile est utilisée pour ...

gérer les appels de fonction (récursion).

Exemple d'application des piles ?

Gestion des historiques de navigation dans un navigateur web.

Comparaison entre pile et tableau.

Une pile : - Accès LIFO - Taille dynamique Un tableau : - Accès aléatoire - Taille fixe (ou dynamique)

Qu'est-ce que l'opération push ?

L'opération push ajoute un nouvel élément au sommet de la pile.

Qu'est-ce que l'opération pop ?

L'opération pop retire le dernier élément ajouté à la pile et le retourne.

Vrai ou faux : Une pile peut contenir des éléments de types différents.

Vrai, si la pile est définie pour accepter des types variés.

Quels types d'algorithmes utilisent des piles ?

- Algorithmes de conversion de notation - Algorithmes de parcours en profondeur (DFS)

Définissez l'opération peek.

L'opération peek permet de voir l'élément au sommet de la pile sans le retirer.

Vrai ou faux : Les piles sont toujours dynamiques.

Faux. Les piles peuvent être statiques ou dynamiques selon leur implémentation.

Exemples de langages avec support de piles ?

Java, Python, C++ et JavaScript gèrent les piles via des fonctions ou des classes.

Qu'est-ce qu'un débordement de pile ?

Un débordement de pile se produit lorsque la pile dépasse sa capacité maximale.

Quelle est la complexité temporelle de push et pop ?

Les deux opérations ont une complexité temporelle de $\displaystyle O(1)$.

Remplissez le vide : Une pile est souvent utilisée pour ...

réaliser des algorithmes de backtracking.

Qu'est-ce qu'une file ?

Une file est une structure de données qui suit le principe FIFO (First In, First Out). Le premier élément ajouté est le premier à être retiré.

Quelle est l'opération pour ajouter un élément dans une file ?

L'opération pour ajouter un élément dans une file est appelée 'enqueue'.

Quelle est l'opération pour retirer un élément d'une file ?

L'opération pour retirer un élément d'une file est appelée 'dequeue'.

Vrai ou faux : Les files sont LIFO.

Faux. Les files sont FIFO, contrairement aux piles qui sont LIFO.

Quelles sont les applications des files ?

- Gestion des tâches - Imprimantes - Simulation de systèmes - Réseaux informatiques

Comment représenter une file en mémoire ?

Une file peut être représentée par un tableau ou une liste chaînée.

Complétez : Dans une file, les éléments sont retirés de l'___ et ajoutés à l'___.

Avant, arrière.

Quelle est la complexité temporelle d'une opération 'enqueue' ?

O(1), constant, car l'ajout se fait à la fin.

Quelle est la complexité temporelle d'une opération 'dequeue' ?

O(1), constant, car le retrait se fait au début.

Donnez un exemple d'utilisation de files.

Dans une banque : les clients attendent leur tour, le premier arrivé est le premier servi.

Qu'est-ce qu'une file circulaire ?

Une file circulaire est une structure où la fin de la file est reliée au début, permettant une utilisation efficace de l'espace.

Vrai ou faux : Une file peut contenir des éléments de types différents.

Faux. Généralement, une file contient des éléments du même type.

Quel est le rôle d'une file d'attente dans un serveur web ?

Elle gère les requêtes des utilisateurs en les traitant dans l'ordre de leur arrivée.

Quelles sont les variations de files ?

- File prioritaire - Double file - File circulaire

Qu'est-ce qu'une file prioritaire ?

Une file où chaque élément a une priorité, et les éléments de haute priorité sont servis avant ceux de basse priorité.

Illustration : Comment fonctionne une file ?

1. Enqueue(1) → [1] 2. Enqueue(2) → [1, 2] 3. Dequeue() → [2]