CKTIS / JavaScript
Collections : pile, file et algorithme LRU
Une pile traite les éléments selon LIFO, une file selon FIFO, et un cache LRU évince l’entrée la moins récemment utilisée. En JavaScript, on peut les implémenter avec Array et Map, mais il faut gérer consciemment l’ordre, le coût des opérations et les valeurs absentes.
Version : ECMAScript and Web APIs; exact feature edition and browser support reviewed per entry; Node 24 in repository does not prove browser API support
Syntaxe
stack.push(value); stack.pop(); queue.push(value); queue.shift(); map.delete(key); map.set(key, value); map.keys().next().valuePile, file et LRU désignent des règles de gestion des collections, et non des noms de constructeurs intégrés. Une pile suit LIFO : le dernier élément ajouté est le premier retiré. Un tableau avec push() et pop() suffit pour une pile simple. Une file suit FIFO : le premier élément ajouté est le premier retiré ; une version simple utilise push() et shift().
shift() peut nécessiter le déplacement des propriétés indexées ; ne supposez donc pas que la suppression au début a un coût constant. Pour une grande file, envisagez un tampon circulaire ou un indice de tête avec compactage périodique ; libérez les références aux objets consommés. pop() et shift() renvoient undefined pour un tableau vide, ce qui ne permet pas de distinguer une collection vide d’une collection contenant la valeur undefined.
LRU (least recently used) évince l’entrée la moins récemment utilisée lorsque la capacité est dépassée. Map conserve l’ordre d’insertion, mais ni get() ni set() sur une clé existante ne met à jour sa position. Supprimez puis réinsérez l’entrée lors d’une lecture réussie et lors d’une écriture ; la première clé de keys() désigne alors la candidate à l’éviction. L’exemple a une capacité fixe de 2 ; une version paramétrée devrait vérifier que la capacité est un entier positif.
Dans l’exemple, has() distingue une clé absente d’une entrée contenant undefined, même si le get() public renvoie undefined dans les deux cas. La spécification exige un accès moyen sous-linéaire pour Map, sans garantir O(1). Le code utilise la syntaxe et les fonctionnalités disponibles dans ECMAScript 2015 ; il ne nécessite aucune Web API de navigateur. L’exécuter dans Node ne prouve pas sa compatibilité avec un navigateur cible.
Exemples
const stack = [];
stack.push('a', 'b');
console.log(stack.pop());
const queue = [];
queue.push('a', 'b');
console.log(queue.shift());
const cache = new Map();
const capacity = 2;
function put(key, value) {
cache.delete(key);
cache.set(key, value);
if (cache.size > capacity) {
cache.delete(cache.keys().next().value);
}
}
function get(key) {
if (!cache.has(key)) return undefined;
const value = cache.get(key);
cache.delete(key);
cache.set(key, value);
return value;
}
put('a', 1);
put('b', 2);
console.log(get('a'));
put('c', 3);
console.log(cache.has('b'));
console.log([...cache.keys()].join(','));Résultat
b a 1 false a,c
Le code affiché et le résultat déclaré ont été vérifiés dans un environnement isolé selon la méthode consignée dans la preuve de vérification de cette version exacte.