23 Pregunta: ¿Cómo implementar una pila y una cola en JavaScript?

pregunta creada en Mon, Oct 19, 2009 12:00 AM

¿Cuál es la mejor manera de implementar una pila y una cola en JavaScript?

Estoy buscando hacer el algoritmo de derivación y voy a necesitar estas estructuras de datos.

    
641
23 Respuestas                              23                         
var stack = [];
stack.push(2);       // stack is now [2]
stack.push(5);       // stack is now [2, 5]
var i = stack.pop(); // stack is now [2]
alert(i);            // displays 5

var queue = [];
queue.push(2);         // queue is now [2]
queue.push(5);         // queue is now [2, 5]
var i = queue.shift(); // queue is now [5]
alert(i);              // displays 2

tomado de " 9 sugerencias de javascript que quizás no conozcas "

    
1170
2015-01-30 06: 10: 57Z
  1. Recomendaría precaución al usar queue.shift. IIRC no es O (1), pero O (n) y puede ser demasiado lento si la cola se hace grande.
    2009-10-19 18: 29: 01Z
  2. Diría que esto depende de la implementación de javascript. No creo que esté definido en la especificación de JavaScript.
    2009-10-19 19: 18: 12Z
  3. Consulte code.stephenmorley.org/javascript /queues para una implementación simple que mejora el rendimiento de la cola.
    2013-01-21 19: 24: 11Z
  4. Para problemas de rendimiento de la cola, vea una buena comparación de tres tipos diferentes de comportamientos de pila en jsperf.com/queue-push-unshift-vs-shift-pop - Ahora, si alguien fue lo suficientemente bueno como para incluir una velocidad de ese jsperf que contendría el script JS que @Gili mencionó ...
    2013-04-24 10: 13: 00Z
  5. Resucité la publicación del blog vinculada en esta respuesta, ya que archive.org no siempre es el más eficaz. Actualicé los enlaces y las imágenes para que funcionen, pero no cambié nada más.
    2013-09-19 21: 43: 19Z

Javascript tiene métodos push y pop, que operan en objetos ordinarios de matriz Javascript.

Para colas, mira aquí:

http://safalra.com/web-design/javascript/queues/

  

Las colas se pueden implementar en   JavaScript utilizando cualquiera de los pulsadores y   Métodos de cambio o sin cambios y pop.   Métodos del objeto array. A pesar de que   Esta es una forma simple de implementar.   colas, es muy ineficiente para   colas grandes - porque los métodos   operar en matrices, el cambio y   métodos de cambio mueven todos los elementos en   la matriz cada vez que se llaman.

     

Queue.js es una implementación de cola simple y eficiente para JavaScript cuya función de salida de cola se ejecuta en tiempo constante amortizado. Como resultado, para colas más grandes puede ser significativamente más rápido que usar arreglos.

    
78
2013-04-19 15: 32: 42Z
  1. + 1 para el enlace a la implementación de una cola de turnos retrasados ​​
    2009-10-19 21: 49: 44Z
  2. Con el enlace que usted compartió tenía la funcionalidad de verificar los resultados de referencia y amp; No veo mejoras de rendimiento cuando se prueba con Google Chromeversión 59. Queue.js es incosistente con su velocidad, pero Chrome era muy consistente con su velocidad.
    2017-07-12 06: 09: 31Z
  3. También hice una demostración con el queue.js, que, la función de dequeue realmente no elimina el elemento de la cola, así que me pregunto si se supone que es cómo ¿funciona? Si es así, ¿cómo puede recuperar la nueva cola después de sacar de la cola el elemento anterior? codepen.io/adamchenwei/pen/VxgNrX?editors=0001
    2018-05-21 13: 59: 45Z
  4. parece que la salida de cola en queue.js también requiere memoria adicional, ya que está clonando la matriz con un segmento.
    2018-06-13 03: 11: 56Z
  5. Además, la matriz subyacente es cada vez más grande con cada elemento agregado. Aunque la implementación reduce el tamaño de la matriz de vez en cuando, el tamaño global aumenta.
    2018-10-05 09: 29: 25Z

Arreglos.

Pila:

var stack = [];

//put value on top of stack
stack.push(1);

//remove value from top of stack
var value = stack.pop();

Cola:

var queue = [];

//put value on end of queue
queue.push(1);

//Take first value from queue
var value = queue.shift();
    
