Estructuras de datos con JavaScript: Pila y cola

() translation by (you can also view the original English article)

Dos de las estructuras de datos más comúnmente utilizadas en el desarrollo web son pilas y colas. Muchos usuarios de Internet, incluidos los desarrolladores web, desconocen este sorprendente hecho. Si eres uno de estos desarrolladores, prepárate para dos ejemplos esclarecedores: la operación 'deshacer' de un editor de texto utiliza una pila para organizar los datos; el bucle de eventos de un navegador web, que maneja eventos (clics, traslados, etc.), utiliza una cola para procesar datos.

Ahora haz una pausa por un momento e imagina cuántas veces nosotros, como usuarios y desarrolladores, usamos pilas y colas. Eso es increíble, ¿verdad? Debido a su ubicuidad y similitud en el diseño, he decidido usarlos para presentarles las estructuras de datos.

Una pila o Stack

En informática, una pila es una estructura de datos lineal. Si esta afirmación tiene un valor marginal para ti, como originalmente lo hizo conmigo, considera esta alternativa: una pila organiza los datos en orden secuencial.

Este orden secuencial se describe comúnmente como una pila de platos en una cafetería. Cuando se agrega una placa a una pila de platos, la placa retiene el orden de cuándo se agregó; además, cuando se agrega una placa, se empuja hacia la parte inferior de una pila. Cada vez que agregamos una placa nueva, la placa se empuja hacia la parte inferior de la pila, pero también representa la parte superior de la pila de placas.

Este proceso de agregar placas retendrá el orden secuencial de cuando cada placa se agregó a la pila. La eliminación de las placas de una pila también conservará el orden secuencial de todas las placas. Si se quita una placa de la parte superior de una pila, cada otra placa en la pila aún conservará el orden correcto en la pila. Lo que estoy describiendo, posiblemente con demasiadas palabras, es cómo se agregan y quitan los platos en la mayoría de las cafeterías.

Para proporcionar un ejemplo más técnico de una pila, recordemos la operación 'deshacer' de un editor de texto. Cada vez que se agrega texto a un editor de texto, este se inserta en una pila. La primera adición al editor de texto representa la parte inferior de la pila; el cambio más reciente representa la parte superior de la pila. Si un usuario quiere deshacer el cambio más reciente, se elimina la parte superior de la pila. Este proceso puede repetirse hasta que no haya más adiciones a la pila, que es un archivo en blanco.

Operaciones de una pila

Como ahora tenemos un modelo conceptual de una pila, vamos a definir las dos operaciones de una pila:

push(data) agrega datos.
pop() elimina los datos agregados más recientemente.

Implementación de una pila

¡Ahora escribamos el código para una pila!

Propiedades de una pila

Para nuestra implementación, crearemos un constructor llamado Stack. Cada instancia de Stack tendrá dos propiedades: _size y _storage.

1	function Stack() {
2	this._size = 0;
3	this._storage = {};
4	}

this._storage permite que cada instancia de Stack tenga su propio contenedor para almacenar datos; this._size refleja la cantidad de veces que se enviaron los datos a la versión actual de una pila. Si se crea una nueva instancia de Stack y los datos se insertan en su almacenamiento, this._size aumentará a 1. Si se vuelven a insertar datos en la pila, this._size aumentará a 2. Si se eliminan los datos de la pila, este ._size disminuirá a 1.

Métodos de una pila

Necesitamos definir métodos que puedan agregar (empujar) y eliminar (pop) datos de una pila. Comencemos por empujar datos.

Método 1 de 2: push(data)

(Este método se puede compartir entre todas las instancias de Stack, así que lo agregaremos al prototipo de Stack).

Tenemos dos requisitos para este método:

Cada vez que agregamos datos, queremos incrementar el tamaño de nuestra pila.
Cada vez que agregamos datos, queremos conservar el orden en que se agregaron.

Stack.prototype.push = function(data) {
    // increases the size of our storage
    var size = this._size++;

    // assigns size as a key of storage
    // assigns data as the value of this key
    this._storage[size] = data;
};

Nuestra implementación de push(data) incluye la siguiente lógica. Declara una variable llamada size y asígnale el valor de this._size++. Asigna la variable size como una clave de this._storage. Y asigna data como el valor de una clave correspondiente.

