Implémentation et applications d’une pile
Implémentez une pile avec push/pop/peek, puis résolvez valid-parentheses, min-stack et l’évaluation de la notation polonaise inversée.
Implémentation et applications d’une pile est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 1 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 Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.
La structure de données Stack
Une pile est une structure de données dernier entré, premier sorti (LIFO). Le dernier élément empilé est le premier élément dépilé. Imaginez une pile d’assiettes : vous ne pouvez ajouter ou retirer des éléments que par le sommet. Les opérations principales sont push (ajouter au sommet), pop (retirer du sommet) et peek (lire le sommet sans le retirer). Ces trois opérations s’effectuent en O(1) dans une pile correctement implémentée.
En Python, une liste constitue une pile idéale : append correspond à push, pop() à pop et [-1] à peek.
stack = []
# Push
stack.append(10)
stack.append(20)
stack.append(30)
print('After pushes:', stack) # [10, 20, 30]
# Peek
print('Top:', stack[-1]) # 30
# Pop
print('Popped:', stack.pop()) # 30
print('After pop:', stack) # [10, 20]Classe Stack avec push, pop, peek et isEmpty
Encapsuler la liste dans une classe offre une interface plus claire et empêche l’utilisation accidentelle d’opérations qui ne font pas partie d’une pile, comme insert ou l’indexation à des positions autres que le sommet. C’est l’implémentation que les examinateurs attendent lorsqu’ils vous demandent d’« implémenter une pile à partir de zéro ».
class Stack:
def __init__(self):
self._data = []
def push(self, val):
self._data.append(val)
def pop(self):
if self.is_empty():
raise IndexError('pop from empty stack')
return self._data.pop()
def peek(self):
if self.is_empty():
raise IndexError('peek at empty stack')
return self._data[-1]
def is_empty(self):
return len(self._data) == 0
def __len__(self):
return len(self._data)
s = Stack()
s.push(1); s.push(2); s.push(3)
print(s.peek()) # 3
print(s.pop()) # 3
print(len(s)) # 2Parenthèses valides (LeetCode 20)
LeetCode 20 « Parenthèses valides » : déterminer si une chaîne de crochets est équilibrée. Pour chaque crochet ouvrant, empilez-le. Pour chaque crochet fermant, vérifiez que le sommet de la pile est le crochet ouvrant correspondant ; sinon, ou si la pile est vide, renvoyez faux. Si la pile est vide à la fin, la chaîne est valide. C’est la première application classique d’une pile dans les entretiens de programmation.
def isValid(s):
stack = []
matching = {')': '(', '}': '{', ']': '['}
for ch in s:
if ch in '([{':
stack.append(ch)
else:
if not stack or stack[-1] != matching[ch]:
return False
stack.pop()
return len(stack) == 0
print(isValid('()[]{}')) # True
print(isValid('([)]')) # False
print(isValid('{[]}')) # True
print(isValid(']')) # FalsePile minimale (LeetCode 155)
LeetCode 155 « Pile minimale » : concevoir une pile prenant en charge push, pop, peek et getMin, chacun en O(1). L’astuce consiste à maintenir une seconde pile qui suit le minimum à chaque étape. Lors d’un empilement, empilez également dans la pile des minimums si la nouvelle valeur est <= au minimum actuel (ou si la pile des minimums est vide). Lors d’un dépilement, dépilez aussi la pile des minimums si la valeur retirée est égale au minimum actuel.
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, val):
self.stack.append(val)
if not self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val)
def pop(self):
val = self.stack.pop()
if val == self.min_stack[-1]:
self.min_stack.pop()
return val
def top(self):
return self.stack[-1]
def getMin(self):
return self.min_stack[-1]
ms = MinStack()
ms.push(-2); ms.push(0); ms.push(-3)
print(ms.getMin()) # -3
ms.pop()
print(ms.top()) # 0
print(ms.getMin()) # -2Évaluer la notation polonaise inversée
LeetCode 150 « Évaluer la notation polonaise inversée » (notation postfixée) : empilez les opérandes ; lorsqu’un opérateur apparaît, dépilez deux opérandes, appliquez l’opérateur, puis empilez le résultat. L’ordre est important pour la soustraction et la division : le premier opérande dépilé est celui de droite, et le second est celui de gauche.
def evalRPN(tokens):
stack = []
ops = set(['+', '-', '*', '/'])
for tok in tokens:
if tok not in ops:
stack.append(int(tok))
else:
b = stack.pop() # right operand
a = stack.pop() # left operand
if tok == '+':
stack.append(a + b)
elif tok == '-':
stack.append(a - b)
elif tok == '*':
stack.append(a * b)
else: # division truncated toward zero
stack.append(int(a / b))
return stack[0]
print(evalRPN(['2','1','+','3','*'])) # 9
print(evalRPN(['4','13','5','/','+'])) # 6
print(evalRPN(['10','6','9','3','+','-11','*','/','*','17','+','5','+'])) # 22Décoder une chaîne (LeetCode 394)
LeetCode 394 « Décoder une chaîne » : étant donnée une chaîne encodée comme 3[a2[c]], la développer en accaccacc. Utilisez deux piles : une pour les compteurs de répétition et une pour les chaînes accumulées. Lorsqu’un chiffre apparaît, construisez le nombre complet. À l’apparition de [, empilez la chaîne et le compteur actuels. À l’apparition de ], dépilez-les et répétez le segment actuel. Lorsqu’une lettre apparaît, ajoutez-la à la chaîne actuelle.
def decodeString(s):
count_stack = []
str_stack = []
current_str = ''
current_num = 0
for ch in s:
if ch.isdigit():
current_num = current_num * 10 + int(ch)
elif ch == '[':
count_stack.append(current_num)
str_stack.append(current_str)
current_str = ''
current_num = 0
elif ch == ']':
repeats = count_stack.pop()
current_str = str_stack.pop() + current_str * repeats
else:
current_str += ch
return current_str
print(decodeString('3[a]2[bc]')) # 'aaabcbc'
print(decodeString('3[a2[c]]')) # 'accaccacc'
print(decodeString('2[abc]3[cd]ef')) # 'abcabccdcdcdef'Températures quotidiennes (aperçu de Stack monotone)
LeetCode 739 « Températures quotidiennes » : pour chaque jour, trouver dans combien de jours une température plus élevée apparaîtra. Une méthode par force brute coûte O(n²). Avec une pile, parcourez les températures ; pour chaque jour, dépilez toutes les entrées de la pile (des indices de jours) dont la température est inférieure à celle d’aujourd’hui. La réponse pour chacun de ces jours retirés est (aujourd’hui - jour retiré). Empilez le jour actuel. Les entrées restantes n’ont jamais trouvé de jour plus chaud ; leur réponse est donc 0.
def dailyTemperatures(temps):
result = [0] * len(temps)
stack = [] # stores indices
for i, t in enumerate(temps):
while stack and temps[stack[-1]] < t:
j = stack.pop()
result[j] = i - j
stack.append(i)
return result
print(dailyTemperatures([73,74,75,71,69,72,76,73]))
# [1, 1, 4, 2, 1, 1, 0, 0]Stack pour le parcours DFS
La pile d’appels d’un DFS récursif peut être remplacée par une pile explicite, ce qui rend l’algorithme itératif. Empilez la racine ; tant que la pile n’est pas vide, dépilez un nœud, traitez-le, puis empilez ses enfants (l’enfant droit avant le gauche pour un traitement de gauche à droite). Ce DFS itératif se comporte exactement comme le DFS récursif, mais évite la limite de récursion de Python pour les arbres profonds.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def preorder_iterative(root):
if not root:
return []
result, stack = [], [root]
while stack:
node = stack.pop()
result.append(node.val)
if node.right:
stack.append(node.right) # push right first
if node.left:
stack.append(node.left) # so left is processed first
return result
root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
print(preorder_iterative(root)) # [1, 2, 4, 5, 3]Complexité temporelle et spatiale
Toutes les opérations d’une pile (push, pop, peek, isEmpty) s’effectuent en O(1) amorti. Construire une pile de n éléments coûte O(n). L’espace est de O(n) dans le pire cas, lorsque tous les éléments sont stockés. Pour les problèmes qui utilisent une pile monotone, chaque élément est empilé et dépilé au plus une fois, ce qui donne une complexité temporelle globale de O(n) sur l’ensemble des itérations — et non O(n²), comme pourrait le laisser penser une lecture naïve de la boucle externe.
# Demonstrate O(n) total for monotonic stack
# Each element pushed once, popped at most once => 2n operations total
def count_ops(n):
pushes = pops = 0
stack = []
for i in range(n):
while stack and stack[-1] < i: # simulated decreasing condition
stack.pop()
pops += 1
stack.append(i)
pushes += 1
return pushes, pops
p, pp = count_ops(1000)
print(f'Pushes: {p}, Pops: {pp}, Total ops: {p+pp}') # <= 2000Plus grand rectangle dans un histogramme (aperçu)
LeetCode 84 « Plus grand rectangle dans un histogramme » est le problème classique de pile le plus difficile. Pour chaque barre, le rectangle dont elle peut être l’ancrage s’étend vers la gauche jusqu’à rencontrer une barre plus courte, et vers la droite jusqu’à rencontrer une barre plus courte. Une pile monotone suit les indices des barres par ordre croissant de hauteur. Lorsqu’une barre plus courte apparaît, dépilez une barre et calculez le rectangle correspondant à sa hauteur. La pile fournit les limites gauche et droite en O(1) par dépilement.
def largestRectangleArea(heights):
stack = [] # indices, increasing heights
result = 0
heights = heights + [0] # sentinel forces all pops
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()]
width = i if not stack else i - stack[-1] - 1
result = max(result, height * width)
stack.append(i)
return result
print(largestRectangleArea([2,1,5,6,2,3])) # 10
print(largestRectangleArea([2,4])) # 4Stratégie d’entretien pour les problèmes de Stack
Les problèmes de pile se présentent souvent sous la forme « traiter de l’intérieur vers l’extérieur » ou « trouver l’élément suivant plus grand ou plus petit ». Une pile peut être utile lorsque vous devez retrouver l’élément vu le plus récemment, lorsque vous faites correspondre des paires (crochets, balises) ou lorsque vous cherchez une complexité O(n) pour un problème qui nécessiterait naïvement des boucles imbriquées en O(n²). Les piles monotones transforment notamment la recherche, pour chaque élément, de l’élément plus grand ou plus petit le plus proche, en un problème de O(n) au lieu de O(n²).
Lors d’un entretien, énoncez clairement l’invariant de votre pile : « Je vais maintenir une pile d’indices par hauteur décroissante. »
Vérification rapide
Testez votre compréhension des concepts de Structures de données et 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 : les listes Python implémentent push, pop et peek en O(1), ce qui en fait des piles idéales, les parenthèses valides et la pile minimale sont les deux problèmes classiques de pile en entretien, et les piles monotones résolvent les problèmes de recherche de l’élément suivant le plus grand en O(n), en empilant et dépilant chaque élément au plus une fois. Ensuite, vous construirez des files avec la file à double extrémité de Python et résoudrez le problème du maximum dans une fenêtre glissante.
Questions Fréquemment Posées
La leçon « Implémentation et applications d’une pile » est-elle gratuite ?
Oui — le texte complet de « Implémentation et applications d’une pile » 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 Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Implémentation et applications d’une pile » ?
Implémentez une pile avec push/pop/peek, puis résolvez valid-parentheses, min-stack et l’évaluation de la notation polonaise inversée. Tu pratiques Coding 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 Coding Interview Prep ?
Aucune expérience préalable n'est requise. Coding 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 1 sur 4.
Combien de temps prend la leçon « Implémentation et applications d’une pile » ?
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 Coding Interview Prep ?
Oui. Chaque leçon Coding 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