61
2009-10-19 18: 19: 21Z
  1. Array.prototype.pop no elimina el valor de la parte superior (primer elemento) del Array. Elimina el valor de la parte inferior (último elemento) de la matriz.
    2016-06-18 02: 50: 47Z
  2. @ MichaelGeller La parte superior de la pila es el elemento último de la matriz. Los métodos push y pop de la matriz se comportan como una pila.
    2016-10-13 19: 58: 42Z
  3. @ mrdommyg Array.prototype.pop elimina el elemento último de la matriz (consulte developer.mozilla.org/en/docs/Web/JavaScript/Reference/… ). Último en este contexto significa el elemento con el índice más alto. Una matriz en JS no tiene nada que ver con una pila. No es una pila solo porque tiene un método pop. Pop solo significa "quitar el último elemento y devolverlo". Por supuesto, puede imitar la funcionalidad de una pila con una matriz, pero una matriz aún no es una pila por definición. Todavía es una lista (un objeto de "lista similar" según MDN).
    2017-02-20 01: 03: 14Z
  4. @ MichaelGeller El comportamiento de una pila es "primero en entrar, último en salir". Si lo implementa utilizando un Array en JavaScript con sus métodos push y pop, entonces el problema se solucionó. Realmente no veo tu punto aquí.
    2017-07-27 06: 09: 51Z
  5. @ MichaelGeller Una pila es conceptual. Una matriz JS es (entre otras cosas), por definición, una pila en virtud de la implementación de la semántica de pila. Simplemente porque también implementa la semántica de matrices no cambia eso. Puedes usar una matriz JS como una pila fuera de la caja, y en ese contexto, lo que presionas y sacas es el elemento "superior".
    2017-07-27 17: 09: 43Z

Si quisiera crear sus propias estructuras de datos, podría crear las suyas propias:

var Stack = function(){
  this.top = null;
  this.size = 0;
};

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

Stack.prototype.push = function(data) {
  var node = new Node(data);

  node.previous = this.top;
  this.top = node;
  this.size += 1;
  return this.top;
};

Stack.prototype.pop = function() {
  temp = this.top;
  this.top = this.top.previous;
  this.size -= 1;
  return temp;
};

Y para la cola:

var Queue = function() {
  this.first = null;
  this.size = 0;
};

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

Queue.prototype.enqueue = function(data) {
  var node = new Node(data);

  if (!this.first){
    this.first = node;
  } else {
    n = this.first;
    while (n.next) {
      n = n.next;
    }
    n.next = node;
  }

  this.size += 1;
  return node;
};

Queue.prototype.dequeue = function() {
  temp = this.first;
  this.first = this.first.next;
  this.size -= 1;
  return temp;
};
    
29
2014-05-09 20: 13: 37Z
  1. Para evitar la necesidad de iterar sobre todo para agregar un final, almacene una referencia a la última a través de this.last = node;
    2015-04-17 04: 56: 49Z
  2. Nunca implementes una Cola como esta a menos que tengas una buena razón para ello ... aunque parezca lógicamente correcto, las CPU no funcionan de acuerdo con las abstracciones humanas. Iterar sobre una estructura de datos que tiene punteros en todo el lugar dará como resultado errores de caché en la CPU, a diferencia de una matriz secuencial que es altamente eficiente. blog.davidecoppola.com/2014/05 /… CPUs punteros HATE con una pasión ardiente: probablemente sean la causa número 1 de fallas de caché y tener que acceder a la memoria desde la RAM.
    2015-09-16 19: 51: 26Z
  3. esta es una solución tentadora, pero no veo que se eliminen los Nodes cuando se hacen estallar /sacar la cola ... ¿no se quedarán sentados alrededor de la memoria hasta el navegador? se bloquea?
    2016-02-29 11: 49: 57Z
  4. @ cneuro A diferencia de C ++, JavaScript es un lenguaje recolectado de basura. Tiene una palabra clave delete, pero solo es útil para marcar una propiedad de un objeto como no presente, lo cual es diferente de solo asignar undefined a la propiedad . JavaScript también tiene un operador new, pero solo se usa para establecer this en un nuevo objeto vacío al llamar a una función. En C ++ necesita emparejar cada new con un delete, pero no en JavaScript porque GC. Para dejar de usar la memoria en JavaScript, simplemente deje de hacer referencia al objeto y finalmente se reclamará.
    2016-12-06 15: 35: 43Z
  5. ¿No es también necesario verificar el desbordamiento de una pila al establecer un tamaño máximo de pila?
    2017-11-23 05: 47: 50Z

Mi implementación de Stack y Queue usando Lista vinculada

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

// Stack implemented using LinkedList
function Stack() {
  this.top = null;
}

Stack.prototype.push = function(data) {
  var newNode = new Node(data);

  newNode.next = this.top; //Special attention
  this.top = newNode;
}

Stack.prototype.pop = function() {
  if (this.top !== null) {
    var topItem = this.top.data;
    this.top = this.top.next;
    return topItem;
  }
  return null;
}

