Piles et files (basées sur tableau)
Deux façons de stocker des éléments
- Une pile et une file stockent toutes deux une ligne d'éléments, mais elles diffèrent par quel élément sortra en premier.
- Une pile est LIFO : Last In, First Out (Dernier entré, Premier sorti) — comme une pile d'assiettes.
- Une file est FIFO : First In, First Out (Premier entré, Premier sorti) — comme une file d'attente.
Une pile est LIFO
- push ajoute un élément au sommet. pop retire et retourne l'élément supérieur. peek regarde le sommet sans le retirer.
- Le dernier élément que vous avez poussé est le premier que vous tirerez.
- Nous stockons les éléments dans un tableau
dataet un indextopqui compte combien il y en a.
Pile basée sur un tableau
- Avec
topcomme compteur, l'élément supérieur est àdata[top - 1]. - push : écrire à
data[top], puistop++. pop :top--, puis retournerdata[top]. - (Pour ces exercices, le tableau est assez grand ; vous n'avez pas besoin de vérifier s'il est "plein".)
Une file est FIFO
- enqueue ajoute un élément à l'arrière. dequeue retire et retourne l'élément à l'avant.
- Le premier élément que vous mettez en file est le premier que vous tirez de la file.
- Nous gardons deux indexes :
front(prochain à sortir) etback(prochaine case libre).
File basée sur un tableau
- enqueue : écrire à
data[back], puisback++. dequeue : liredata[front], puisfront++, et la retourner. frontrattrapebackà mesure que les éléments entrent et sortent.- (Pour ces exercices, le tableau est assez grand ; vous n'avez pas besoin de faire le tour ou de vérifier s'il est "vide".)
Erreurs courantes
- Une pile est last-in-first-out ; une file est first-in-first-out.
- Vérifiez que la structure n'est pas vide avant de pop ou dequeue.
À vous maintenant
- Les structs
StacketQueuesont donnés dans le modèle de départ. Utilisezs->top,q->frontetq->back. - N'écrivez pas de
main— le vérificateur en fournit une.
Piles et files
Une pile est LIFO ; une file est FIFO. Passez en revue les opérations.
Difficulté 4/5 · 280 pièces + un petit bonus lors de la première réussite aujourd'hui
La structure Stack (avec data et un compteur top) est donnée. Complétez void push(Stack *s, int v) et int pop(Stack *s) pour que la pile soit LIFO. Ne pas écrire de main.
Cliquez sur Exécuter pour voir le résultat ici.
Difficulté 4/5 · 280 pièces + un petit bonus lors de la première réussite aujourd'hui
La structure Stack est donnée. Complétez int peek(const Stack *s) pour qu'il retourne l'élément du sommet sans le retirer. Supposez que la pile n'est pas vide. Ne pas écrire de main.
Cliquez sur Exécuter pour voir le résultat ici.
Difficulté 4/5 · 280 pièces + un petit bonus lors de la première réussite aujourd'hui
La structure Queue (avec data, front, et back) est donnée. Complétez void enqueue(Queue *q, int v) et int dequeue(Queue *q) pour que la file soit FIFO. Ne pas écrire de main.
Cliquez sur Exécuter pour voir le résultat ici.