LIFO ou FIFO ? Guide des piles/files d'attente

Suppose une compréhension de la notation Big O. Les exemples sont en JavaScript. Références d'informations "Cracking the Coding Interview" par Gayle Laakmann McDowell

Aujourd'hui, nous allons explorer deux structures de données essentielles : les piles et les files d'attente. Nous plongerons dans leurs concepts, leurs cas d'utilisation et les implémenterons en JavaScript en utilisant à la fois des approches classiques et basées sur des prototypes.

---

Piles : dernier entré, premier sorti (LIFO)

Imaginez une pile de crêpes : la dernière que vous mettez dessus est la première que vous mangerez. C'est exactement ainsi que fonctionne une structure de données de pile. Il suit le principe Last In, First Out (LIFO).

Opérations clés

• push(item) : Ajouter un élément en haut de la pile
• pop() : supprime l'élément supérieur de la pile
• peek() : renvoie l'élément du haut sans le supprimer
• isEmpty() : Vérifiez si la pile est vide

Cas d'utilisation

Les piles sont particulièrement utiles dans les scénarios impliquant :

• Algorithmes récursifs
• Mécanismes d'annulation dans les éditeurs de texte

Implémentation JavaScript

POO classique

class Stack {
  constructor() {
    this.items = [];
  }

  push(element) {
    this.items.push(element);
  }

  pop() {
    if (this.isEmpty()) {
      return "Stack is empty";
    }
    return this.items.pop();
  }

  peek() {
    if (this.isEmpty()) {
      return "Stack is empty";
    }
    return this.items[this.items.length - 1];
  }

  isEmpty() {
    return this.items.length === 0;
  }

  size() {
    return this.items.length;
  }

  clear() {
    this.items = [];
  }
}

Basé sur un prototype

function Stack() {
  this.items = [];
}

Stack.prototype.push = function(element) {
  this.items.push(element);
};

Stack.prototype.pop = function() {
  if (this.isEmpty()) {
    return "Stack is empty";
  }
  return this.items.pop();
};

Stack.prototype.peek = function() {
  if (this.isEmpty()) {
    return "Stack is empty";
  }
  return this.items[this.items.length - 1];
};

Stack.prototype.isEmpty = function() {
  return this.items.length === 0;
};

Stack.prototype.size = function() {
  return this.items.length;
};

Stack.prototype.clear = function() {
  this.items = [];
};

---

Files d'attente : premier entré, premier sorti (FIFO)

Maintenant, concentrons-nous sur les files d'attente. Contrairement aux piles, les files d'attente suivent le principe du Premier entré, premier sorti (FIFO). Pensez à une file d’attente dans une salle de concert : la première personne à arriver est la première à entrer.

Opérations clés

• enqueue(item) : Ajouter un élément à la fin de la file d'attente
• dequeue() : Supprime le premier élément de la file d'attente
• peek() : renvoie le premier élément sans le supprimer
• isEmpty() : Vérifiez si la file d'attente est vide

Cas d'utilisation

Les files d'attente sont couramment utilisées dans :

• Algorithmes de recherche en largeur d'abord
• Planification des tâches

Implémentation JavaScript

POO classique

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.start = null;
    this.end = null;
    this.size = 0;
  }

  enqueue(element) {
    const newNode = new Node(element);
    if (this.isEmpty()) {
      this.start = newNode;
      this.end = newNode;
    } else {
      this.end.next = newNode;
      this.end = newNode;
    }
    this.size++;
  }

  dequeue() {
    if (this.isEmpty()) {
      return "Queue is empty";
    }
    const removedData = this.start.data;
    this.start = this.start.next;
    this.size--;
    if (this.isEmpty()) {
      this.end = null;
    }
    return removedData;
  }

  peek() {
    if (this.isEmpty()) {
      return "Queue is empty";
    }
    return this.start.data;
  }

  isEmpty() {
    return this.size === 0;
  }

  getSize() {
    return this.size;
  }

  clear() {
    this.start = null;
    this.end = null;
    this.size = 0;
  }
}

Basé sur un prototype

function Node(data) {
  this.data = data;
  this.next = null;
}

function Queue() {
  this.start = null;
  this.end = null;
  this.size = 0;
}

Queue.prototype.enqueue = function(element) {
  const newNode = new Node(element);
  if (this.isEmpty()) {
    this.start = newNode;
    this.end = newNode;
  } else {
    this.end.next = newNode;
    this.end = newNode;
  }
  this.size++;
};

Queue.prototype.dequeue = function() {
  if (this.isEmpty()) {
    return "Queue is empty";
  }
  const removedData = this.start.data;
  this.start = this.start.next;
  this.size--;
  if (this.isEmpty()) {
    this.end = null;
  }
  return removedData;
};

Queue.prototype.peek = function() {
  if (this.isEmpty()) {
    return "Queue is empty";
  }
  return this.start.data;
};

Queue.prototype.isEmpty = function() {
  return this.size === 0;
};

Queue.prototype.getSize = function() {
  return this.size;
};

Queue.prototype.clear = function() {
  this.start = null;
  this.end = null;
  this.size = 0;
};

---

Analyse des performances

Les piles et les files d'attente offrent $O(1)$O(1) complexité temporelle pour leurs opérations principales (push/pop pour les piles, mise en file d'attente/retrait des files d'attente) lorsqu'elles sont mises en œuvre efficacement. Cela les rend très performants pour leurs cas d'utilisation spécifiques.

Ils fournissent tous deux des solutions élégantes à de nombreux problèmes de programmation courants et constituent la base de structures de données et d'algorithmes plus complexes. En comprenant et en implémentant ces structures en JavaScript, vous êtes bien équipé pour résoudre un large éventail de problèmes de Leetcode/Algorithme ?.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!