Implementación de Queue en Javascript

En este artículo, estaríamos implementando la estructura de datos de cola en javascript. Una cola funciona según el principio FIFO (primero en entrar, primero en salir). Por lo tanto, realiza dos operaciones básicas que son la adición de elementos al final de la cola y la eliminación de elementos del principio de la cola. Al igual que Stack , Queue también es una estructura de datos lineal .

Nota: suponiendo que una cola pueda crecer dinámicamente, no estamos considerando la condición de desbordamiento.
Ahora veamos un ejemplo de clase de cola usando una array:

Ejemplo:

// Queue class
class Queue
{
    // Array is used to implement a Queue
    constructor()
    {
        this.items = [];
    }
                  
    // Functions to be implemented
    // enqueue(item)
    // dequeue()
    // front()
    // isEmpty()
    // printQueue()
}

Como en la definición anterior, hemos creado un esqueleto de una clase de cola que contiene un constructor en el que declaramos una array para implementar la cola. Por lo tanto, con la creación de un objeto de una clase de cola, este constructor se llamará automáticamente y la array se declarará

Implementemos cada una de estas funciones:

  1. enqueue() – Agrega un elemento a la cola

    // enqueue function
    enqueue(element)
    {    
        // adding element to the queue
        this.items.push(element);
    }

    Esta función agrega un elemento al final de una cola. Hemos utilizado el método de array push() para agregar un elemento al final de la cola.

  2. dequeue() – Elimina un elemento de la cola

    // dequeue function
    dequeue()
    {
        // removing element from the queue
        // returns underflow when called 
        // on empty queue
        if(this.isEmpty())
            return "Underflow";
        return this.items.shift();
    }

    Esta función elimina un elemento del principio de una cola. Hemos utilizado el método de cambio de una array para eliminar un elemento de la cola.

  3. front() – devuelve el elemento frontal de la cola

    // front function
    front()
    {
        // returns the Front element of 
        // the queue without removing it.
        if(this.isEmpty())
            return "No elements in Queue";
        return this.items[0];
    }

    Esta función devuelve el elemento frontal de la cola. Simplemente devolvemos el elemento 0 de una array para obtener el frente de una cola.

Métodos auxiliares

Declaremos algún método auxiliar que es bastante útil mientras se trabaja con la cola.

  1. isEmpty() : devuelve verdadero si la cola está vacía

    // isEmpty function
    isEmpty()
    {
        // return true if the queue is empty.
        return this.items.length == 0;
    }

    En esta función, hemos utilizado la propiedad de longitud de una array y si la longitud de la array es 0, la cola está vacía.

  2. printQueue() : devuelve todos los elementos de una cola.

    // printQueue function
    printQueue()
    {
        var str = "";
        for(var i = 0; i < this.items.length; i++)
            str += this.items[i] +" ";
        return str;
    }

    En este método concatenamos todos los elementos de la cola en una string y devolvemos la string

Nota: Se pueden declarar diferentes métodos auxiliares en la clase Queue según el requisito.

Implementación

Ahora usemos la clase de cola y su método diferente descrito anteriormente

// creating object for queue class
var queue = new Queue();
              
  
// Testing dequeue and pop on an empty queue
// returns Underflow
console.log(queue.dequeue());
  
// returns true
console.log(queue.isEmpty());
  
// Adding elements to the queue
// queue contains [10, 20, 30, 40, 50]
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
queue.enqueue(40);
queue.enqueue(50);
queue.enqueue(60);
  
// returns 10
console.log(queue.front());
  
// removes 10 from the queue
// queue contains [20, 30, 40, 50, 60]
console.log(queue.dequeue());
  
// returns 20
console.log(queue.front());
  
// removes 20
// queue contains [30, 40, 50, 60]
console.log(queue.dequeue());
  
// printing the elements of the queue
// prints [30, 40, 50, 60]
console.log(queue.printQueue());

Ahora, una vez que hayamos terminado con la implementación de la clase Queue, podemos usarla en diferentes aplicaciones.

Aplicación: un método interesante para generar números binarios del 1 al n

En este problema generamos diferentes números binarios del 1 al n.

// function to generate binary numbers
function generatePrintBinary(n)
{
    // Create an empty queue of strings
    var q = new Queue();
           
    // Enqueue the first binary number
    q.enqueue("1");
           
    // This loops is like BFS of a tree with 1 as root
    // 0 as left child and 1 as right child and so on
    while(n-- > 0)
    {
        // print the front of queue
        var s1 = q.front();
        q.dequeue();
        console.log(s1);
               
        // Store s1 before changing it
        var s2 = s1;
               
        // Append "0" to s1 and enqueue it
        q.enqueue(s1 + "0");
               
        // Append "1" to s2 and enqueue it. Note that s2 contains
        // the previous front
        q.enqueue(s2 + "1");
     }
}
  
// calling the above function    
// prints [1 10 11 100 101]
generatePrintBinary(5);

Este artículo es una contribución de Sumit Ghosh . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *