Cómo implementar una pila en JavaScript vanilla y ES6

Una pila es una colección ordenada de elementos que siguen el principio de último en entrar, primero en salir (LIFO). La adición y eliminación de elementos se realiza en el mismo extremo, es decir, en la parte superior. Los elementos más nuevos están en la parte superior y los elementos más antiguos están en la parte inferior.

Tenemos muchos ejemplos de pilas a nuestro alrededor, como una pila de libros, una pila de bandejas o platos, etc.

Los compiladores utilizan una pila en lenguajes de programación, en la memoria de la computadora para almacenar variables y llamadas a funciones, y en editores de texto para realizar operaciones de deshacer y rehacer.

Lista de operaciones realizadas en Stack

  • push () : agrega uno o varios elementos a la parte superior de la pila.
  • pop () : elimina y devuelve el elemento superior de la pila.
  • peek () : devuelve el elemento superior de la pila.
  • isEmpty () : Devuelve Truesi la pila está vacía, de lo Falsecontrario.
  • clear () : elimina todos los elementos de la pila.
  • size () : Devuelve la longitud de la pila.

Crear una pila

Un enfoque clásico

Vamos a implementar una pila como se implementa en otros lenguajes además de JavaScript.

Usaremos una matriz y una variable adicional para realizar un seguimiento de los elementos.

