En este artículo vamos a revisar rápidamente los conceptos de colas, pilas y listas enlazadas.
Colas
Una cola es una estructura de datos que recibe valores y los dispone en un modelo de «primero en entrar, primero en salir» (FIFO).
Implementa 3 funciones básicas:
- add (x): inserta un nuevo valor a la entrada de la cola.
- remove(): obtiene el valor disponible en la salida de la cola y lo elimina de la cola.
- peek:() obtiene el valor disponible en la salida de la cola sin removerlo.
class Queue { constructor(){ this.mydata = []; } add(entry){ this.mydata.unshift(entry); } remove(){ return this.mydata.pop(); } peek(){ return this.mydata.slice(-1)[0]; } } //PRUEBAS const q = new Queue(); q.add(3); q.add(2); q.add(1); console.log("PEEK 3", q.peek()==3); console.log("PEEK 3", q.peek()==3); console.log("PEEK 3", q.peek()==3); console.log("REMOVE 3", q.remove()==3); console.log("REMOVE 2", q.remove()==2); console.log("REMOVE 1", q.remove()==1); console.log("REMOVE U", q.remove()==undefined);
Pilas
Una pila acumula valores y los dispone en modelo «primero en entrar, último en salir» (FILO).
- push: agrega un valor a la pila que quedará disponible como siguiente valor de salida.
- pop: obtiene el siguiente valor de salida y lo remueve de la pila.
- peek: obtiene el siguiente valor de salida sin removerlo de la pila.
class Stack { constructor(){ this.mydata = []; } push(entry){ this.mydata.push(entry); } pop(){ return this.mydata.pop(); } peek(){ return this.mydata[this.mydata.length-1]; } } //PRUEBAS const q = new Stack(); q.push(3); q.push(2); q.push(1); console.log("PEEK 3", q.peek()==1); console.log("PEEK 3", q.peek()==1); console.log("PEEK 3", q.peek()==1); console.log("POP 3", q.pop()==1); console.log("POP 2", q.pop()==2); console.log("POP 1", q.pop()==3); console.log("POP U", q.pop()===undefined);
Colas usando Pilas
El siguiente código de ejemplo muestra la implementación de una cola mediante dos pilas. El proceso es ineficiente pero sirve para ejemplificar las diferentes interacciones entre colas y pilas.
Haz clic acá para ver el código de ejemploclass Stack { constructor(){ this.mydata = []; } push(entry){ this.mydata.push(entry); } pop(){ return this.mydata.pop(); } peek(){ return this.mydata[this.mydata.length-1]; } } class Queue { constructor(){ this.stackA = new Stack(); this.stackB = new Stack(); } add(entry){ this.stackA.push(entry); } remove(){ while(this.stackA.peek()){ this.stackB.push(this.stackA.pop()); } let result = this.stackB.pop(); while(this.stackB.peek()){ this.stackA.push(this.stackB.pop()); } return result; } peek(){ while(this.stackA.peek()){ this.stackB.push(this.stackA.pop()); } let result = this.stackB.peek(); while(this.stackB.peek()){ this.stackA.push(this.stackB.pop()); } return result; } } //PRUEBAS const q = new Queue(); q.add(3); q.add(2); q.add(1); console.log(q.peek()); console.log("PEEK 3", q.peek()==3); console.log("PEEK 3", q.peek()==3); console.log("PEEK 3", q.peek()==3); console.log("REMOVE 3", q.remove()==3); console.log("REMOVE 2", q.remove()==2); console.log("REMOVE 1", q.remove()==1); console.log("REMOVE U", q.remove()==undefined);
Listas Enlazadas
Estructura de datos que agrupa nodos enlazados entre sí. Cada nodo contiene un valor y un enlace al siguiente nodo de la lista. El primer nodo de la lista se denomina «cabeza» y el último nodo se denomina «final». El nodo final se caracteriza por que su referencia a un siguiente nodo es nula. El nodo cabeza se caracteriza por que ningún nodo tiene una referencia a este nodo cabeza.
Haz clic acá para ver el código de ejemploconst linkedList = { head: undefined } linkedList.head = { data: 123 } const node2 = { data: 456 } const node3 = { data: 789 } linkedList.head.next = node2; node2.next = node3; var myNode = linkedList.head; while (myNode) { console.log(myNode.data); myNode = myNode.next; }
28,934 total views, 1 views today
Comentarios
Hola Jose, estoy interesado en una asesoría en diseño de apps.
Hola Amir. Gracias por tu comentario. Pronto te estaremos contactando por email. Saludos!
Hola me interesa una asesoría en diseño de apps
Claro Emiliano, con gusto, ¿De qué forma te podemos servir? te escribiré por email