Si nuestra pila invoca push(data) cinco veces, entonces el tamaño de nuestra pila sería 5. El primer empujón a la pila asignaría esa información una clave de 1 en this._storage. La quinta invocación de push(data) asignaría a esos datos una clave de 5 en this._storage. ¡Acabamos de asignar orden a nuestros datos!

Método 2 de 2: pop()

Ahora podemos enviar datos a una pila; el siguiente paso lógico es extraer (eliminar) datos de una pila. Visualizar datos de una pila no es simplemente eliminar datos; está eliminando solo los datos agregados más recientemente.

Aquí están nuestros objetivos para este método:

Usa el tamaño actual de una pila para obtener los datos agregados más recientemente.
Eliminar los datos agregados más recientemente.
Decrementa _this._size por uno.
Devuelve los datos eliminados más recientemente.

Stack.prototype.pop = function() {
    var size = this._size,
        deletedData;

    deletedData = this._storage[size];

    delete this._storage[size];
    this.size--;

    return deletedData;
};

pop() cumple con cada uno de nuestros cuatro objetivos. Primero, declaramos dos variables: size que se inicializa al tamaño de una pila; deletedData que se asigna a los datos agregados más recientemente a una pila. En segundo lugar, eliminamos el par clave-valor de nuestros datos agregados más recientemente. En tercer lugar, disminuimos el tamaño de una pila en 1. En cuarto lugar, devolvemos los datos que se eliminaron de la pila.

Si probamos nuestra implementación actual de pop(), encontramos que funciona para el siguiente caso de uso. Si empujamos los datos con push(data) a una pila, el tamaño de la pila se incrementa en uno. Si extraemos datos de nuestra pila con pop(), el tamaño de nuestra pila se reduce en uno.

Sin embargo, surge un problema cuando revertimos el orden de invocación. Considera la siguiente situación: invocamos pop() y luego push(data). El tamaño de nuestra pila cambia a -1 y luego a 0. ¡Pero el tamaño correcto de nuestra pila es 1!

Para manejar este caso de uso, agregaremos una instrucción if a pop().

Stack.prototype.pop = function() {
    var size = this._size,
        deletedData;

    if (size) {
        deletedData = this._storage[size];

        delete this._storage[size];
        this._size--;

        return deletedData;
    }
}; 

Con la adición de nuestra declaración if, el cuerpo de nuestro código se ejecuta solo cuando hay datos en nuestro almacenamiento.

Implementación completa de una pila

Nuestra implementación de Stack está completa. Independientemente del orden en que invoquemos cualquiera de nuestros métodos, ¡nuestro código funciona! Aquí está la versión final de nuestro código:

function Stack() {
    this._size = 0;
    this._storage = {};
}

Stack.prototype.push = function(data) {
    var size = ++this._size;
    this._storage[size] = data;
};

Stack.prototype.pop = function() {
    var size = this._size,
        deletedData;

    if (size) {
        deletedData = this._storage[size];

        delete this._storage[size];
        this._size--;

        return deletedData;
    }
}; 

De la pila a la cola

Una pila es útil cuando queremos agregar datos en orden secuencial y eliminar datos. Según su definición, una pila puede eliminar solo los datos agregados más recientemente. ¿Qué sucede si queremos eliminar los datos más antiguos? Queremos usar una estructura de datos llamada cola.

Una cola

Similar a una pila, una cola es una estructura de datos lineal. A diferencia de una pila, una cola solo elimina los datos agregados más antiguos.

Para ayudarte a conceptualizar cómo funcionaría esto, tomemos un momento para usar una analogía. Imagina una cola que es muy similar al sistema de venta de entradas de una tienda de delicatessen. Cada cliente toma un boleto y se sirve cuando se llama a su número. El cliente que toma el primer boleto debe ser atendido primero.

Imaginemos además que este ticket tiene el número "uno" en pantalla. El siguiente boleto tiene el número "dos" exhibido en él. El cliente que toma el segundo boleto será atendido en segundo lugar. (Si nuestro sistema de emisión de boletos funcionara como una pila, ¡el cliente que ingresó primero en la pila sería el último en ser atendido!)

Un ejemplo más práctico de una cola es el bucle de eventos de un navegador web. A medida que se desencadenan diferentes eventos, como el clic de un botón, se agregan a la cola de un bucle de evento y se manejan en el orden en que ingresaron a la cola.

