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

741

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

Estoy buscando hacer el algoritmo del patio de maniobras y voy a necesitar estas estructuras de datos.

ReyNestor
fuente

Respuestas:

1347
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 consejos de JavaScript que quizás no conozcas "

Corey Ballou
fuente
218
Aconsejaría precaución al usar queue.shift. IIRC no es O (1), sino O (n) y podría ser demasiado lento si la cola se agranda.
MAK
20
Yo diría que esto depende de la implementación de JavaScript. No creo que esté definido en la especificación de JavaScript.
Georg Schölly
99
Vea code.stephenmorley.org/javascript/queues para una implementación simple que mejora el rendimiento de la cola.
Gili
15
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 solo alguien fuera lo suficientemente amable como para incluir una revolución de ese jsperf, eso sería contiene el script JS que @Gili mencionó ...
Nenotlep
3
Resucité la publicación del blog vinculada en esta respuesta, ya que archive.org no siempre es el más eficiente. Actualicé enlaces e imágenes para que funcionen, pero no cambié nada más.
Chev
87

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

Para colas, mira aquí:

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

Las colas se pueden implementar en JavaScript utilizando los métodos push y shift o los métodos unshift y pop del objeto de matriz. Aunque esta es una manera simple de implementar colas, es muy ineficiente para las colas grandes: debido a que los métodos operan en matrices, los métodos shift y unshift mueven cada elemento de la matriz cada vez que se los llama.

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

Robert Harvey
fuente
2
Con el enlace que compartió tenía la funcionalidad de verificar los resultados de referencia y no veo ganancias de rendimiento cuando se prueba con Google Chrome versión 59. Queue.js es incosistente con su velocidad, pero Chrome fue bastante consistente con su velocidad.
Shiljo Paulson
También hice una demostración con queue.js, que, la función de eliminación de cola realmente no elimina el elemento de la cola, por lo que me pregunto si se supone que es así como funciona. Si es así, ¿cómo puede recuperar la nueva cola después de quitar el elemento anterior? codepen.io/adamchenwei/pen/VxgNrX?editors=0001
Ezeewei
parece que el dequeue en queue.js también requiere memoria adicional ya que está clonando la matriz con una división.
JaTo
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 general aumenta.
Philipp Mitterer
73

Arreglos

Apilar:

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();
Jani Hartikainen
fuente
1
Array.prototype.pop no elimina el valor de la parte superior (primer elemento) de la matriz. Elimina el valor de la parte inferior (último elemento) de la matriz.
Michael Geller
21
@MichaelGeller La parte superior de la pila es el último elemento de la matriz. Los métodos push y pop de matriz se comportan como una pila.
mrdommyg
@mrdommyg Array.prototype.pop elimina el último elemento 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 "eliminar el último elemento y devolverlo". Por supuesto, puede imitar la funcionalidad de una pila con una matriz, pero una matriz todavía no es una pila por definición. Sigue siendo una lista (un objeto de "lista como" según MDN).
Michael Geller
55
@MichaelGeller El comportamiento de una pila es "primero en entrar, último en salir". Si lo implementa utilizando una matriz en JavaScript con sus métodos pushy pop, entonces el problema está resuelto. Realmente no veo tu punto aquí.
Rax Weber
2
@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 la pila. El hecho de que también implemente la semántica de matrices no cambia eso. Puede usar una matriz JS como una pila fuera de la caja, y en ese contexto lo que empuja y hace estallar es el elemento "superior".
Hans
32

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 hacer 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;
};
usuario2954463
fuente
13
Para evitar la necesidad de iterar sobre todo para poder agregar al final, almacene una referencia al último a través de this.last = node;
Perkins
99
Nunca implemente una Cola como esta a menos que tenga una buena razón para ello ... si bien puede parecer lógicamente correcto, las CPU no funcionan de acuerdo con las abstracciones humanas. La iteración sobre una estructura de datos que tiene punteros por todas partes dará como resultado errores de caché en la CPU, a diferencia de una matriz secuencial que es altamente eficiente. blog.davidecoppola.com/2014/05/… Los CPUs ODIAN los punteros con una pasión ardiente: probablemente sean la causa número 1 de errores de caché y de tener que acceder a la memoria desde la RAM.
Centril
1
esta es una solución tentadora, pero no veo que Nodese eliminen las creaciones cuando aparecen / desaparecen ... ¿no se quedarán sentadas acumulando memoria hasta que el navegador se bloquee?
cneuro
55
@cneuro A diferencia de C ++, JavaScript es un lenguaje de recolección de basura. Tiene una deletepalabra clave, pero eso solo es útil para marcar una propiedad de un objeto como no presente, que es diferente de simplemente asignarla undefineda la propiedad . JavaScript también tiene un newoperador, pero solo se usa para establecer thisun nuevo objeto vacío cuando se llama a una función. En C ++ necesita emparejar cada uno newcon a delete, pero no en JavaScript porque GC. Para dejar de usar memoria en JavaScript, simplemente deje de hacer referencia al objeto y eventualmente será reclamado.
binki
¿No es también necesario verificar el desbordamiento de una pila configurando un tamaño máximo de pila?
abeja
16

Mi implementación Stacky QueueusoLinked List

