Ejemplos detallados con imágenes y textos para implementar colas en JavaScript

Recomendaciones relacionadas: tutorial de javascript

1. Estructura de datos de la cola

• La cola es un tipo de estructura de datos "primero en entrar, primero en salir" (FIFO). El primer elemento en cola (entrada) es el primer elemento en cola (salida).
• La cola tiene 2 punteros: cabeza y cola. El elemento más antiguo de la cola está al principio y el elemento más nuevo está al final.
• La cola es como hacer cola en el metro. Los pasajeros cerca de la puerta están al principio de la cola y los pasajeros que acaban de entrar en la cola están al final de la cola.

Desde una perspectiva de alto nivel, una cola es una estructura de datos que nos permite procesar cada elemento de datos en el orden en que están almacenados en la base de datos.

2. Operaciones en la cola

La cola admite 2 operaciones principales: poner en cola y quitar de la cola. Además, puede resultarle útil realizar operaciones de vista y longitud en la cola.

• Operación de puesta en cola <br/>La operación de puesta en cola consiste en insertar un elemento al final de la cola y el elemento insertado se convierte en el final de la cola.

La operación de puesta en cola en la figura anterior inserta el elemento 8 al final y 8 se convierte en el final de la cola.

queue.enqueue(8);

• Operación de retirada de la cola <br/> La operación de retirada de la cola consiste en extraer el elemento al principio de la cola y el siguiente elemento de la cola se convierte en el elemento principal.

En la imagen de arriba, la operación de sacar de la cola regresa y elimina el elemento 7 de la cola. Después de sacarlo de la cola, el artículo 2 se convierte en el nuevo elemento principal.

queue.dequeue(); // => 7

• operación de inspección <br/> La operación de inspección lee el comienzo de la cola sin cambiar la cola.

El elemento 7 es el comienzo de la cola en la imagen de arriba, y la operación de inspección solo devuelve el encabezado (elemento) 7 sin modificar la cola.

queue.peek(); // => 7

• longitud de la cola La operación de longitud calcula cuántos elementos contiene la cola.

Hay 4 elementos en la cola de la imagen: 4, 6, 2 y 7. Como resultado, la longitud de la cola es 4.

queue.length; // => 4

• Complejidad del tiempo de operación de la cola Lo importante para todas las operaciones de la cola (poner en cola, quitar la cola, ver y longitud) es que todas estas operaciones deben ejecutarse en un tiempo fijo O(1).

El tiempo constante O(1) significa que, sin importar el tamaño de la cola (puede tener 10 o 1 millón de elementos): las operaciones de poner en cola, quitar la cola, mirar y longitud deben realizarse todas simultáneamente.

3. Implementación de colas en JavaScript

Veamos una posible implementación de una estructura de datos de cola manteniendo el requisito de que todas las operaciones deben realizarse en tiempo constante O(1).

cola de clase {
  constructor() {
    this.items = {};
    this.headIndex = 0;
    this.tailIndex = 0;
  }

  poner en cola (elemento) {
    this.items[this.tailIndex] = artículo;
    this.tailIndex++;
  }

  sacar de cola() {
    elemento constante = this.items[this.headIndex];
    eliminar this.items[this.headIndex];
    this.headIndex++;
    artículo devuelto;
  }

  mirar() {
    devolver this.items[this.headIndex];
  }

  obtener longitud() {
    devolver this.tailIndex - this.headIndex;
  }
}

cola constante = nueva cola();

cola.encola(7);
cola.encola(2);
cola.encola(6);
cola.encola(4);

cola.dequeue(); // => 7

cola.peek(); // => 2

queue.length; // => 3

const queue = new Queue() es cómo crear una instancia de una cola.

Llame al método queue.enqueue(7) para poner el elemento 7 en la cola.

queue.dequeue() elimina un elemento principal de la cola, mientras queue.peek() solo mira desde el principio.

Finalmente, queue.length muestra cuántos elementos quedan en la cola.

Respecto a la implementación: dentro de la clase Queue, el objeto simple this.items contiene los elementos en la cola por índice numérico. this.headIndex realiza un seguimiento del índice del elemento principal y this.tailIndex realiza un seguimiento del índice del elemento final.

• Complejidad de los métodos de cola

Los métodos queue(), dequeue(), peek() y length() de la clase Queue solo utilizan:

acceso a atributos (como this.items[this.headIndex]),

o realizar operaciones aritméticas (como this.headIndex++).

Por lo tanto, la complejidad temporal de estos métodos es un tiempo constante O (1).

4. Resumen

La estructura de datos de la cola es un tipo de "primero en entrar, primero en salir" (FIFO): el primer elemento que se pone en cola es el primer elemento que se retira de la cola.

Las colas tienen 2 operaciones principales: poner en cola y quitar de la cola. Además, las colas pueden tener operaciones auxiliares como vista y longitud.

Todas las operaciones en cola deben realizar O(1) en tiempo constante.

Recomendaciones relacionadas: Tutorial de aprendizaje de JavaScript

Lo anterior es una explicación detallada de la implementación de colas en JavaScript con ejemplos e imágenes. Para obtener más información, preste atención a otros artículos relacionados en el sitio web chino de PHP.