Stack.prototype.print = function() {
  var curr = this.top;
  while (curr) {
    console.log(curr.data);
    curr = curr.next;
  }
}

// var stack = new Stack();
// stack.push(3);
// stack.push(5);
// stack.push(7);
// stack.print();

// Queue implemented using LinkedList
function Queue() {
  this.head = null;
  this.tail = null;
}

Queue.prototype.enqueue = function(data) {
  var newNode = new Node(data);

  if (this.head === null) {
    this.head = newNode;
    this.tail = newNode;
  } else {
    this.tail.next = newNode;
    this.tail = newNode;
  }
}

Queue.prototype.dequeue = function() {
  var newNode;
  if (this.head !== null) {
    newNode = this.head.data;
    this.head = this.head.next;
  }
  return newNode;
}

Queue.prototype.print = function() {
  var curr = this.head;
  while (curr) {
    console.log(curr.data);
    curr = curr.next;
  }
}

var queue = new Queue();
queue.enqueue(3);
queue.enqueue(5);
queue.enqueue(7);
queue.print();
queue.dequeue();
queue.dequeue();
queue.print();
    
12
2015-07-13 14: 59: 33Z

El desplazamiento de la matriz de Javascript () es lento, especialmente cuando se tienen muchos elementos. Conozco dos formas de implementar la cola con complejidad O (1) amortizada.

Primero se usa el búfer circular y la duplicación de tablas. He implementado esto antes. Puedes ver mi código fuente aquí https://github.com/kevyuu/rapid-queue

La segunda forma es usando dos pilas. Este es el código para la cola con dos pilas

function createDoubleStackQueue() {
var that = {};
var pushContainer = [];
var popContainer = [];

function moveElementToPopContainer() {
    while (pushContainer.length !==0 ) {
        var element = pushContainer.pop();
        popContainer.push(element);
    }
}

that.push = function(element) {
    pushContainer.push(element);
};

that.shift = function() {
    if (popContainer.length === 0) {
        moveElementToPopContainer();
    }
    if (popContainer.length === 0) {
        return null;
    } else {
        return popContainer.pop();
    }
};

that.front = function() {
    if (popContainer.length === 0) {
        moveElementToPopContainer();
    }
    if (popContainer.length === 0) {
        return null;
    }
    return popContainer[popContainer.length - 1];
};

that.length = function() {
    return pushContainer.length + popContainer.length;
};

that.isEmpty = function() {
    return (pushContainer.length + popContainer.length) === 0;
};

return that;}

Esta es la comparación de rendimiento utilizando jsPerf

CircularQueue.shift () vs Array.shift ()

http://jsperf.com/rapidqueue-shift-vs-array-shift /a>

Como puede ver, es significativamente más rápido con un gran conjunto de datos

    
8
2015-05-03 14: 43: 04Z

Hay varias maneras de implementar Stacks y colas en Javascript. La mayoría de las respuestas anteriores son implementaciones bastante superficiales y trataría de implementar algo más legible (usando las nuevas características de sintaxis de es6) y robusto.

Aquí está la sImplementación de la tachuela:

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

    if(items.length>0)
      items.forEach(item => this._items.push(item) )

  }

  push(...items){
    //push item to the stack
     items.forEach(item => this._items.push(item) )
     return this._items;

  }

  pop(count=0){
    //pull out the topmost item (last item) from stack
    if(count===0)
      return this._items.pop()
     else
       return this._items.splice( -count, count )
  }

  peek(){
    // see what's the last item in stack
    return this._items[this._items.length-1]
  }

  size(){
    //no. of items in stack
    return this._items.length
  }

  isEmpty(){
    // return whether the stack is empty or not
    return this._items.length==0
  }

  toArray(){
    return this._items;
  }
}

Y así es como puedes usar la pila:

let my_stack = new Stack(1,24,4);
// [1, 24, 4]
my_stack.push(23)
//[1, 24, 4, 23]
my_stack.push(1,2,342);
//[1, 24, 4, 23, 1, 2, 342]
my_stack.pop();
//[1, 24, 4, 23, 1, 2]
my_stack.pop(3)
//[1, 24, 4]
my_stack.isEmpty()
// false
my_stack.size();
//3

Si desea ver la descripción detallada sobre esta implementación y cómo puede mejorarse, puede leer aquí: http://jschap.com/data-structures-in-javascript-stack/

Aquí está el código para la implementación de la cola en es6:

class Queue{
 constructor(...items){
   //initialize the items in queue
   this._items = []
   // enqueuing the items passed to the constructor
   this.enqueue(...items)
 }

