Implementación pila de manera eficiente.

[Pantaláimon]

Buenas,

Según tengo entendido, los arrays en javascript tienen implementados los siguientos métodos con la siguiente complejidad algorítmica.

Código Javascript:

push // O(1)
pop // O(1)
shift // O(n) pues al quitar el primer elemento hay que desplazar el resto de elementos
unshift // O(n) pues al insertar un elemento en la primera posición hay que desplazar el resto
 

Esto hace que se pueda implementar una pila de manera eficiente usando push i pop pero no se pueda implementar un cola de manera eficiente usando las combinaciones unshift-pop o push-shift.

Entonces la manera que se me ha ocurrido de implementar una cola es mediante los objetos de javascript, que al ser hashes tanto la inserción como el borrado tienen un coste constante O(1). Por ejemplo:

Código Javascript:

function Queue (){
   this.elements = {}
   this.begin = 0;
   this.end = -1;
}
 
Queue.prototype.enqueue = function (element) {
   this.end++;
   this.elements[this.end] = element;
   
}
 
Queue.prototype.dequeue = function () {
   var value = this.elements[this.begin];
   if (this.begin === this.end) {
      Queue.call(this); // si la cola tiene 1 elemento dejarla vacía y resetear indices begin y end
   } else if (this.begin < this.end) {
      delete this.elements[this.begin];
      this.begin++;
   }
   return value;
}
 

¿Tiene algún inconveniente? ¿Hay mejores maneras de implementar colas en javascript?

Un saludo y gracias.

[Panino5001]

A mi me gustó mucho esta implementación de Aijoona: http://blog.aijoona.com/2011/04/30/i...en-javascript/

[Pantaláimon]

A mi no me gustó por lo que ya expliqué en mi primer post:

Iniciado por Aijoona

// Obtenemos la primer tarea activa
task = this._tasks.shift();

Si hay muchas tareas en la cola la operación shift tiene un coste demasiado elevado. Quizá para una cola de ejecución eso no pase habitualmente, no lo sé. Pero yo no quiero implementar una cola de ejecución.

[Panino5001]

Habría que hacer los tests correspondientes en varios navegadores. Al parecer algunos lo han hecho y comentan resultados diferentes de los tuyos: http://stackoverflow.com/questions/8...ally-for-googl
Yo no hice nunca los tests, pero recuerdo en viejas versiones de jQuery (las nuevas no las reviso hace mucho) que implementaban las colas con shift, y como es una comunidad muy grande seguro que han evaluado este tema.
De todas maneras, tu planteo me resulta interesante

[marlanga]

Puedes usar push() y un array para añadir. "end" no lo necesitas, un simple this,length que no sea cero te servirá para saber si el array está vacío o no (aunque devuelva un tamaño no creíble). Es también O(1) porque internamente el objeto Array mantiene el atributo length con el índice numérico más grande que exista en el array + 1, que va actualizando en memoria cada vez que se inserta o elimina un elemento, como también hace PHP.

En cuanto a al eficiencia, con javascript nada es lo que parece. Me he llevado muchos palos por hacer suposiciones.

Y ya que estamos con la eficiencia, un this(); es más rápido que un Queue.call(this).

Código Javascript:

function Queue (){
   this.elements = []
   this.begin = 0;
}
 
Queue.prototype.enqueue = function (element) {
   this.elements.push(element);
   
}
 
Queue.prototype.dequeue = function () {
   var value = this.elements[this.begin];
   if (!this.elements.length) {
      this(); // si la cola tiene 1 elemento dejarla vacía y resetear indices begin y end
   } else if (this.elements.hasOwnProperty(this.begin)) {
      delete this.elements[this.begin++];
   }
   return value;
}
 

El hasOwnProperty hace lo que parece.