Implémentation d’une file et d’une deque
Construisez une file avec deque de Python, implémentez une file circulaire et résolvez le maximum d’une fenêtre glissante avec une deque monotone.
Implémentation d’une file et d’une deque est une leçon DSA Interview Prep gratuite sur CoddyKit. Ceci est la leçon 2 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 DSA Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours DSA Interview Prep comprend 4 leçons au total.
La structure de données Queue
Une file est une structure de données premier entré, premier sorti (FIFO). Le premier élément mis en file est le premier élément retiré — comme dans une file d’attente à la caisse d’un magasin. Les opérations principales sont enqueue (ajouter à l’arrière) et dequeue (retirer à l’avant). Toutes deux doivent s’effectuer en O(1) pour que la file soit efficace.
Utiliser une liste Python comme file est tentant, mais incorrect : list.pop(0) coûte O(n), car tous les éléments doivent être décalés. L’outil approprié est collections.deque, qui fournit appendleft, append, popleft et pop en O(1).
from collections import deque
queue = deque()
# Enqueue (add to rear)
queue.append(10)
queue.append(20)
queue.append(30)
print('Queue:', queue) # deque([10, 20, 30])
# Peek front
print('Front:', queue[0]) # 10
# Dequeue (remove from front)
print('Dequeued:', queue.popleft()) # 10
print('Queue after:', queue) # deque([20, 30])Classe Queue utilisant une file à double extrémité
Encapsulez deque dans une classe Queue dotée d’opérations nommées, conformément à ce que les examinateurs attendent. En interne, enqueue appelle append et dequeue appelle popleft. L’opération peek lit queue[0] sans le retirer.
from collections import deque
class Queue:
def __init__(self):
self._data = deque()
def enqueue(self, val):
self._data.append(val)
def dequeue(self):
if self.is_empty():
raise IndexError('dequeue from empty queue')
return self._data.popleft()
def peek(self):
if self.is_empty():
raise IndexError('peek at empty queue')
return self._data[0]
def is_empty(self):
return len(self._data) == 0
def __len__(self):
return len(self._data)
q = Queue()
q.enqueue(1); q.enqueue(2); q.enqueue(3)
print(q.peek()) # 1
print(q.dequeue()) # 1
print(len(q)) # 2BFS avec une Queue
L’application classique d’une file est la recherche en largeur (BFS). Mettez la racine en file ; tant que la file n’est pas vide, retirez un nœud, traitez-le, puis mettez en file ses voisins non visités. Comme les nœuds sont traités niveau par niveau, BFS trouve naturellement le plus court chemin dans un graphe non pondéré. La file contient toujours des nœuds provenant d’au plus deux niveaux adjacents.
from collections import deque
def bfs(graph, start):
visited = {start}
queue = deque([start])
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbour in graph[node]:
if neighbour not in visited:
visited.add(neighbour)
queue.append(neighbour)
return order
graph = {0:[1,2], 1:[0,3,4], 2:[0,5], 3:[1], 4:[1], 5:[2]}
print(bfs(graph, 0)) # [0, 1, 2, 3, 4, 5]Queue circulaire (LeetCode 622)
LeetCode 622 « Concevoir une Queue circulaire » : implémenter une file de capacité fixe qui revient au début lorsqu’elle atteint la fin. Utilisez un tableau de taille k et deux pointeurs : head et tail. Ajoutez les éléments à la fin, retirez-les au début et calculez les positions modulo k. Une variable count permet de distinguer une file pleine d’une file vide (dans les deux cas, head == tail modulo k, sinon).
class MyCircularQueue:
def __init__(self, k):
self.data = [0] * k
self.head = 0
self.tail = 0
self.count = 0
self.k = k
def enQueue(self, value):
if self.isFull(): return False
self.data[self.tail] = value
self.tail = (self.tail + 1) % self.k
self.count += 1
return True
def deQueue(self):
if self.isEmpty(): return False
self.head = (self.head + 1) % self.k
self.count -= 1
return True
def Front(self):
return -1 if self.isEmpty() else self.data[self.head]
def Rear(self):
return -1 if self.isEmpty() else self.data[(self.tail - 1) % self.k]
def isEmpty(self): return self.count == 0
def isFull(self): return self.count == self.k
cq = MyCircularQueue(3)
print(cq.enQueue(1), cq.enQueue(2), cq.enQueue(3)) # True True True
print(cq.enQueue(4)) # False (full)
print(cq.Rear()) # 3
print(cq.isFull()) # True
print(cq.deQueue()) # True
print(cq.enQueue(4)) # TrueMaximum d’une fenêtre glissante avec une file à double extrémité monotone
LeetCode 239 « Maximum d’une fenêtre glissante » : pour chaque fenêtre de taille k, trouver l’élément maximal. La méthode par force brute coûte O(n*k). L’approche en O(n) utilise une file à double extrémité monotone décroissante qui stocke des indices. Pour chaque nouvel élément : retirez de l’avant les indices situés en dehors de la fenêtre ; retirez de l’arrière les indices associés à des valeurs plus petites (ils ne pourront jamais être le maximum d’une fenêtre ultérieure). L’avant contient toujours le maximum.
from collections import deque
def maxSlidingWindow(nums, k):
dq = deque() # stores indices, decreasing values
result = []
for i, n in enumerate(nums):
# Remove indices outside window
while dq and dq[0] < i - k + 1:
dq.popleft()
# Remove smaller elements from back
while dq and nums[dq[-1]] < n:
dq.pop()
dq.append(i)
if i >= k - 1:
result.append(nums[dq[0]])
return result
print(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3))
# [3, 3, 5, 5, 6, 7]Pourquoi une file à double extrémité plutôt qu’une simple liste pour une Queue ?
list.pop(0) de Python supprime le premier élément en O(n), car chaque élément restant doit être décalé d’une position vers la gauche. Pour n insertions et n suppressions, cela donne un coût total de O(n²). collections.deque est une liste doublement chaînée de blocs de taille fixe ; popleft s’effectue en O(1), car il suffit d’ajuster un pointeur. Pour un BFS sur un graphe de 10^5 nœuds, la différence entre O(n) et O(n²) est la différence entre 100 ms et 100 secondes.
import timeit
n = 10000
# Using list (O(n) per popleft)
list_time = timeit.timeit(
stmt='q = list(range(n)); [q.pop(0) for _ in range(n)]',
globals={'n': n}, number=10
)
# Using deque (O(1) per popleft)
from collections import deque
deque_time = timeit.timeit(
stmt='q = deque(range(n)); [q.popleft() for _ in range(n)]',
globals={'n': n, 'deque': deque}, number=10
)
print(f'List: {list_time:.4f}s')
print(f'Deque: {deque_time:.4f}s')
print(f'Speedup: {list_time / deque_time:.1f}x')Parcours par niveaux d’un arbre binaire (LeetCode 102)
LeetCode 102 « Parcours par niveaux d’un arbre binaire » : renvoyer toutes les valeurs des nœuds niveau par niveau. Utilisez une file ; au début de chaque niveau, notez la taille de la file (c’est le nombre de nœuds de ce niveau). Retirez exactement ce nombre de nœuds, en recueillant leurs valeurs et en mettant leurs enfants en file. Répétez jusqu’à ce que la file soit vide.
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def levelOrder(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
level = []
level_size = len(queue)
for _ in range(level_size):
node = queue.popleft()
level.append(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
result.append(level)
return result
root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
print(levelOrder(root)) # [[3], [9, 20], [15, 7]]File de priorité avec heapq
Le module heapq de Python fournit un tas-min (file de priorité) : l’élément le plus petit est toujours retiré en premier. heapq.heappush(h, item) ajoute un élément en O(log n) et heapq.heappop(h) retire le minimum en O(log n). Pour des tâches comme l’algorithme de Dijkstra et les problèmes des k plus grands éléments, heapq remplace la file simple.
import heapq
pq = []
heapq.heappush(pq, 5)
heapq.heappush(pq, 1)
heapq.heappush(pq, 3)
heapq.heappush(pq, 2)
print('Min:', heapq.heappop(pq)) # 1
print('Min:', heapq.heappop(pq)) # 2
print('Min:', heapq.heappop(pq)) # 3
# Tasks with priorities
tasks = [(2, 'send email'), (1, 'fix bug'), (3, 'write docs')]
heapq.heapify(tasks)
while tasks:
priority, task = heapq.heappop(tasks)
print(f'Priority {priority}: {task}')Motif de fond d’écran : file pour l’échelle de mots
LeetCode 127 « Échelle de mots » : trouvez le nombre minimal de remplacements d’un seul caractère nécessaires pour transformer un mot en un autre, en utilisant uniquement des mots du dictionnaire. Modélisez le problème comme un graphe dont les arêtes relient les mots qui diffèrent d’un caractère. Un parcours BFS de ce graphe trouve le plus court chemin (le nombre minimal d’étapes) en O(n * L²), où n est la taille du dictionnaire et L la longueur des mots.
from collections import deque
def ladderLength(beginWord, endWord, wordList):
word_set = set(wordList)
if endWord not in word_set:
return 0
queue = deque([(beginWord, 1)])
visited = {beginWord}
while queue:
word, steps = queue.popleft()
for i in range(len(word)):
for ch in 'abcdefghijklmnopqrstuvwxyz':
new_word = word[:i] + ch + word[i+1:]
if new_word == endWord:
return steps + 1
if new_word in word_set and new_word not in visited:
visited.add(new_word)
queue.append((new_word, steps + 1))
return 0
print(ladderLength('hit', 'cog', ['hot','dot','dog','lot','log','cog'])) # 5File à double extrémité
collections.deque est une file à double extrémité : vous pouvez ajouter et retirer efficacement des éléments à ses deux extrémités. Méthodes : appendleft et popleft pour l’avant ; append et pop pour l’arrière. Cela permet à une file à double extrémité de servir à la fois de file FIFO (ajout à droite + popleft) et de pile LIFO (append + pop). Le maximum d’une fenêtre glissante utilise les deux extrémités : retirez les indices anciens à gauche et les valeurs plus petites à droite.
from collections import deque
dq = deque([3, 4, 5])
dq.appendleft(2) # add to front: [2,3,4,5]
dq.appendleft(1) # add to front: [1,2,3,4,5]
dq.append(6) # add to rear: [1,2,3,4,5,6]
print(dq.popleft()) # 1 (from front)
print(dq.pop()) # 6 (from rear)
print(list(dq)) # [2, 3, 4, 5]Résumé : file, file à double extrémité et tas
Choisissez l’outil adapté au problème. Utilisez une file simple (file à double extrémité) pour le traitement FIFO et le parcours BFS. Utilisez une file à double extrémité monotone lorsque vous avez besoin du maximum ou du minimum d’une fenêtre glissante : elle maintient un invariant d’ordre en retirant les éléments dominés. Utilisez une file de priorité (heapq) lorsque vous avez besoin du minimum ou du maximum global, quel que soit l’ordre, comme dans l’algorithme de Dijkstra ou les problèmes des k plus grands éléments. Savoir quel outil choisir et pourquoi est une compétence clé évaluée par les recruteurs.
Vérification rapide
Vérifiez votre compréhension des concepts de structures de données et d’algorithmes — préparation aux entretiens de programmation présentés dans cette leçon.
Récapitulatif de la leçon
Dans cette leçon, vous avez appris que : collections.deque fournit l’ajout et le retrait d’éléments en O(1), ce qui en fait l’implémentation correcte d’une file en Python ; BFS utilise une file pour traiter les nœuds niveau par niveau et trouver les plus courts chemins dans les graphes non pondérés ; et une file à double extrémité monotone décroissante résout le problème du maximum d’une fenêtre glissante en O(n) en retirant les indices dominés. Nous allons maintenant étudier en profondeur le motif de la pile monotone.
Questions Fréquemment Posées
La leçon « Implémentation d’une file et d’une deque » est-elle gratuite ?
Oui — le texte complet de « Implémentation d’une file et d’une 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 DSA Interview Prep, passe à CoddyKit PRO. Le cours DSA Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Implémentation d’une file et d’une deque » ?
Construisez une file avec deque de Python, implémentez une file circulaire et résolvez le maximum d’une fenêtre glissante avec une deque monotone. Tu pratiques DSA Interview Prep 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 DSA Interview Prep ?
Aucune expérience préalable n'est requise. DSA Interview Prep 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 2 sur 4.
Combien de temps prend la leçon « Implémentation d’une file et d’une 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 DSA Interview Prep ?
Oui. Chaque leçon DSA Interview Prep 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
- Implémentation et applications d’une pile
- Implémentation d’une file et d’une deque
- Schéma de la pile monotone
- Simulation réciproque d’une pile et d’une file