  enqueue(...items){
    //push items into the queue
    items.forEach( item => this._items.push(item) )
    return this._items;
  }

  dequeue(count=1){
    //pull out the first item from the queue
    this._items.splice(0,count);
    return this._items;
  }

  peek(){
    //peek at the first item from the queue
    return this._items[0]
  }

  size(){
    //get the length of queue
    return this._items.length
  }

  isEmpty(){
    //find whether the queue is empty or no
    return this._items.length===0
  }
}

Aquí se explica cómo puede usar esta implementación:

let my_queue = new Queue(1,24,4);
// [1, 24, 4]
my_queue.enqueue(23)
//[1, 24, 4, 23]
my_queue.enqueue(1,2,342);
//[1, 24, 4, 23, 1, 2, 342]
my_queue.dequeue();
//[24, 4, 23, 1, 2, 342]
my_queue.dequeue(3)
//[1, 2, 342]
my_queue.isEmpty()
// false
my_queue.size();
//3

Para ver el tutorial completo sobre cómo se han implementado estas estructuras de datos y cómo se pueden mejorar aún más, es posible que desee revisar la serie "Jugar con estructuras de datos en javascript" en jschap.com. Aquí están los enlaces para colas: http://jschap.com/playing-data-structures- javascript-queues /

    
8
2018-03-13 17: 23: 50Z
/*------------------------------------------------------------------ 
 Defining Stack Operations using Closures in Javascript, privacy and
 state of stack operations are maintained

 @author:Arijt Basu
 Log: Sun Dec 27, 2015, 3:25PM
 ------------------------------------------------------------------- 
 */
var stackControl = true;
var stack = (function(array) {
        array = [];
        //--Define the max size of the stack
        var MAX_SIZE = 5;

        function isEmpty() {
            if (array.length < 1) console.log("Stack is empty");
        };
        isEmpty();

        return {

            push: function(ele) {
                if (array.length < MAX_SIZE) {
                    array.push(ele)
                    return array;
                } else {
                    console.log("Stack Overflow")
                }
            },
            pop: function() {
                if (array.length > 1) {
                    array.pop();
                    return array;
                } else {
                    console.log("Stack Underflow");
                }
            }

        }
    })()
    // var list = 5;
    // console.log(stack(list))
if (stackControl) {
    console.log(stack.pop());
    console.log(stack.push(3));
    console.log(stack.push(2));
    console.log(stack.pop());
    console.log(stack.push(1));
    console.log(stack.pop());
    console.log(stack.push(38));
    console.log(stack.push(22));
    console.log(stack.pop());
    console.log(stack.pop());
    console.log(stack.push(6));
    console.log(stack.pop());
}
//End of STACK Logic

/* Defining Queue operations*/

var queue = (function(array) {
    array = [];
    var reversearray;
    //--Define the max size of the stack
    var MAX_SIZE = 5;

    function isEmpty() {
        if (array.length < 1) console.log("Queue is empty");
    };
    isEmpty();

    return {
        insert: function(ele) {
            if (array.length < MAX_SIZE) {
                array.push(ele)
                reversearray = array.reverse();
                return reversearray;
            } else {
                console.log("Queue Overflow")
            }
        },
        delete: function() {
            if (array.length > 1) {
                //reversearray = array.reverse();
                array.pop();
                return array;
            } else {
                console.log("Queue Underflow");
            }
        }
    }



})()

console.log(queue.insert(5))
console.log(queue.insert(3))
console.log(queue.delete(3))
    
6
2015-12-27 21: 40: 35Z

O bien, puede utilizar dos matrices para implementar la estructura de datos de la cola.

var temp_stack = new Array();
var stack = new Array();

temp_stack.push(1);
temp_stack.push(2);
temp_stack.push(3);

Si hago estallar los elementos ahora, la salida será 3,2,1. Pero queremos una estructura FIFO para que pueda hacer lo siguiente.

stack.push(temp_stack.pop());
stack.push(temp_stack.pop());
stack.push(temp_stack.pop());

stack.pop(); //Pop out 1
stack.pop(); //Pop out 2
stack.pop(); //Pop out 3
    
5
2012-10-29 06: 09: 09Z
  1. Esto solo funciona si nunca push después de la primera vez que pop
    2017-09-22 04: 06: 39Z

Aquí hay una implementación de cola bastante simple con dos objetivos:

  • A diferencia de array.shift (), sabes que este método de salida de cola lleva tiempo constante (O (1)).
  • Para mejorar la velocidad, este enfoque utiliza muchas menos asignaciones que el enfoque de lista enlazada.

La implementación de la pila solo comparte el segundo objetivo.

