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:

  1. add (x): inserta un nuevo valor a la entrada de la cola.
  2. remove(): obtiene el valor disponible en la salida de la cola y lo elimina de la cola.
  3. peek:() obtiene el valor disponible en la salida de la cola sin removerlo.
Haz clic acá para ver el código
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).

  1. push: agrega un valor a la pila que quedará disponible como siguiente valor de salida.
  2. pop: obtiene el siguiente valor de salida y lo remueve de la pila.
  3. peek: obtiene el siguiente valor de salida sin removerlo de la pila.
Haz clic acá para ver el código
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 ejemplo
class 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 ejemplo
const 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;
}

168 total views, 1 views today

0Shares
Última modificación: abril 27, 2019

Autor

Comentarios

Hola Jose, estoy interesado en una asesoría en diseño de apps.

Comenta o responde a los comentarios

Tu dirección de correo no será publicada.

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.