Abstract Data Types — stack, queue, linked list · Types de Données Abstraits — pile, file, liste chaînée
| English | Français |
|---|---|
| queue/kjuː/ | file d'attente |
| push/pʊʃ/ | repousser |
| abstract data type/ˈæbstrækt ˈdeɪtə taɪp/ | type de donnée abstrait (TDA) |
| stack/stæk/ | pile |
| linked list/lɪŋkt lɪst/ | liste chaînée |
| LIFO/ˈlaɪfəʊ/ | Dernier entré, premier sorti |
| pop/pɒp/ | populer |
| pointer/ˈpɔɪntə/ | pointeur |
| FIFO/ˈfaɪfəʊ/ | FIFO |
| enqueue/enˈkjuː/ | enfiler |
| dequeue/diːˈkjuː/ | défiler |
| node/nəʊd/ | nœud |
| traverse/trəˈvɜːs/ | parcours |
The Back button and the printer queue
- Every page you visit is pushed onto a pile; the Back button takes the top one off. The page you left most recently is the first you return to.
- Down the corridor, a printer works through jobs in the order they arrived. The document sent first comes out first, however small the ones behind it.
- Two structures, opposite rules, and you use both before break. Neither says how it is stored; each says only what its operations do.
- That is an abstract data type 抽象数据类型. This lesson is the three the syllabus names, the operations on each, and how to justify one for a situation.
Le bouton Retour et la file d'impression
- Chaque page visitée est poussée sur une pile ; le bouton Retour retire le dessus. La page laissée le plus récemment est la première à la quelle on revient.
- Dans le couloir, une imprimante traite les tâches dans l'ordre d'arrivée. Le document envoyé en premier sort en premier, peu importe la taille de ceux derrière lui.
- Deux structures, règles opposées, et vous utilisez les deux avant la pause. Aucune ne dit comment elles sont stockées ; chacune dit seulement ce que font leurs opérations.
- C'est un type de données abstrait 抽象数据类型. Cette leçon porte sur les trois que le programme nomme, les opérations sur chacun, et comment justifier l'un pour une situation donnée.
What an ADT is
- An abstract data type (ADT) is a collection of data together with a set of operations on that data. That one sentence is the one-mark definition.
- It is defined by what the operations do, not by how the data is stored. The implementation is hidden, so it can change without affecting the code that uses it.
- A stack, a queue, a linked list, a binary tree and an array are all ADTs.
Ce qu'est un TDA
- Un type de données abstrait (TDA) est un ensemble de données accompagné d'un ensemble d'opérations sur ces données. Cette phrase unique est la définition à un point.
- Il est défini par ce que font les opérations, pas par comment les données sont stockées. L'implémentation est cachée, donc elle peut changer sans affecter le code qui l'utilise.
- Une pile, une file, une liste chaînée, un arbre binaire et un tableau sont tous des TDAs.
An Abstract Data Type (ADT) is defined by: · Un Type de Données Abstrait (ADT) est défini par :
An ADT specifies the operations (the interface); the implementation is hidden and can change freely. · Un TAD spécifie les opérations (l'interface) ; l'implémentation est cachée et peut changer librement.
The stack
- A stack 栈 is a list in which items are added to and removed from the same end, the top, so the last item added is the first removed: LIFO 后进先出.
- Operations: push 入栈 adds to the top, pop 出栈 removes from the top, peek looks at the top, and tests for empty and full.
- Uses: undo history, the Back button, the return addresses of function calls, checking brackets, backtracking.
Everything happens at the top
La pile
- Une pile 栈 est une liste où les éléments sont ajoutés et retirés à la même extrémité, le sommet, donc le dernier élément ajouté est le premier retiré : LIFO 后进先出.
- Opérations : push 入栈 ajoute au sommet, pop 出栈 retire du sommet, peek regarde le sommet, et teste pour vide et plein.
- Usages : historique d'annulation, bouton Retour, adresses de retour des appels de fonction, vérification des parenthèses, backtrack.
Tout se passe au sommet
A stack works in which order? · Dans quel ordre fonctionne une pile ?
A stack is LIFO: the most recently pushed item is the first to be popped. · Une pile est LIFO : l'élément le plus récemment empilé est le premier à être dépiler.
Worked example: trace the stack
- A stack holds, from the bottom,
'P' 'N' 'Z' 'X' 'Y' 'W'; the top pointer is at'W'. The operationsPOP,POP,PUSH 'A',PUSH 'B',POPare performed. What does the stack hold, and where is the pointer? - The two pops remove
'W'then'Y'. The pushes put'A'then'B'in their places. The last pop removes'B'. - The stack holds
'P' 'N' 'Z' 'X' 'A', with the pointer at'A'. The item on the stack longest is the bottom one,'P'; five more pops are possible, and a sixth would be an error, which is why pop tests for empty first.
Exemple résolu : tracer la pile
- Une pile contient, du bas vers le haut,
'P' 'N' 'Z' 'X' 'Y' 'W'; le pointeur supérieur est à'W'. Les opérationsPOP,POP,PUSH 'A',PUSH 'B',POPsont effectuées. Que contient la pile, et où se trouve le pointeur ? - Les deux pops retirent
'W'puis'Y'. Les pushes placent'A'puis'B'à leur place. Le dernier pop retire'B'. - La pile contient
'P' 'N' 'Z' 'X' 'A', avec le pointeur à'A'. L'item resté le plus longtemps sur la pile est le fond,'P'; cinq autres pops sont possibles, et une sixième serait une erreur, c'est pourquoi pop teste pour vide d'abord.
A stack holds P N Z X Y W (top is W). After POP, POP, PUSH 'A', PUSH 'B', POP, which item is on top? · Une pile contient P N Z X Y W (le sommet est W). Après POP, POP, PUSH 'A', PUSH 'B', POP, quel élément est au sommet ?
W and Y are popped, A then B pushed, B popped. The top is A, above X. · W et Y sont déspilés, A puis B sont empilés, B est déspilé. Le sommet est A, au-dessus de X.
The queue
- A queue 队列 is a list in which items are added at the rear and removed from the front, so the first item added is the first removed: FIFO 先进先出.
- Operations: enqueue 入队 adds at the rear, dequeue 出队 removes from the front, and tests for empty and full.
- Uses: print spooling, keyboard buffers, scheduling, customers in a shop, breadth-first search.
Join at the back, leave from the front
La file
- Une file 队列 est une liste où les éléments sont ajoutés à l'arrière et retirés de l'avant, donc le premier élément ajouté est le premier retiré : FIFO 先进先出.
- Opérations : enqueue 入队 ajoute à l'arrière, dequeue 出队 retire de l'avant, et teste pour vide et plein.
- Usages : spooling d'impression, tampons clavier, ordonnancement, clients dans un magasin, recherche en largeur.
Entrer par derrière, sortir par devant
Stacks, queues & linked lists · Piles, files & listes chaînées
LIFO vs FIFO
A stack · pile is last-in-first-out; push and pop happen at the same end (the top). · Une pile est last-in-first-out (dernier entré, premier sorti) ; push et pop se font au même bout (le sommet).
A queue is first-in-first-out: items are removed from the ______ and added at the rear. · Une file est premier-entré-premier-sorti : les éléments sont retirés du ______ et ajoutés à l'arrière.
FIFO: dequeue from the front, enqueue at the rear — like a line of people. · FIFO : défiler depuis le devant, enfiler à l'arrière — comme une file d'attente.
Worked example: describe adding to and removing from a queue
- Adding: check that the queue is not full; store the item at the position given by the rear pointer; move the rear pointer on (and add one to the count).
- Removing: check that the queue is not empty; read the item at the front pointer; move the front pointer on (and subtract one from the count).
- State the convention you use: if the rear pointer marks the next free space, store first and then move; if it marks the last item, move first and then store. Either scores, if you are consistent.
Exemple résolu : décrire l'ajout et le retrait d'une file
- Ajouter : vérifier que la file n'est pas pleine ; stocker l'élément à la position donnée par le pointeur arrière ; déplacer le pointeur arrière (et ajouter un au compteur).
- Retirer : vérifier que la file n'est pas vide ; lire l'élément au pointeur avant ; déplacer le pointeur avant (et soustraire un au compteur).
- Énoncer la convention utilisée : si le pointeur arrière marque la prochaine case libre, stocker d'abord puis déplacer ; s'il marque le dernier élément, déplacer d'abord puis stocker. Les deux valent des points, tant que vous êtes cohérent.
Put the steps of adding an item to a queue in order (rear pointer marks the next free space). · Mettez les étapes d'ajout d'un élément dans une file dans l'ordre (le pointeur arrière marque la prochaine case libre).
The check comes first; then store, then move, under this convention. Say which convention you use. · La vérification vient en premier ; puis stocker, puis déplacer, selon cette convention. Dites quelle convention vous utilisez.
The linked list
- A linked list 链表 is a list in which each node 节点 holds a data item and a pointer 指针 to the next node, with a start pointer to the first node. The last node's pointer is a sentinel such as
NULL. - Operations: insert, delete, search, and traverse 遍历, following the pointers from the head to visit every node in order.
- Advantage over an array: inserting or deleting is cheap, just rewire pointers, and the list grows as needed. Disadvantage: no random access; reaching the tenth node means following nine pointers.
A value and an arrow, repeated
La liste chaînée
- Une liste chaînée 链表 est une liste où chaque nœud 节点 contient un élément de données et un pointeur 指针 vers le nœud suivant, avec un pointeur de départ vers le premier nœud. Le pointeur du dernier nœud est un sentinelle tel que
NULL. - Opérations : insertion, suppression, recherche, et traversée 遍历, suivant les pointeurs de la tête pour visiter tous les nœuds dans l'ordre.
- Avantage sur un tableau : insérer ou supprimer est peu coûteux, il suffit de rebrancher les pointeurs, et la liste grandit selon les besoins. Inconvénient : pas d'accès aléatoire ; atteindre le dixième nœud signifie suivre neuf pointeurs.
Une valeur et une flèche, répété
A linked list: nodes joined by pointers · Une liste chaînée : des nœuds joints par des pointeurs
Each node stores a value and a pointer to the next node. Inserting or deleting just re-links pointers — no items shift along, unlike an array. · Chaque nœud stocke une valeur et un pointeur vers le nœud suivant. Insérer ou supprimer ne fait que relier les pointeurs — aucun élément ne se décale, contrairement à un tableau.
Each node of a linked list holds: · Chaque nœud d'une liste chaînée contient :
A node stores its value plus a pointer (reference) to the next node; the head marks the start, NULL the end. · Un nœud stocke sa valeur ainsi qu'un pointeur (référence) vers le nœud suivant ; la tête marque le début, NULL la fin.
A linked list makes inserting/deleting cheap (just rewire pointers) but random access slow (you must follow pointers from the head). · Une liste chaînée permet des insertions/suppressions peu coûteuses (simple rebranchement des pointeurs) mais un accès aléatoire lent (il faut suivre les pointeurs depuis la tête).
That is the array-vs-list trade-off: arrays give O(1) index access; lists give cheap insert/delete. · C'est le compromis tableau-vs-liste : les tableaux offrent un accès O(1) par indice ; les listes permettent des insertions/suppressions peu coûteuses.
Worked example: add a node in order
- Describe how a new value is inserted into a linked list that is kept in ascending order. [4]
- Traverse the list from the head, following the pointers, until the node before the position is found: the last node whose value is smaller than the new one.
- Take a free node and store the new value in it. Set the new node's pointer to the address the previous node currently points to.
- Then set the previous node's pointer to the new node. If the new value belongs at the front, it is the head pointer that changes instead.
Exemple résolu : ajouter un nœud dans l'ordre
- Décrire comment une nouvelle valeur est insérée dans une liste chaînée maintenue par ordre croissant. [4]
- Parcourir la liste depuis la tête, en suivant les pointeurs, jusqu'à ce que le nœud avant la position soit trouvé : le dernier nœud dont la valeur est inférieure à la nouvelle.
- Prendre un nœud libre et stocker la nouvelle valeur dedans. Définir le pointeur du nouveau nœud sur l'adresse à laquelle le nœud précédent pointe actuellement.
- Puis définir le pointeur du nœud précédent sur le nouveau nœud. Si la nouvelle valeur doit être placée au début, c'est le pointeur de tête qui change alors.
Put the steps of inserting a value into an ordered linked list in order. · Mettez les étapes d'insertion d'une valeur dans une liste chaînée ordonnée dans l'ordre.
Find, fill, point the new node forward, then rewire the previous node. Reversing the last two loses the rest of the list. · Trouver, remplir, pointer le nouveau nœud vers l'avant, puis rebrancher le nœud précédent. Inverser les deux dernières étapes fait perdre le reste de la liste.
Justifying the choice
- Items must be handled in the order they arrived, print jobs, key presses, customers: a queue, because it is first in, first out.
- The most recent item must be handled first, undo, going back, nested calls: a stack, because it is last in, first out.
- Items are frequently inserted or deleted in the middle of an ordered collection, and the size is unknown: a linked list, because only pointers change and nothing is shifted.
- Name the structure, name its rule, tie the rule to the situation.
Justifier le choix
- Les éléments doivent être traités dans l'ordre d'arrivée, impression, frappe au clavier, clients : une file, car elle est premier entré, premier sorti.
- Le dernier élément doit être traité en premier, annuler, revenir en arrière, appels imbriqués : une pile, car elle est dernier entré, premier sorti.
- Les éléments sont fréquemment insérés ou supprimés au milieu d'une collection ordonnée, et sa taille est inconnue : une liste chaînée, car seuls les pointeurs changent et rien n'est déplacé.
- Nommer la structure, nommer sa règle, relier la règle à la situation.
Match each ADT to its rule and a typical use. · Associez chaque TAD à sa règle et à une utilisation typique.
Stack = last-in-first-out; queue = first-in-first-out; a linked list chains nodes with pointers. · Pile = dernier-entré-premier-sorti ; file = premier-entré-premier-sorti ; une liste chaînée enchaîne des nœuds avec des pointeurs.
Print jobs must be printed in the order they were sent. Which ADT, and why? · Les impressions doivent s'exécuter dans l'ordre d'arrivée. Quel TAD et pourquoi ?
Order of arrival is the FIFO rule. A stack would print the most recent job first. · L'ordre d'arrivée suit la règle FIFO. Une pile imprimerait la tâche la plus récente en premier.
ADT versus implementation
- The ADT is the behaviour: push and pop, enqueue and dequeue, insert and traverse.
- The implementation is the storage: in this course, an array plus a few pointer variables (next lesson).
- A question about the ADT wants operations and rules; a question about implementation wants arrays, pointers and the checks.
ADT versus implémentation
- L'ADT est le comportement : push et pop, enqueue et dequeue, insert et traverse.
- L'implémentation est le stockage : dans ce cours, un tableau plus quelques variables pointeur (prochaine leçon).
- Une question sur l'ADT demande des opérations et des règles ; une question sur l'implémentation demande des tableaux, des pointeurs et les vérifications.
Marks that slip away
- Push and enqueue test for full first; pop and dequeue test for empty first. Write the check into the description.
- Inserting into a linked list: set the new node's pointer before changing the previous node's, or the rest of the list is lost.
- A stack changes at one end, a queue at both. "Remove from the top of the queue" is a stack answer.
- Expand the abbreviations once: LIFO, last in first out; FIFO, first in first out.
Pièges qui font perdre des points
- Push et enqueue testent pour plein d'abord ; pop et dequeue testent pour vide d'abord. Écrire la vérification dans la description.
- Insérer dans une liste chaînée : définir le pointeur du nœud nouveau avant de changer celui du nœud précédent, sinon le reste de la liste sera perdu.
- Une pile change à une extrémité, une file aux deux. « Retirer du haut de la file » est une réponse de pile.
- Développer les abréviations une fois : LIFO, last in first out ; FIFO, first in first out.
You've got it
- an ADT is a collection of data together with a set of operations on it; behaviour, not storage
- stack: add and remove at the top, LIFO, push and pop · queue: add at the rear, remove at the front, FIFO, enqueue and dequeue
- linked list: nodes of value + pointer from a head pointer; cheap insert and delete, slow random access; traverse by following pointers
- justify by rule: order of arrival → queue; most recent first → stack; frequent insertion in the middle → linked list
Vous avez compris
- un ADT est un ensemble de données avec un ensemble d'opérations dessus ; comportement, pas stockage
- pile : ajouter et retirer au sommet, LIFO, push et pop · file : ajouter à l'arrière, retirer à l'avant, FIFO, enqueue et dequeue
- liste chaînée : nœuds de valeur + pointeur depuis un pointeur de tête ; insertion et suppression peu coûteuses, accès aléatoire lent ; parcourir en suivant les pointeurs
- justifier par règle : ordre d'arrivée → file ; plus récent en premier → pile ; insertion fréquente au milieu → liste chaînée