// Queue
function Queue() {
        this.q = new Array(5);
        this.first = 0;
        this.size = 0;
}
Queue.prototype.enqueue = function(a) {
        var other;
        if (this.size == this.q.length) {
                other = new Array(this.size*2);
                for (var i = 0; i < this.size; i++) {
                        other[i] = this.q[(this.first+i)%this.size];
                }
                this.first = 0;
                this.q = other;
        }
        this.q[(this.first+this.size)%this.q.length] = a;
        this.size++;
};
Queue.prototype.dequeue = function() {
        if (this.size == 0) return undefined;
        this.size--;
        var ret = this.q[this.first];
        this.first = (this.first+1)%this.q.length;
        return ret;
};
Queue.prototype.peek = function() { return this.size > 0 ? this.q[this.first] : undefined; };
Queue.prototype.isEmpty = function() { return this.size == 0; };

// Stack
function Stack() {
        this.s = new Array(5);
        this.size = 0;
}
Stack.prototype.push = function(a) {
        var other;
    if (this.size == this.s.length) {
            other = new Array(this.s.length*2);
            for (var i = 0; i < this.s.length; i++) other[i] = this.s[i];
            this.s = other;
    }
    this.s[this.size++] = a;
};
Stack.prototype.pop = function() {
        if (this.size == 0) return undefined;
        return this.s[--this.size];
};
Stack.prototype.peek = function() { return this.size > 0 ? this.s[this.size-1] : undefined; };
    
5
2016-09-01 22: 05: 54Z

Puedes usar tu propia clase personalizada basada en el concepto, aquí el fragmento de código que puedes usar para hacer las cosas

/*
*   Stack implementation in JavaScript
*/

function Stack(){
    this.top = null;
    this.count = 0;

    this.getCount = function(){
        return this.count;
    }

    this.getTop = function(){
        return this.top;
    }

    this.push = function(data){
        var node = {
            data : data,
            next : null
        }

        node.next = this.top;
        this.top = node;

        this.count++;
    }

    this.peek = function(){
        if(this.top === null){
            return null;
        }else{
            return this.top.data;
        }
    }

    this.pop = function(){
        if(this.top === null){
            return null;
        }else{
            var out = this.top;
            this.top = this.top.next;
            if(this.count>0){
                this.count--;
            }

            return out.data;
        }
    }

    this.displayAll = function(){
        if(this.top === null){
            return null;
        }else{
            var arr = new Array();

            var current = this.top;
            //console.log(current);
            for(var i = 0;i<this.count;i++){
                arr[i] = current.data;
                current = current.next;
            }

            return arr;
        }
    }
}

y para verificar esto, use su consola y pruebe estas líneas una por una.

>> var st = new Stack();

>> st.push("BP");

>> st.push("NK");

>> st.getTop();

>> st.getCount();

>> st.displayAll();

>> st.pop();

>> st.displayAll();

>> st.getTop();

>> st.peek();
    
4
2017-03-24 06: 20: 42Z
  1. Votar hacia abajo para una convención de nomenclatura: método que comienza con un capital que se supone que es un constructor.
    2014-12-29 18: 25: 58Z

Si entiendes las pilas con las funciones push () y pop (), la cola es solo para hacer una de estas operaciones en el sentido opuesto. Oposite of push () es unshift () y oposite de pop () es shift (). Entonces:

//classic stack
var stack = [];
stack.push("first"); // push inserts at the end
stack.push("second");
stack.push("last");
stack.pop(); //pop takes the "last" element

//One way to implement queue is to insert elements in the oposite sense than a stack
var queue = [];
queue.unshift("first"); //unshift inserts at the beginning
queue.unshift("second");
queue.unshift("last");
queue.pop(); //"first"

//other way to do queues is to take the elements in the oposite sense than stack
var queue = [];
queue.push("first"); //push, as in the stack inserts at the end
queue.push("second");
queue.push("last");
queue.shift(); //but shift takes the "first" element
    
3
2014-04-26 20: 07: 21Z

Aquí está la versión de la lista enlazada de una cola que también incluye el último nodo, como lo sugiere @perkins y según sea más apropiado.

// QUEUE Object Definition

var Queue = function() {
  this.first = null;
  this.last = null;
  this.size = 0;
};

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

Queue.prototype.enqueue = function(data) {
  var node = new Node(data);

  if (!this.first){ // for empty list first and last are the same
    this.first = node;
    this.last = node;
  } else { // otherwise we stick it on the end
    this.last.next=node;
    this.last=node;
  }

  this.size += 1;
  return node;
};

Queue.prototype.dequeue = function() {
  if (!this.first) //check for empty list
    return null;

  temp = this.first; // grab top of list
  if (this.first==this.last) {
    this.last=null;  // when we need to pop the last one
  }
  this.first = this.first.next; // move top of list down
  this.size -= 1;
  return temp;
};
    