function Stack(){ var items = []; var top = 0; //other methods go here }

Empuje un elemento en la pila

//Push an item in the Stackthis.push = function(element){ items[top++] = element } //top++, first performs the operation then increment's the value

Sacar un artículo de la pila

//Pop an item from the Stackthis.pop = function(){ return items[--top]; } //--top, first decrements the value then performs the operation

Echa un vistazo al artículo superior de la pila

//peek an item in the Stackthis.peek = function(){ return items[top - 1]; }

Compruebe si la pila está vacía

//Is stack emptythis.isEmpty = function(){ return top === 0; }

Limpiar la pila

//clear the stackthis.clear= function(){ top = 0; }

Tamaño de la pila

//Size of the Stackthis.size = function(){ return top; }

Implementación completa de la pila

function Stack(){ var items = []; var top = 0; //other methods go here 
 //Push an item in the Stack this.push = function(element){ items[top++] = element } //top++, first performs the operation then increment's the value 
 //Pop an item from the Stack this.pop = function(){ return items[--top]; } //--top, first decrements the value then performs the operation 
 //Peek top item of the Stack this.peek = function(){ return items[top - 1]; } 
 //Is Stack empty this.isEmpty = function(){ return top === 0; } 
 //Clear the Stack this.clear = function(){ top = 0; } 
 //Size of the Stack this.size = function(){ return top; }
}

Ejemplo

Ahora crearemos una nueva instancia de lo que hemos implementado y comprobaremos si está funcionando correctamente.

var stack = new Stack(); //creating new instance of Stack stack.push(1); stack.push(2); stack.push(3); console.log(stack.peek()); console.log(stack.isEmpty()); console.log(stack.size()); console.log(stack.pop()); console.log(stack.size()); stack.clear(); console.log(stack.isEmpty()); 
Output: 3 false 3 3 2 true

Implementación de pila con JavaScript

Vamos a implementar una pila con una matriz de JavaScript que tiene métodos incorporados como push y pop.

function Stack(){ var items = []; //other methods go here }

Empuje un elemento en la pila

//push an item in the Stackthis.push = function(element){ items.push(element); }

Sacar un artículo de la pila

//Pop an item from the Stackthis.pop = function(){ return items.pop(); }

Echa un vistazo al artículo superior de la pila

//Peek top item of the Stackthis.peek = function(){ return items[items.length - 1]; }

Compruebe si la pila está vacía

//Is Stack emptythis.isEmpty = function(){ return items.length === 0; }

Limpiar la pila

//Clear the Stackthis.clear = function(){ items.length = 0; }

Tamaño de la pila

//Size of the Stackthis.size = function(){ return items.length; }

Implementación completa de Stack

function Stack(){ var items = []; //other methods go here 
 //Push a item in the Stack this.push = function(element){ items.push(element); } 
 //Pop a item from the Stack this.pop = function(){ return items.pop(); } 
 //Peek top item of the Stack this.peek = function(){ return items[items.length - 1]; }
 //Is Stack empty this.isEmpty = function(){ return items.length === 0; } 
 //Clear the Stack this.clear = function(){ items.length = 0; } 
 //Size of the Stack this.size = function(){ return items.length; } 
}

Hacer que las propiedades y los métodos sean privados con el cierre y IIFE (Expresión de función inmediatamente invocada).

var Stack = (function () { return function Stack(){ var items = []; //other methods go here 
 //Push an item in the Stack this.push = function(element){ items.push(element); } 
 //Pop an item from the Stack this.pop = function(){ return items.pop(); } 
 //Peek top item from the Stack this.peek = function(){ return items[items.length - 1]; } 
 //Is Stack empty this.isEmpty = function(){ return items.length === 0; } 
 //Clear the Stack this.clear = function(){ items.length = 0; } //Size of the Stack this.size = function(){ return items.length; } }})();

Apilar usando ES6.

class Stack{ constructor(){ this.items = []; } //other methods go here //Push an item in the Stack push = function(element){ this.items.push(element); }
//Pop an item from the Stack pop = function(){ return this.items.pop(); } //Peek top item from the Stack peek = function(){ return this.items[this.items.length - 1]; }
//Is Stack empty isEmpty = function(){ return this.items.length === 0; }
//Clear the Stack clear = function(){ this.items.length = 0; } //Size of the Stack size = function(){ return this.items.length; }}

Apilar usando ES6 WeakMap.

const items = new WeakMap();class Stack{ constructor(){ items.set(this, []); } //other methods go here //Push an item in the Stack push = function(element){ let temp = items.get(this); temp.push(element); }
//Pop an item from the Stack pop = function(){ let temp = items.get(this); return temp.pop(); } //Peek top item from the Stack peek = function(){ let temp = items.get(this); return temp[temp.length - 1]; }
//Is Stack empty isEmpty = function(){ let temp = items.get(this); return temp.length === 0; }
//Clear the Stack clear = function(){ let temp = items.get(this); temp.length = 0; } //Size of the Stack size = function(){ let temp = items.get(this); return temp.length; }}

Hacer que las propiedades y los métodos sean privados con el cierre y IIFE (Expresión de función inmediatamente invocada) para Stack usando ES6 WeakMap.

let Stack = (() => { const items = new WeakMap(); return class Stack{ constructor(){ items.set(this, []); }
//other methods go here //Push an item in the Stack push = function(element){ let temp = items.get(this); temp.push(element); }
//Pop an item from the Stack pop = function(){ let temp = items.get(this); return temp.pop(); }
//Peek top item from the Stack peek = function(){ let temp = items.get(this); return temp[temp.length - 1]; }
//Is Stack empty isEmpty = function(){ let temp = items.get(this); return temp.length === 0; }
//Clear the Stack clear = function(){ let temp = items.get(this); temp.length = 0; }
//Size of the Stack size = function(){ let temp = items.get(this); return temp.length; } }})();

Complejidad del tiempo

# Promedio

Acceso: Θ (N)

Búsqueda: Θ (N)

Insertar: Θ (1)

Eliminar: Θ (1)

# Worst

Access: O(N)

Search: O(N)

Insert: O(1)

Delete: O(1)

Space Complexity

# Worst: O(N)

There are lots of problems where Stack can be the perfect data structure needed for the solution.

  • The base converter algorithm
  • Balanced Parentheses

If you liked this article, please give it some ?and share it! If you have any questions related to this feel free to ask me.

For more like this and algorithmic solutions in Javascript, follow me on Twitter. I write about ES6, React, Nodejs, Data structures, and Algorithms on learnersbucket.com.