Stacks and queues (array-backed) · Piles et files (basées sur tableau)
Two ways to hold items
- A stack and a queue both hold a line of items, but they differ in which item comes out next.
- A stack is LIFO: Last In, First Out — like a pile of plates.
- A queue is FIFO: First In, First Out — like a line of people.
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.
A stack is LIFO
- push adds an item on top. pop removes and returns the top item. peek looks at the top without removing it.
- The last item you pushed is the first one you pop.
- We store the items in an array
dataand an indextopthat counts how many are in.
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.
Array-backed stack
- With
topas the count, the top item is atdata[top - 1]. - push: write at
data[top], thentop++. pop:top--, then returndata[top]. - (For these tasks the array is big enough; you do not need to check for "full".)
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".)
A queue is FIFO
- enqueue adds an item at the back. dequeue removes and returns the item at the front.
- The first item you enqueue is the first one you dequeue.
- We keep two indexes:
front(next to leave) andback(next free slot).
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).
Array-backed queue
- enqueue: write at
data[back], thenback++. dequeue: readdata[front], thenfront++, and return it. frontchasesbackas items come and go.- (For these tasks the array is big enough; you do not need to wrap around or check for "empty".)
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".)
Common mistakes
- A stack is last-in-first-out; a queue is first-in-first-out.
- Check the structure is not empty before you pop or dequeue.
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.
Now you try
- The
StackandQueuestructs are given in the starter. Uses->top,q->front, andq->back. - Do not write a
main— the checker provides one.
À 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.
Stacks and queues · Piles et files
A stack is LIFO; a queue is FIFO. Step through the operations. · Une pile est LIFO ; une file est FIFO. Passez en revue les opérations.
The · Le Stack struct (with data and a count top) is given. Complete void push(Stack *s, int v) and · et int pop(Stack *s) so the stack is LIFO. Do not · non write a main. · 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.
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.
The · Le Stack struct is given. Complete int peek(const Stack *s) so it returns the top item without removing it. Assume the stack is not empty. Do not · non write a main. · 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.
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.
The · Le Queue struct (with data, front, and back) is given. Complete void enqueue(Queue *q, int v) and · et int dequeue(Queue *q) so the queue is FIFO. Do not · non write a main. · 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.
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.