3
2016-09-06 18: 44: 35Z
  1. En la salida, debe devolver temp.data en su lugar. Porque eso es lo que se puso en cola.
    2017-10-28 18: 08: 52Z

Sin matriz (s)

//Javascript stack linked list data structure (no array)

function node(value, noderef) {
    this.value = value;
    this.next = noderef;
}
function stack() {
    this.push = function (value) {
        this.next = this.first;
        this.first = new node(value, this.next);
    }
    this.pop = function () {
        var popvalue = this.first.value;
        this.first = this.first.next;
        return popvalue;
    }
    this.hasnext = function () {
        return this.next != undefined;
    }
    this.isempty = function () {
        return this.first == undefined;
    }

}

//Javascript stack linked list data structure (no array)
function node(value, noderef) {
    this.value = value;
    this.next = undefined;
}
function queue() {
    this.enqueue = function (value) {
        this.oldlast = this.last;
        this.last = new node(value);
        if (this.isempty())
            this.first = this.last;
        else 
           this.oldlast.next = this.last;
    }
    this.dequeue = function () {
        var queuvalue = this.first.value;
        this.first = this.first.next;
        return queuvalue;
    }
    this.hasnext = function () {
        return this.first.next != undefined;
    }
    this.isempty = function () {
        return this.first == undefined;
    }

}
    
2
2014-02-09 02: 06: 12Z
  1. ¿Cómo puedo ejecutar una función interna dada como un push pop?
    2018-12-15 12: 03: 53Z

La implementación de la pila es trivial como se explica en las otras respuestas.

Sin embargo, no encontré ninguna respuesta satisfactoria en este hilo para implementar una cola en JavaScript, así que hice mi propia cuenta.

Hay tres tipos de soluciones en este hilo:

  • Arrays: la peor solución, usar array.shift() en un array grande es muy ineficiente
  • Listas enlazadas: es O (1) pero usar un objeto para cada elemento es un poco excesivo, especialmente si hay muchos de ellos y son pequeños, como almacenar números
  • Arrays de turnos retrasados: consiste en asociar un índice con la matriz. Cuando un elemento es eliminado, el índice avanza. Cuando el índice llega a la mitad de la matriz, la matriz se divide en dos para eliminar la primera mitad.

Las matrices de turnos retrasados ​​son la solución más satisfactoria en mi mente, pero aún así almacenan todo en una gran matriz contigua que puede ser problemática, y la aplicación se tambaleará cuando la matriz se divida.

Hice una implementación utilizando una lista enlazada de arreglos pequeños (1000 elementos como máximo cada uno). Las matrices se comportan como matrices de desplazamiento retardado, excepto que nunca se cortan en rodajas: cuando se elimina cada elemento de la matriz, la matriz simplemente se descarta.

El paquete es en npm con funcionalidad básica FIFO, lo empujé recientemente . El código se divide en dos partes.

Aquí está la primera parte

/** Queue contains a linked list of Subqueue */
class Subqueue <T> {
  public full() {
    return this.array.length >= 1000;
  }

  public get size() {
    return this.array.length - this.index;
  }

  public peek(): T {
    return this.array[this.index];
  }

  public last(): T {
    return this.array[this.array.length-1];
  }

  public dequeue(): T {
    return this.array[this.index++];
  }

  public enqueue(elem: T) {
    this.array.push(elem);
  }

  private index: number = 0;
  private array: T [] = [];

  public next: Subqueue<T> = null;
}

Y aquí está la clase principal Queue:

class Queue<T> {
  get length() {
    return this._size;
  }

  public push(...elems: T[]) {
    for (let elem of elems) {
      if (this.bottom.full()) {
        this.bottom = this.bottom.next = new Subqueue<T>();
      }
      this.bottom.enqueue(elem);
    }

    this._size += elems.length;
  }

  public shift(): T {
    if (this._size === 0) {
      return undefined;
    }

    const val = this.top.dequeue();
    this._size--;
    if (this._size > 0 && this.top.size === 0 && this.top.full()) {
      // Discard current subqueue and point top to the one after
      this.top = this.top.next;
    }
    return val;
  }

  public peek(): T {
    return this.top.peek();
  }

  public last(): T {
    return this.bottom.last();
  }

  public clear() {
    this.bottom = this.top = new Subqueue();
    this._size = 0;
  }

  private top: Subqueue<T> = new Subqueue();
  private bottom: Subqueue<T> = this.top;
  private _size: number = 0;
}

Las anotaciones de tipo (: X) se pueden eliminar fácilmente para obtener el código javascript de ES6.

    
2
2018-04-18 14: 40: 59Z