Operaciones de una cola

Como ahora tenemos un modelo conceptual de cola, permítanos definir sus operaciones. Como notarás, las operaciones de una cola son muy similares a una pila. La diferencia radica en dónde se eliminan los datos.

enqueue(data) agrega datos a una cola.
dequeue elimina los datos agregados más antiguos a una cola.

Implementación de una cola

¡Ahora escribamos el código para una cola!

Propiedades de una cola

Para nuestra implementación, crearemos un constructor llamado Queue. A continuación, agregaremos tres propiedades: _oldestIndex, _newestIndex y _storage. La necesidad de _oldestIndex y _newestIndex se volverá más clara en la siguiente sección.

function Queue() {
    this._oldestIndex = 1;
    this._newestIndex = 1;
    this._storage = {};
}

Métodos de una cola

Ahora crearemos los tres métodos compartidos entre todas las instancias de una cola: size(), enqueue(data) y dequeue(data). Esbozaré los objetivos para cada método, revelaré el código para cada método y luego explicaré el código para cada método.

Método 1 de 3: size()

Devuelve el tamaño correcto para una cola.

Devuelve el tamaño correcto para una cola.
Conserva el rango correcto de claves para una cola.

1	Queue.prototype.size = function() {
2	return this._newestIndex - this._oldestIndex;
3	};

Implementar size() puede parecer trivial, pero rápidamente descubrirás que no es cierto. Para entender por qué, debemos revisar rápidamente cómo se implementó el size (tamaño) para una pila.

Usando nuestro modelo conceptual de una pila, imaginemos que empujamos cinco placas en una pila. El tamaño de nuestra pila es de cinco y cada placa tiene un número asociado desde una (primera placa añadida) hasta cinco (la última placa añadida). Si removemos tres placas, entonces tenemos dos placas. Simplemente podemos restar tres de cinco para obtener el tamaño correcto, que es dos. Este es el punto más importante sobre el tamaño de una pila: el tamaño actual representa la clave correcta asociada con la placa en la parte superior de la pila (2) y la otra placa en la pila (1). En otras palabras, el rango de claves siempre es del tamaño actual a 1.

Ahora, apliquemos esta implementación del tamaño size de la pila a nuestra cola. Imagina que cinco clientes reciben un boleto de nuestro sistema de venta de entradas. El primer cliente tiene un boleto que muestra el número 1 y el quinto tiene un boleto que muestra el número 5. Con una cola, el cliente con el primer boleto se sirve primero.

Imaginemos ahora que se sirve el primer cliente y que este ticket se elimina de la cola. De forma similar a una pila, podemos obtener el tamaño correcto de nuestra cola restando 1 de 5. Nuestra fila tiene actualmente cuatro tickets no reservados. Ahora, aquí es donde surge un problema: el tamaño ya no representa los números de ticket correctos. Si simplemente restamos uno de cinco, tendríamos un tamaño de 4. No podemos usar 4 para determinar el rango actual de boletos restantes en la cola. ¿Tenemos entradas en la cola con los números del 1 al 4 o del 2 al 5? La respuesta no está clara.

Este es el beneficio de tener las siguientes dos propiedades en una cola: _oldestIndex y _newestIndex. Todo esto puede parecer confuso; todavía estoy confundido de vez en cuando. Lo que me ayuda a racionalizar todo es el siguiente ejemplo que he desarrollado.

Imagina que nuestra deli tiene dos sistemas de emisión de boletos:

_newestIndex representa un ticket de un sistema de ticketing de clientes.
_oldestIndex representa un ticket de un sistema de ticketing de empleados.

Este es el concepto más difícil de entender con respecto a tener dos sistemas de emisión de boletos: cuando los números en ambos sistemas son idénticos, todos los clientes en la fila se han direccionado y la cola está vacía. Usaremos el siguiente escenario para reforzar esta lógica:

Un cliente toma un boleto. El número de ticket del cliente, que se obtiene de _newestIndex, es 1. El próximo boleto disponible en el sistema de boleto del cliente es 2.
Un empleado no acepta un ticket y el ticket actual en el sistema de ticket de empleado es 1.
Tomamos el número de ticket actual en el sistema de cliente (2) y restamos el número en el sistema de empleado (1) para obtener el número 1. El número 1 representa el número de tickets que aún no se han eliminado en la cola.
El empleado toma un boleto de su sistema de emisión de boletos. Este boleto representa el boleto del cliente que se sirve. El ticket que se sirvió se recuperó de _oldestIndex, que muestra el número 1.
Repetimos el paso 4, y ahora la diferencia es cero: ¡no hay más boletos en la cola!

