Simulation réciproque d’une pile et d’une file
Implémentez une file à l’aide de deux piles et une pile à l’aide de deux files, en expliquant le coût amorti de chaque approche.
Simulation réciproque d’une pile et d’une file est une leçon DSA Interview Prep gratuite sur CoddyKit. Ceci est la leçon 4 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.
Pourquoi simuler l’une avec l’autre
Implémenter une file à l’aide de deux piles et une pile à l’aide de deux files sont des questions classiques d’entretien de conception. Elles testent votre compréhension des invariants des deux structures de données et votre capacité à maintenir la garantie d’une structure en utilisant les primitives d’une autre. Les recruteurs s’en servent également pour introduire la discussion sur la complexité amortie.
L’idée clé est la suivante : les piles sont LIFO et les files sont FIFO. Pour passer de l’une à l’autre, vous devez inverser l’ordre ; or, inverser une pile dans une autre pile produit l’ordre d’insertion original, qui est FIFO.
File avec deux piles (approche paresseuse)
L’approche paresseuse consiste à utiliser une pile inbox pour les ajouts et une pile outbox pour les retraits. Lorsqu’un retrait de la file est demandé, si outbox est vide, transférez-y tous les éléments de inbox : cette inversion rétablit l’ordre FIFO. Si outbox n’est pas vide, retirez directement l’élément qui s’y trouve. Les transferts sont effectués à la demande, ce qui répartit le coût O(n) d’un transfert sur de nombreuses opérations.
class MyQueue:
def __init__(self):
self.inbox = []
self.outbox = []
def push(self, x):
self.inbox.append(x)
def _transfer(self):
if not self.outbox:
while self.inbox:
self.outbox.append(self.inbox.pop())
def pop(self):
self._transfer()
return self.outbox.pop()
def peek(self):
self._transfer()
return self.outbox[-1]
def empty(self):
return not self.inbox and not self.outbox
q = MyQueue()
q.push(1); q.push(2); q.push(3)
print(q.peek()) # 1
print(q.pop()) # 1
print(q.pop()) # 2
q.push(4)
print(q.pop()) # 3Analyse amortie en O(1) pour une file construite avec des piles
Chaque élément est transféré de inbox vers outbox au plus une fois. Lorsque le retrait depuis outbox coûte O(1) et que les transferts n’ont lieu que lorsque outbox est vide, le travail total pour n ajouts et n retraits est d’au plus 2n opérations sur les piles, soit O(n) au total et O(1) amorti par opération. Cela signifie que certaines opérations peuvent coûter O(n) dans le pire des cas, mais que la moyenne est O(1).
# Trace transfer costs for 10 push/pop interleaved
class TrackedQueue:
def __init__(self):
self.inbox = []; self.outbox = []; self.transfers = 0
def push(self, x): self.inbox.append(x)
def pop(self):
if not self.outbox:
while self.inbox:
self.outbox.append(self.inbox.pop())
self.transfers += 1
return self.outbox.pop()
q = TrackedQueue()
for i in range(5):
q.push(i)
for _ in range(5):
q.pop()
q.push(10); q.push(20)
q.pop()
print('Total transfer operations:', q.transfers) # at most nPile avec deux files (retrait paresseux)
Implémenter une pile avec deux files est moins naturel, car les files sont FIFO. L’approche du retrait paresseux consiste à conserver une file principale et une file temporaire. Lors de push, ajoutez l’élément à la file principale (O(1)). Lors de pop ou de peek, retirez tous les éléments sauf le dernier pour les placer dans la file temporaire, enregistrez le dernier élément, puis échangez les files. Cette opération coûte O(n) par retrait, mais O(1) par ajout.
from collections import deque
class MyStack:
def __init__(self):
self.main = deque()
self.temp = deque()
def push(self, x):
self.main.append(x) # O(1)
def pop(self):
# Move all but last element to temp
while len(self.main) > 1:
self.temp.append(self.main.popleft())
val = self.main.popleft() # the 'top'
self.main, self.temp = self.temp, self.main # swap
return val
def top(self):
while len(self.main) > 1:
self.temp.append(self.main.popleft())
val = self.main[0]
self.temp.append(self.main.popleft())
self.main, self.temp = self.temp, self.main
return val
def empty(self):
return len(self.main) == 0
s = MyStack()
s.push(1); s.push(2); s.push(3)
print(s.top()) # 3
print(s.pop()) # 3
print(s.pop()) # 2Pile avec une file (rotation lors de push)
Voici une implémentation élégante avec une seule file : lors de push, ajoutez le nouvel élément, puis faites pivoter la file afin de placer ce nouvel élément à l’avant. Faire pivoter la file consiste à retirer puis à réajouter tous les éléments qui s’y trouvaient avant l’ajout. pop et peek coûtent alors O(1) : il suffit de retirer ou de consulter l’élément à l’avant. L’opération push coûte O(n), ce qui constitue le compromis inverse de la version avec deux files.
from collections import deque
class MyStackOneQueue:
def __init__(self):
self.q = deque()
def push(self, x):
self.q.append(x)
# Rotate: move all preceding elements behind x
for _ in range(len(self.q) - 1):
self.q.append(self.q.popleft())
def pop(self):
return self.q.popleft()
def top(self):
return self.q[0]
def empty(self):
return len(self.q) == 0
s = MyStackOneQueue()
s.push(1); s.push(2); s.push(3)
print(s.top()) # 3
print(s.pop()) # 3
print(s.top()) # 2Résumé des compromis : quelle variante choisir
Pour une file construite avec deux piles : push O(1), pop/peek O(1) amorti ; privilégiez cette solution lorsque les opérations pop sont fréquentes. Pour une pile construite avec deux files : push O(1), pop O(n) ; privilégiez-la lorsque les opérations push sont beaucoup plus fréquentes que les opérations pop. Pour une pile construite avec une file : push O(n), pop O(1) ; privilégiez-la lorsque les opérations pop dominent. Énoncez explicitement ces compromis en entretien afin de montrer que vous réfléchissez au-delà du simple fait que « ça fonctionne ».
print('Queue from 2 stacks: push O(1), pop O(1) amortised')
print('Stack from 2 queues: push O(1), pop O(n)')
print('Stack from 1 queue: push O(n), pop O(1)')Pourquoi l’inversion rétablit-elle FIFO
Lorsque les éléments 1, 2 et 3 sont empilés dans une première pile, ils se trouvent dans l’ordre 1, 2, 3 du bas vers le haut. Dépiler tous ces éléments dans une seconde pile inverse l’ordre : la seconde pile contient 3 au fond et 1 au sommet. Dépiler cette seconde pile donne 1, puis 2, puis 3, exactement dans l’ordre d’insertion FIFO. C’est pourquoi deux inversions exactement (deux piles) rétablissent FIFO, tandis qu’une seule pile produirait LIFO.
# Demonstrate double-reversal = FIFO
inbox = [1, 2, 3] # pushed in this order
outbox = []
while inbox:
outbox.append(inbox.pop())
print('outbox (one reversal):', outbox) # [3, 2, 1] top-to-bottom
# Pop from outbox gives FIFO
result = []
while outbox:
result.append(outbox.pop())
print('dequeued:', result) # [1, 2, 3] — FIFO!LeetCode 232 : implémenter une file avec des piles
LeetCode 232 est le problème direct de la « file construite avec deux piles ». La solution attendue est le transfert paresseux vers la pile de sortie. En entretien, indiquez que chaque élément passe de la pile d’entrée à la pile de sortie au plus une fois, ce qui rend toutes les opérations amorties en O(1). Précisez que les appels individuels à pop peuvent coûter O(n) dans le pire des cas, lorsque la pile de sortie est vide, mais que la moyenne sur n opérations est O(1).
class MyQueue:
def __init__(self):
self.inbox = []
self.outbox = []
def push(self, x):
self.inbox.append(x)
def pop(self):
self.peek() # ensure outbox is populated
return self.outbox.pop()
def peek(self):
if not self.outbox:
while self.inbox: # transfer lazily
self.outbox.append(self.inbox.pop())
return self.outbox[-1]
def empty(self):
return not self.inbox and not self.outbox
# Simulation
q = MyQueue()
q.push(1); q.push(2)
print(q.peek()) # 1
print(q.pop()) # 1
print(q.empty()) # FalseLeetCode 225 : implémenter une pile avec des files
LeetCode 225 est le problème de la « pile construite avec des files ». La solution la plus claire est celle qui utilise une seule file avec rotation lors de push. Après avoir ajouté l’élément x, faites pivoter la file en déplaçant derrière x tous les éléments qui s’y trouvaient déjà. Cette opération coûte O(n) par push, mais rend top et pop disponibles en O(1). Présentez ce compromis et vérifiez qu’il respecte les contraintes, par exemple une charge de travail avec peu de push ou beaucoup de pop.
from collections import deque
class MyStack:
def __init__(self):
self.q = deque()
def push(self, x): # O(n)
self.q.append(x)
for _ in range(len(self.q) - 1):
self.q.append(self.q.popleft())
def pop(self): # O(1)
return self.q.popleft()
def top(self): # O(1)
return self.q[0]
def empty(self):
return len(self.q) == 0
s = MyStack()
s.push(1); s.push(2); s.push(3)
print(s.top()) # 3
print(s.pop()) # 3
print(s.top()) # 2
print(s.empty()) # FalseÉtendre à trois piles dans un tableau
Un problème de conception connexe consiste à implémenter trois piles à l’aide d’un seul tableau. Une approche divise le tableau en trois sections fixes de taille égale. Une approche plus flexible utilise un stockage entrelacé avec des pointeurs, chaque pile grandissant dans sa propre région, avec une copie lorsque les limites se rencontrent. Cela évalue la gestion dynamique des tableaux et constitue une question posée lors d’entretiens de haut niveau. L’approche par sections fixes est plus simple, mais elle gaspille de l’espace si les piles grandissent de manière inégale.
class ThreeStacks:
def __init__(self, size):
self.data = [0] * (3 * size)
self.tops = [-1, -1, -1] # relative top of each stack
self.size = size
def push(self, stack_num, val):
self.tops[stack_num] += 1
if self.tops[stack_num] >= self.size:
raise OverflowError('stack full')
self.data[stack_num * self.size + self.tops[stack_num]] = val
def pop(self, stack_num):
if self.tops[stack_num] < 0:
raise IndexError('stack empty')
val = self.data[stack_num * self.size + self.tops[stack_num]]
self.tops[stack_num] -= 1
return val
ts = ThreeStacks(5)
ts.push(0, 10); ts.push(1, 20); ts.push(2, 30)
print(ts.pop(0), ts.pop(1), ts.pop(2)) # 10 20 30Points essentiels : schémas de simulation
Les problèmes de simulation réciproque enseignent un principe plus général : toute structure de données peut être construite à partir d’une autre, à condition de disposer de suffisamment de mémoire tampon intermédiaire et de possibilités d’inversion. Le coût de la simulation dépend des opérations que vous optimisez — vous pouvez toujours rendre push O(1) ou pop O(1), mais rendre les deux opérations O(1) nécessite une analyse amortie ou plusieurs structures auxiliaires.
Lors d’un entretien, demandez toujours : « Quelles opérations sont les plus fréquentes ? » Cela guide le choix de la variante d’implémentation et témoigne d’une réflexion de haut niveau sur les exigences opérationnelles.
Vérification rapide
Vérifiez 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 : une file construite à partir de deux piles atteint un coût amorti O(1) pour pop en transférant paresseusement les éléments de la boîte d’entrée vers la boîte de sortie, une pile construite à partir d’une seule file atteint un coût O(1) pour pop en faisant pivoter la file à chaque push (push en O(n)), et le choix de l’opération à rendre O(1) dépend du schéma d’utilisation. Ensuite, nous explorerons les mécanismes internes des tables de hachage et la gestion des collisions.
Questions Fréquemment Posées
La leçon « Simulation réciproque d’une pile et d’une file » est-elle gratuite ?
Oui — le texte complet de « Simulation réciproque d’une pile et d’une file » 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 « Simulation réciproque d’une pile et d’une file » ?
Implémentez une file à l’aide de deux piles et une pile à l’aide de deux files, en expliquant le coût amorti de chaque approche. 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 4 sur 4.
Combien de temps prend la leçon « Simulation réciproque d’une pile et d’une file » ?
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