La estructura regular de Array en Javascript es una pila (primero en entrar, última en salir) y también se puede usar como una cola (primero en entrar, primero en salir) dependiendo de las llamadas que realice.

Marque este enlace para ver cómo hacer que un Array actúe como una Cola:

Colas

    
2
2018-09-29 05: 58: 13Z

Si está buscando la implementación ESO OOP de la estructura de datos de la pila y la cola con algunas operaciones básicas (basadas en listas vinculadas), puede que tenga este aspecto:

Queue.js

import LinkedList from '../linked-list/LinkedList';

export default class Queue {
  constructor() {
    this.linkedList = new LinkedList();
  }

  isEmpty() {
    return !this.linkedList.tail;
  }

  peek() {
    if (!this.linkedList.head) {
      return null;
    }

    return this.linkedList.head.value;
  }

  enqueue(value) {
    this.linkedList.append(value);
  }

  dequeue() {
    const removedHead = this.linkedList.deleteHead();
    return removedHead ? removedHead.value : null;
  }

  toString(callback) {
    return this.linkedList.toString(callback);
  }
}

Stack.js

import LinkedList from '../linked-list/LinkedList';

export default class Stack {
  constructor() {
    this.linkedList = new LinkedList();
  }

  /**
   * @return {boolean}
   */
  isEmpty() {
    return !this.linkedList.tail;
  }

  /**
   * @return {*}
   */
  peek() {
    if (!this.linkedList.tail) {
      return null;
    }

    return this.linkedList.tail.value;
  }

  /**
   * @param {*} value
   */
  push(value) {
    this.linkedList.append(value);
  }

  /**
   * @return {*}
   */
  pop() {
    const removedTail = this.linkedList.deleteTail();
    return removedTail ? removedTail.value : null;
  }

  /**
   * @return {*[]}
   */
  toArray() {
    return this.linkedList
      .toArray()
      .map(linkedListNode => linkedListNode.value)
      .reverse();
  }

  /**
   * @param {function} [callback]
   * @return {string}
   */
  toString(callback) {
    return this.linkedList.toString(callback);
  }
}

Y se puede encontrar la implementación de LinkedList que se usa para la pila y la cola en los ejemplos anteriores en GitHub aquí .

    
2
2019-01-04 20: 29: 18Z
  var x = 10; 
  var y = 11; 
  var Queue = new Array();
  Queue.unshift(x);
  Queue.unshift(y);

  console.log(Queue)
  // Output [11, 10]

  Queue.pop()
  console.log(Queue)
  // Output [11]
    
1
2017-09-27 05: 58: 49Z

Saludos,

En Javascript, la implementación de pilas y colas es la siguiente:

Pila: Una pila es un contenedor de objetos que se insertan y eliminan de acuerdo con el principio de último en entrar, primero en salir (LIFO).

  • Push: El método agrega uno o más elementos al final de una matriz y devuelve la nueva longitud de la matriz.
  • Pop: el método elimina el último elemento de una matriz y devuelve ese elemento.

Cola: Una cola es un contenedor de objetos (una colección lineal) que se inserta y elimina de acuerdo con el principio de primero en entrar, primero en salir (FIFO).

  • Unshift: el método agrega uno o más elementos al principio de una matriz.

  • Shift: el método elimina el primer elemento de una matriz.

let stack = [];
 stack.push(1);//[1]
 stack.push(2);//[1,2]
 stack.push(3);//[1,2,3]
 
console.log('It was inserted 1,2,3 in stack:', ...stack);

stack.pop(); //[1,2]
console.log('Item 3 was removed:', ...stack);

stack.pop(); //[1]
console.log('Item 2 was removed:', ...stack);


let queue = [];
queue.push(1);//[1]
queue.push(2);//[1,2]
queue.push(3);//[1,2,3]

console.log('It was inserted 1,2,3 in queue:', ...queue);

queue.shift();// [2,3]
console.log('Item 1 was removed:', ...queue);

queue.shift();// [3]
console.log('Item 2 was removed:', ...queue);
    
1
2018-12-20 16: 40: 05Z

Cree un par de clases que proporcionen los diversos métodos que tiene cada una de estas estructuras de datos (push, pop, peek, etc.). Ahora implementa los métodos. Si está familiarizado con los conceptos detrás de la pila /cola, esto debería ser bastante sencillo. Puede implementar la pila con una matriz y una cola con una lista vinculada, aunque ciertamente hay otras formas de hacerlo. Javascript lo hará fácil, porque está mal escrito, por lo que ni siquiera tiene que preocuparse por los tipos genéricos, lo que tendría que hacer si lo estuviera implementando en Java o C #.

    
0
2009-10-19 18: 23: 45Z