Ahora tenemos una propiedad (_newestIndex) que nos puede decir el número más grande (clave) asignado en la cola y una propiedad (_oldestIndex) que nos puede decir el número de índice más antiguo (clave) en la cola.

Hemos explorado adecuadamente el size(), así que ahora vamos a poner en cola los datos con enqueue(data).

Método 2 de 3: enqueue(data)

Para enqueue, tenemos dos objetivos:

Usa _newestIndex como clave de this._storage y usa cualquier dato que se agregue como valor de esa clave.
Incrementa el valor de _newestIndex por 1.

En función de estos dos objetivos, crearemos la siguiente implementación de enqueue(data):

1	Queue.prototype.enqueue = function(data) {
2	this._storage[this._newestIndex] = data;
3	this._newestIndex++;
4	};

El cuerpo de este método contiene dos líneas de código. En la primera línea, usamos this._newestIndex para crear una nueva clave para this._storage y asignarle data. this._newestIndex siempre comienza en 1. En la segunda línea de código, incrementamos this._newestIndex en 1, lo que actualiza su valor a 2.

Ese es todo el código que necesitamos para enqueue(data). Vamos a implementar dequeue().

Método 3 de 3: dequeue()

Estos son los objetivos de este método:

Elimina los datos más antiguos en una cola.
Incrementa _oldestIndex por uno.

Queue.prototype.dequeue = function() {
    var oldestIndex = this._oldestIndex,
        deletedData = this._storage[oldestIndex];

    delete this._storage[oldestIndex];
    this._oldestIndex++;

    return deletedData;
};

En el cuerpo de dequeue(), declaramos dos variables. La primera variable, oldestIndex, tiene asignado el valor actual de la cola para this._oldestIndex. A la segunda variable, deletedData, se le asigna el valor contenido en this._storage[oldestIndex].

A continuación, eliminamos el índice más antiguo en la cola. Después de eliminarlo, incrementamos this._oldestIndex en 1. Finalmente, devolvemos los datos que acabamos de eliminar.

Similar al problema en nuestra primera implementación de pop() con una pila, nuestra implementación de dequeue() no maneja situaciones donde se eliminan datos antes de que se agreguen datos. Necesitamos crear un condicional para manejar este caso de uso.

Queue.prototype.dequeue = function() {
    var oldestIndex = this._oldestIndex,
        newestIndex = this._newestIndex,
        deletedData;

    if (oldestIndex !== newestIndex) {
        deletedData = this._storage[oldestIndex];
        delete this._storage[oldestIndex];
        this._oldestIndex++;

        return deletedData;
    }
};

Cuando los valores de oldestIndex y newestIndex no son iguales, entonces ejecutamos la lógica que teníamos antes.

Implementación completa de una cola

Nuestra implementación de una cola está completa. Veamos todo el código.

function Queue() {
    this._oldestIndex = 1;
    this._newestIndex = 1;
    this._storage = {};
}

Queue.prototype.size = function() {
    return this._newestIndex - this._oldestIndex;
};

Queue.prototype.enqueue = function(data) {
    this._storage[this._newestIndex] = data;
    this._newestIndex++;
};

Queue.prototype.dequeue = function() {
    var oldestIndex = this._oldestIndex,
        newestIndex = this._newestIndex,
        deletedData;

    if (oldestIndex !== newestIndex) {
        deletedData = this._storage[oldestIndex];
        delete this._storage[oldestIndex];
        this._oldestIndex++;

        return deletedData;
    }
};

Conclusión

En este artículo, hemos explorado dos estructuras de datos lineales: pilas y colas. Una pila almacena datos en orden secuencial y elimina los datos agregados más recientemente; una cola almacena los datos en orden secuencial, pero elimina los datos agregados más antiguos.

Si la implementación de estas estructuras de datos parece trivial, recuerda el propósito de las estructuras de datos. No están diseñados para ser demasiado complicados; están diseñados para ayudarnos a organizar los datos. En este contexto, si te encuentras con datos que deben organizarse en orden secuencial, considera usar una pila o una cola.