// 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();

Rohit
fuente
10

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

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

La segunda forma es mediante el uso de 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 usando jsPerf

CircularQueue.shift () vs Array.shift ()

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

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

kevinyu
fuente
8

Hay bastantes maneras en que puede implementar pilas 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 nuevas características de sintaxis de es6) y robusto.

Aquí está la implementación de la pila:

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 se puede mejorar aún más, 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í le mostramos 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 de cómo se han implementado estas estructuras de datos y cómo se pueden mejorar aún más, puede consultar 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/

Anish K.
fuente
7

Puede usar su propia clase de personalización basada en el concepto, aquí el fragmento de código que puede 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();
jforjs
fuente
2
Voto a favor de una convención de nomenclatura: método que comienza con una mayúscula que se supone que es un constructor.
Pavlo
6
/*------------------------------------------------------------------ 
 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))
Arijit Basu
fuente
5

O bien, puede usar 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
Ni3
fuente
1
Esto solo funciona si nunca pushdespués de la primera vez quepop
jnnnnn
5

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

  • A diferencia de array.shift (), sabe que este método de eliminación de la cola tarda un tiempo constante (O (1)).
  • Para mejorar la velocidad, este enfoque utiliza muchas menos asignaciones que el enfoque de la lista vinculada.

La implementación de la pila comparte solo 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; };
snydergd
fuente
5

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 la mía.

Hay tres tipos de soluciones en este hilo:

  • Matrices: la peor solución, usar array.shift()una matriz grande es muy ineficiente.
  • Listas vinculadas: 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.
  • Matrices de turnos demorados: consiste en asociar un índice con la matriz. Cuando se quita un elemento, el índice avanza. Cuando el índice alcanza el centro de la matriz, la matriz se divide en dos para eliminar la primera mitad.

En mi opinión, las matrices de turnos diferidos son la solución más satisfactoria, pero aún almacenan todo en una matriz contigua grande que puede ser problemática, y la aplicación se tambaleará cuando la matriz se corte.

Hice una implementación usando listas vinculadas de pequeñas matrices (1000 elementos como máximo cada una). Las matrices se comportan como matrices de desplazamiento retardado, excepto que nunca se cortan: cuando se eliminan todos los elementos de la matriz, la matriz simplemente se descarta.

El paquete está en npm con la funcionalidad básica FIFO, lo acabo de recientemente. El código se divide en dos partes.

Aqui esta 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 Queueclase principal :

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 ES6.

coyotte508
fuente
4

Si comprende las pilas con las funciones push () y pop (), entonces la cola es solo para realizar una de estas operaciones en sentido contrario. El lado opuesto de push () es unshift () y opuesto a 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
Javier Giovannini
fuente
Una advertencia para quienes escriben software crítico para el rendimiento. El .shift()método no es una implementación de cola adecuada. Es O (n) en lugar de O (1), y será lento para colas grandes.
Rudi Kershaw
3

Aquí está la versión de la lista vinculada de una cola que también incluye el último nodo, según lo sugerido por @perkins y lo 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;
};
DrByrd
fuente
En la cola, debe devolver temp.data en su lugar. Porque eso es lo que estaba en la cola.
no es un robot
3

Si está buscando la implementación ESOP OOP de la estructura de datos Stack and Queue con algunas operaciones básicas (basadas en listas vinculadas), entonces puede verse así:

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 la implementación de LinkedList que se usa para Stack y Queue en los ejemplos anteriores se puede encontrar en GitHub aquí .

Oleksii Trekhleb
fuente
2

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;
    }

}
Andriy
fuente
¿Cómo puedo ejecutar una función interna dada como push pop?
Chandan Kumar
2

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

Consulte este enlace para ver cómo hacer que una matriz actúe como una cola:

Colas

Justin Niessner
fuente
2

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: Method agrega uno o más elementos al final de una matriz y devuelve la nueva longitud de la matriz.
  • Pop: Method 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 insertan y eliminan de acuerdo con el principio de primero en entrar, primero en salir (FIFO).

  • Unshift: Method agrega uno o más elementos al comienzo 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);

Daniel Barrientos
fuente
1
  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]
Rajesh Kumar
fuente
1

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 Jestprueba para ello

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,

Salud,

Stu

Stuart Clark
fuente
0

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 implemente los métodos. Si está familiarizado con los conceptos detrás de stack / queue, 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 facilitará esto, porque está tipado débilmente, por lo que ni siquiera tiene que preocuparse por los tipos genéricos, lo que tendría que hacer si lo implementara en Java o C #.

eco
fuente
0

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());
Hitesh Joshi
fuente
0

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 se muestra 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
Salar
fuente
0

Construya una cola usando dos pilas.

O (1) para operaciones en cola y en cola.

class Queue {
  constructor() {
    this.s1 = []; // in
    this.s2 = []; // out
  }

  enqueue(val) {
    this.s1.push(val);
  }

  dequeue() {
    if (this.s2.length === 0) {
      this._move();
    }

    return this.s2.pop(); // return undefined if empty
  }

  _move() {
    while (this.s1.length) {
      this.s2.push(this.s1.pop());
    }
  }
}
Yuki-Dreamer
fuente