Aquí está mi implementación de pilas.

function Stack() {
this.dataStore = [];
this.top = 0;
this.push = push;
this.pop = pop;
this.peek = peek;
this.clear = clear;
this.length = length;
}
function push(element) {
this.dataStore[this.top++] = element;
}
function peek() {
return this.dataStore[this.top-1];
}
function pop() {
return this.dataStore[--this.top];
}
function clear() {
this.top = 0;
}
function length() {
return this.top;
}

var s = new Stack();
s.push("David");
s.push("Raymond");
s.push("Bryan");
console.log("length: " + s.length());
console.log(s.peek());
    
0
2018-02-16 07: 47: 39Z

Me parece que la matriz integrada está bien para una pila. Si desea una Cola en TypeScript, aquí hay una implementación

/**
 * A Typescript implementation of a queue.
 */
export default class Queue {

  private queue = [];
  private offset = 0;

  constructor(array = []) {
    // Init the queue using the contents of the array
    for (const item of array) {
      this.enqueue(item);
    }
  }

  /**
   * @returns {number} the length of the queue.
   */
  public getLength(): number {
    return (this.queue.length - this.offset);
  }

  /**
   * @returns {boolean} true if the queue is empty, and false otherwise.
   */
  public isEmpty(): boolean {
    return (this.queue.length === 0);
  }

  /**
   * Enqueues the specified item.
   *
   * @param item - the item to enqueue
   */
  public enqueue(item) {
    this.queue.push(item);
  }

  /**
   *  Dequeues an item and returns it. If the queue is empty, the value
   * {@code null} is returned.
   *
   * @returns {any}
   */
  public dequeue(): any {
    // if the queue is empty, return immediately
    if (this.queue.length === 0) {
      return null;
    }

    // store the item at the front of the queue
    const item = this.queue[this.offset];

    // increment the offset and remove the free space if necessary
    if (++this.offset * 2 >= this.queue.length) {
      this.queue = this.queue.slice(this.offset);
      this.offset = 0;
    }

    // return the dequeued item
    return item;
  };

  /**
   * Returns the item at the front of the queue (without dequeuing it).
   * If the queue is empty then {@code null} is returned.
   *
   * @returns {any}
   */
  public peek(): any {
    return (this.queue.length > 0 ? this.queue[this.offset] : null);
  }

}

Y aquí hay una prueba Jest para ella

it('Queue', () => {
  const queue = new Queue();
  expect(queue.getLength()).toBe(0);
  expect(queue.peek()).toBeNull();
  expect(queue.dequeue()).toBeNull();

  queue.enqueue(1);
  expect(queue.getLength()).toBe(1);
  queue.enqueue(2);
  expect(queue.getLength()).toBe(2);
  queue.enqueue(3);
  expect(queue.getLength()).toBe(3);

  expect(queue.peek()).toBe(1);
  expect(queue.getLength()).toBe(3);
  expect(queue.dequeue()).toBe(1);
  expect(queue.getLength()).toBe(2);

  expect(queue.peek()).toBe(2);
  expect(queue.getLength()).toBe(2);
  expect(queue.dequeue()).toBe(2);
  expect(queue.getLength()).toBe(1);

  expect(queue.peek()).toBe(3);
  expect(queue.getLength()).toBe(1);
  expect(queue.dequeue()).toBe(3);
  expect(queue.getLength()).toBe(0);

  expect(queue.peek()).toBeNull();
  expect(queue.dequeue()).toBeNull();
});

Espero que alguien encuentre esto útil,

Saludos,

Stu

    
0
2018-04-04 10: 11: 42Z

puede usar WeakMaps para implementar propiedad privada en la clase ES6 y los beneficios de las propiedades y métodos de String en el lenguaje JavaScript como a continuación:

const _items = new WeakMap();

class Stack {
  constructor() {
    _items.set(this, []);
  }

push(obj) {
  _items.get(this).push(obj);
}

pop() {
  const L = _items.get(this).length;
  if(L===0)
    throw new Error('Stack is empty');
  return _items.get(this).pop();
}

peek() {
  const items = _items.get(this);
  if(items.length === 0)
    throw new Error ('Stack is empty');
  return items[items.length-1];
}

get count() {
  return _items.get(this).length;
}
}

const stack = new Stack();

//now in console:
//stack.push('a')
//stack.push(1)
//stack.count   => 2
//stack.peek()  => 1
//stack.pop()   => 1
//stack.pop()   => "a"
//stack.count   => 0
//stack.pop()   => Error Stack is empty
    
0
2019-01-22 10: 32: 20Z
fuente colocada aquí