Implementing ADTs using arrays · Implémenter des TADs à l'aide de tableaux
| English | Français |
|---|---|
| overflow/ˌəʊvəˈfləʊ/ | débordement |
| underflow/ˌʌndəˈfləʊ/ | sous-débordement |
| circular array/ˈsɜːkjʊlə əˈreɪ/ | tableau circulaire |
| free list/friː lɪst/ | liste libre |
There is no such thing as a stack in memory
- Open a computer and look for the stack. You will not find one. Memory is one enormous array of numbered cells, and that is all there is.
- Every stack, every queue, every linked list is that array plus two or three integer variables that remember where things are. Push is "add one to a number and store"; dequeue is "read a cell and add one to a different number".
- The whole of this lesson is bookkeeping: which pointers, which checks, and what happens at the edges.
- The exam asks you to describe the declarations, walk the pointers through a few operations, and say why the checks are there.
Il n'existe pas de pile en mémoire
- Ouvrir un ordinateur et chercher la pile. Vous n'en trouverez pas. La mémoire est un immense tableau de cellules numérotées, et c'est tout.
- Chaque pile, chaque file, chaque liste chaînée est ce tableau plus deux ou trois variables entières qui se souviennent où se trouvent les choses. Push est « ajouter un à un nombre et stocker » ; dequeue est « lire une cellule et ajouter un à un autre nombre ».
- Tout ce cours est de la tenue de registre : quels pointeurs, quelles vérifications, et ce qui arrive aux bords.
- L'examen vous demande de décrire les déclarations, parcourir les pointeurs à travers quelques opérations, et dire pourquoi les vérifications sont là.
A stack in an array
- Hold the items in
Stack[1:MaxSize]with an integerTop, 0 when the stack is empty. - Push(x): if
Top = MaxSizethe stack is full, an overflow 溢出; otherwiseTop ← Top + 1andStack[Top] ← x. - Pop(): if
Top = 0the stack is empty, an underflow 下溢; otherwise returnStack[Top]andTop ← Top − 1.
The array never moves; only Top does
Une pile dans un tableau
- Garder les éléments dans
Stack[1:MaxSize]avec un entierTop, 0 quand la pile est vide. - Push(x) : si
Top = MaxSizela pile est pleine, une surcharge 溢出 ; sinonTop ← Top + 1etStack[Top] ← x. - Pop() : si
Top = 0la pile est vide, une sous-charge 下溢 ; sinon retournerStack[Top]etTop ← Top − 1.
Le tableau ne bouge jamais ; seul Top fait
Pushing an item onto a stack that is already full causes a stack ______. · Empiler un élément sur une pile déjà pleine provoque un dépassement de pile ______.
Overflow = push when Top = MaxSize; popping from an empty stack (Top = 0) is underflow. · Dépassement = empiler lorsque Top = MaxSize ; dépiler depuis une pile vide (Top = 0) est une sous-dépassement.
Match each array-stack condition to what it means. · Associez chaque condition de pile à base de tableau à sa signification.
Top counts the items: 0 = empty, MaxSize = full; the two error cases are underflow and overflow. · Top compte les éléments : 0 = vide, MaxSize = plein ; les deux cas d'erreur sont le sous-dépassement et le dépassement.
Worked example: declare and initialise the stack
- Describe the declarations and initialisation needed to implement a stack of up to 50 integers using an array. [5]
- An array of 50 elements of type
INTEGER,DECLARE Stack : ARRAY[1:50] OF INTEGER, to hold the items. - A constant or variable
MaxSizeset to 50, so that push can test for full. - An
INTEGERtop-of-stack pointer,Top, initialised to 0 to show the stack is empty; pop tests it for underflow, and push compares it withMaxSizefor overflow.
Exemple résolu : déclarer et initialiser la pile
- Décrire les déclarations et l'initialisation nécessaires pour implémenter une pile de jusqu'à 50 entiers utilisant un tableau. [5]
- Un tableau de 50 éléments de type
INTEGER,DECLARE Stack : ARRAY[1:50] OF INTEGER, pour garder les éléments. - Une constante ou variable
MaxSizefixée à 50, afin que push puisse tester pour plein. - Un
INTEGERpointeur de haut-de-pile,Top, initialisé à 0 pour montrer que la pile est vide ; pop le teste pour sous-charge, et push le compare avecMaxSizepour surcharge.
Which belong in the declaration and initialisation of an array-based stack? Select all · tout that apply. · Quels éléments appartiennent à la déclaration et l'initialisation d'une pile à base de tableau ? Sélectionnez tous ceux qui s'appliquent.
A stack needs one pointer, Top. A front pointer belongs to a queue. · Une pile a besoin d'un seul pointeur, Top. Un pointeur front appartient à une file.
A queue in a plain array
- Two pointers:
Frontfor the next item to leave,Rearfor the next free space. Enqueue stores atRearand moves it on; dequeue reads atFrontand moves it on. - Both pointers only ever move forward, so after a few operations they march off the end of the array while the cells at the start sit empty and unusable.
- The fix is to let the pointers wrap around.
Une file dans un tableau simple
- Deux pointeurs :
Frontpour le prochain élément à partir,Rearpour le prochain espace libre. Enqueue stocke àRearet le déplace ; dequeue lit àFrontet le déplace. - Les deux pointeurs ne bougent jamais qu'en avant, donc après quelques opérations ils marchent hors de fin du tableau tandis que les cellules au début restent vides et inutilisables.
- La solution est de laisser les pointeurs faire un tour.
The circular array
- A circular array 循环数组 wraps a pointer back to the first cell when it passes the last: with 1-based indices,
Rear ← (Rear MOD MaxSize) + 1. - Enqueue(x): check not full;
Rear ← (Rear MOD MaxSize) + 1;Queue[Rear] ← x. Dequeue(): check not empty; returnQueue[Front];Front ← (Front MOD MaxSize) + 1. - Keep a separate count: when the queue is completely full and when it is completely empty the two pointers are in the same relative position, so the pointers alone cannot tell the two apart.
After the last cell comes the first cell
Le tableau circulaire
- Un tableau circulaire 循环数组 renvoie un pointeur à la première cellule quand il passe la dernière : avec indices 1-based,
Rear ← (Rear MOD MaxSize) + 1. - Enqueue(x) : vérifier non plein ;
Rear ← (Rear MOD MaxSize) + 1;Queue[Rear] ← x. Dequeue() : vérifier non vide ; retournerQueue[Front];Front ← (Front MOD MaxSize) + 1. - Garder un count séparé : quand la file est complètement pleine et complètement vide, les deux pointeurs sont dans la même position relative, donc les pointeurs seuls ne peuvent pas les distinguer.
Après la dernière cellule vient la première cellule
Implementing ADTs with arrays · Implémenter des TADs avec des tableaux
FIFO
A queue · file d'attente is first-in-first-out — enqueue at the back, dequeue from the front. · Une file · fichier est premier-entré-premier-sorti — enfiler à l'arrière, défiler depuis le devant.
Why use a circular array for a queue? · Pourquoi utiliser un tableau circulaire pour une file ?
A linear queue wastes the cells at the start as Front advances; wrapping with MOD reuses them. · Une file linéaire gaspille les cases au début quand Front avance ; le tournant avec MOD les réutilise.
A circular queue uses MOD so the front/rear pointers wrap around and reuse the cells freed at the start of the array. · Une file circulaire utilise MOD pour que les pointeurs front/rear fassent le tour et réutilisent les cases libérées au début du tableau.
(pointer MOD MaxSize) + 1 wraps the index back to the first cell, so a linear queue no longer wastes the cells Front has passed. · (pointer MOD MaxSize) + 1 ramène l'index à la première case, afin qu'une file linéaire ne gaspille plus les cases que Front a dépassées.
Worked example: walk the pointers
- With
MaxSize = 6: ifRear = 5, then(5 MOD 6) + 1 = 6, so the next item goes in cell 6. IfRear = 6, then(6 MOD 6) + 1 = 1: the pointer wraps to cell 1. - A circular queue is held in an array of size 5, indices 0 to 4, with
Front = 3,Rear = 3and one item stored. Two items are added, then two removed. With 0-based indices each move is(pointer + 1) MOD 5. - Adding twice moves
Rear: 3 → 4, then 4 → 0, because (4 + 1) MOD 5 = 0. Removing twice movesFront: 3 → 4 → 0. One item remains, at index 0, and the queue reused the cells freed at the start of the array.
Exemple résolu : parcourir les pointeurs
- Avec
MaxSize = 6: siRear = 5, alors(5 MOD 6) + 1 = 6, donc le prochain élément va dans la cellule 6. SiRear = 6, alors(6 MOD 6) + 1 = 1: le pointeur fait un tour vers la cellule 1. - Une file circulaire est contenue dans un tableau de taille 5, indices 0 à 4, avec
Front = 3,Rear = 3et un élément stocké. Deux éléments sont ajoutés, puis deux retirés. Avec indices 0-based chaque mouvement est(pointer + 1) MOD 5. - Ajouter deux fois déplace
Rear: 3 → 4, puis 4 → 0, parce que (4 + 1) MOD 5 = 0. Retirer deux fois déplaceFront: 3 → 4 → 0. Un élément reste, à l'index 0, et la file a réutilisé les cellules libérées au début du tableau.
A circular queue uses cells 1 to 6 and Rear = 6. After Rear ← (Rear MOD 6) + 1, where does the next item go? · Une file circulaire utilise les cases 1 à 6 et Rear = 6. Après Rear ← (Rear MOD 6) + 1, où va le prochain élément ?
6 MOD 6 = 0, plus 1 gives 1. The pointer wraps to the start of the array. · 6 MOD 6 = 0, plus 1 donne 1. Le pointeur fait le tour vers le début du tableau.
Worked example: the enqueue algorithm in words
- Describe the algorithm for adding an item to a circular queue. [4]
- If the count equals the size, report that the queue is full and stop.
- Otherwise add one to the rear pointer; if it is now past the last index, set it to the first index.
- Store the item at the rear pointer and add one to the count.
Exemple résolu : l'algorithme d'enqueue en mots
- Décrire l'algorithme pour ajouter un élément à une file circulaire. [4]
- Si count égale size, rapport que la file est pleine et arrêter.
- Sinon ajouter un au pointeur rear ; s'il est maintenant passé le dernier index, le fixer au premier index.
- Stocker l'élément au pointeur rear et ajouter un à count.
Put the steps of adding to a circular queue in order. · Mettez les étapes d'ajout dans une file circulaire dans l'ordre.
Check, move, wrap, store, count. The wrap is what makes the array circular. · Vérifier, déplacer, tourner, stocker, compter. Le tournant rend le tableau circulaire.
A linked list in an array
- Use an array of node records, each with a
Nextindex;-1marks the end. AHeadindex marks the first node,-1if the list is empty. - The unused slots are chained into a free list 空闲列表 from
FreeListHead, exactly as the data list chains its used ones.
- Insert: take the slot at
FreeListHead, set itsValueandNext, then rewire the previous node'sNextorHead. Delete: unlink the node and return its slot to the front of the free list.
Two lists share one array: the data list and the free list
Une liste chaînée dans un tableau
- Utilisez un tableau d'enregistrements de nœuds, chacun avec un index de
Next;-1marque la fin. Un index deHeadmarque le premier nœud,-1si la liste est vide. - Les cases inutilisées sont enchaînées dans une free list 空闲列表 depuis
FreeListHead, exactement comme la liste de données enchaîne ses utilisées.
TYPE TNode
DECLARE Value : INTEGER
DECLARE Next : INTEGER // index of the next node, or -1
ENDTYPE
DECLARE Nodes : ARRAY[1:MaxSize] OF TNode
DECLARE Head : INTEGER // -1 when empty
DECLARE FreeListHead : INTEGER // first unused slot
- Insertion : prendre la case à
FreeListHead, définir sonValueetNext, puis rewire leNextdu nœud précédent ouHead. Suppression : délier le nœud et retourner sa case au début de la free list.
Deux listes partagent un tableau : la liste de données et la free list
In an array-based linked list, the free list: · Dans une liste chaînée à base de tableau, la liste libre :
The free list links the spare slots, so an insert can grab one and a delete can return one — like a second linked list of empties. · La liste libre relie les emplacements disponibles, donc une insertion peut en prendre une et une suppression peut en retourner une — comme une seconde liste chaînée de vides.
Worked example: insert into the array-held list
DataandPointerarrays hold the list 1 → 3 → 4, withStart = 1; index 1 holdsD40, index 3 holdsD32, index 4 holdsD11with a null pointer. The free list starts at index 2 and continues 2 → 5. InsertD6betweenD32andD11.- Take the first free node, index 2, and set
FreeStartto its pointer, 5. StoreD6inData[2]. - Set
Pointer[2]to the valuePointer[3]held, which is 4. Then setPointer[3]to 2. - The list now reads 1 → 3 → 2 → 4 and the free list is 5 → null. The implementation, if asked: an array for the data, a parallel array (or record field) for the pointers, a start pointer, and a free-list pointer.
Exemple résolu : insérer dans la liste tenue par tableau
DataetPointertableaux tiennent la liste 1 → 3 → 4, avecStart = 1; index 1 contientD40, index 3 contientD32, index 4 contientD11avec un pointeur null. La free list commence à index 2 et continue 2 → 5. InsérerD6entreD32etD11.- Prendre le premier nœud libre, index 2, et définir
FreeStartvers son pointeur, 5. StockerD6dansData[2]. - Définir
Pointer[2]sur la valeurPointer[3]tenue, qui est 4. Puis définirPointer[3]sur 2. - La liste se lit maintenant 1 → 3 → 2 → 4 et la free list est 5 → null. L'implémentation, si demandée : un tableau pour les données, un tableau parallèle (ou champ record) pour les pointeurs, un pointeur de départ, et un pointeur de free-list.
In the worked example, after D6 is inserted the free list starts at index ____. · Dans l'exemple résolu, après l'insertion de D6, la liste libre commence à l'indice ____.
Index 2 was taken from the free list, so FreeStart moves to what index 2 pointed to, which was 5. · L'indice 2 a été pris de la liste libre, donc FreeStart passe à ce que l'indice 2 pointait, qui était 5.
When inserting into the list, the previous node's pointer should be changed before the new node's pointer is set. · Lors de l'insertion dans la liste, le pointeur du nœud précédent doit être modifié avant que le pointeur du nouveau nœud ne soit défini.
Set the new node's pointer to the old next node first. Rewiring the previous node first loses the address of the rest of the list. · Définissez d'abord le pointeur du nouveau nœud sur l'ancien nœud suivant. Rebrancher le nœud précédent en premier fait perdre l'adresse du reste de la liste.
Marks that slip away
- The checks come first: full before push or enqueue, empty before pop or dequeue. Describe them; they are marks.
- The wrap formula depends on the indices:
(Rear MOD MaxSize) + 1for 1-based,(Rear + 1) MOD Sizefor 0-based. Match the question's bounds. - The count is what tells a full circular queue from an empty one. Pointers alone cannot.
- Set the new node's
Nextbefore rewiring the previous node, and return a deleted node's slot to the free list, or the array slowly fills with unreachable cells.
Pièges qui font perdre des points
- Les vérifications viennent en premier : plein avant push ou enqueue, vide avant pop ou dequeue. Les décrire ; ce sont des points.
- La formule de wrap dépend des indices :
(Rear MOD MaxSize) + 1pour 1-based,(Rear + 1) MOD Sizepour 0-based. Correspondre aux bornes de la question. - Le count est ce qui distingue une file circulaire pleine d'une vide. Les pointeurs seuls ne le peuvent pas.
- Définir le
Nextdu nouveau nœud avant de rewire le nœud précédent, et retourner la case d'un nœud supprimé à la free list, sinon le tableau se remplira lentement de cases inaccessibles.
You've got it
- stack in an array:
Stack[1:MaxSize]and aToppointer starting at 0;Top = MaxSizeis overflow,Top = 0is underflow - circular queue:
FrontandRearwrap withMOD; a separate count distinguishes full from empty - linked list in an array: node records with a
Nextindex, aHead, and a free list chaining the spare slots - every operation is check, then pointer arithmetic, then store or read; the ADT's behaviour is unchanged by how it is stored
Vous avez compris
- pile dans un tableau :
Stack[1:MaxSize]et unToppointeur commençant à 0 ;Top = MaxSizeest overflow,Top = 0est underflow - file circulaire :
FrontetRearfont un tour avecMOD; un count séparé distingue plein de vide - liste chaînée dans un tableau : records de nœuds avec un
Nextindex, unHead, et une free list enchaînant les cases libres - chaque opération est check, ensuite arithmétique de pointeur, ensuite store ou read ; le comportement de l'ADT est inchangé par la façon dont il est stocké