Files et collections.deque
Ajouter et retirer rapidement des deux extrémités
Files et collections.deque est une leçon Competitive Programming Academy gratuite sur CoddyKit. Ceci est la leçon 3 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Competitive Programming Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Competitive Programming Academy comprend 4 leçons au total.
Premier entré, premier sorti
Une file sert les éléments dans l’ordre de leur arrivée, comme une file d’attente dans un magasin. Le premier entré est le premier sorti.
Pourquoi ne pas utiliser une liste
Une liste peut retirer un élément au début, mais pop(0) coûte O(n), car tous les autres éléments sont décalés vers la gauche. C’est trop lent pour de grandes entrées.
q = []
q.pop(0) # O(n), avoid thisDécouvrir collections.deque
Le type file à double extrémité est une file qui ajoute et retire des éléments à ses deux extrémités en O(1). C’est votre outil de prédilection pour les concours.
from collections import deque
q = deque()Enfiler à l’arrière
Ajoutez les nouveaux éléments à l’extrémité droite avec append, exactement comme dans une liste. Il s’agit de l’arrière de la file.
q.append(1)
q.append(2)Défiler à l’avant
Retirez l’élément le plus ancien à gauche avec popleft, une opération en temps constant qui fournit un véritable comportement FIFO.
first = q.popleft() # returns 1Les deux extrémités sont ouvertes
Une file à double extrémité prend également en charge appendleft et pop à droite. Cette souplesse permet à une seule structure de jouer le rôle d’une pile ou d’une file.
q.appendleft(0)
last = q.pop()Vérifier avant de retirer
Retirer un élément d’une file à double extrémité vide déclenche une erreur. Dans les boucles, testez donc while q pour que votre parcours reste sûr.
while q:
x = q.popleft()Les files alimentent BFS
L’utilisation la plus courante dans les concours est BFS. Vous enfilez un nœud de départ, puis retirez toujours l’élément à l’avant et ajoutez ses voisins.
Un petit squelette de BFS
Cette boucle visite les nœuds couche par couche. Chaque voisin est ajouté, puis traité dans l’ordre de son arrivée.
while q:
node = q.popleft()
for nb in graph[node]:
q.append(nb)Limiter la taille de la file à double extrémité
Indiquer une longueur maximale fait supprimer le plus ancien élément lorsque la file est pleine, ce qui convient parfaitement aux fenêtres glissantes et au suivi de l’historique récent.
window = deque(maxlen=3)Une structure, de nombreux rôles
N’oubliez pas qu’une file à double extrémité est rapide à ses deux extrémités. Utilisez-la donc chaque fois que vous avez besoin d’une file, d’une pile ou d’un tampon glissant.
Vérification rapide
Vous avez besoin de retirer rapidement un élément à l’avant d’une file. Quel choix convient ?
Récapitulatif : la file à double extrémité est rapide
Vous avez découvert collections.deque : append et popleft pour un comportement FIFO en O(1), deux extrémités accessibles et une longueur maximale pour les fenêtres. C’est la structure fondamentale de BFS. 🎯
Questions Fréquemment Posées
La leçon « Files et collections.deque » est-elle gratuite ?
Oui — le texte complet de « Files et collections.deque » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Competitive Programming Academy, passe à CoddyKit PRO. Le cours Competitive Programming Academy comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Files et collections.deque » ?
Ajouter et retirer rapidement des deux extrémités Tu pratiques Competitive Programming Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Competitive Programming Academy ?
Aucune expérience préalable n'est requise. Competitive Programming Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 3 sur 4.
Combien de temps prend la leçon « Files et collections.deque » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Competitive Programming Academy ?
Oui. Chaque leçon Competitive Programming Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Piles pour faire correspondre les parenthèses
- Pile monotone : élément suivant plus grand
- Files et collections.deque
- Maximum d’une fenêtre glissante avec une deque