Tema: Estructura de datos
Pregunta: Que es una Pila(Stack) y como hacerla en JAVA??
Respuesta: Ok, una pila es una estructura de datos la cual consta de dos métodos uno denominado PUSH y otro llamado POP.
El primer método (push) es con el que insertaremos
nodos a la pila, una pila se construye como una torre, los primeros "bloques" (nodos) que agregamos serán los últimos en ser quitados, ósea que vamos ir quitando el que este en la cima, o el ultimo en ser agregado!! por Ejemplo
8 -> 3 -> 7 -> 2 -> 9 -> 4 -> null
^
Raiz
(
root)
en ese ejemplo el primer elemento en ser agregado fue el
8 y el ultimo fue el
4, si quisiéramos agregar otro elemento a la pila seguiría después del
4. Pero si queremos sacar un elemento, el único que podemos sacar para este caso es el
4 y nuestra pila quedaría así:
8 -> 3 -> 7 -> 2 -> 9 -> null
^
Raiz
(
root)
Ok, ahora bien teniendo claramente el concepto de PILA, pasemos a JAVA, vamos a crear una clase llamada
NODO el cual va a contener el un
entero y un
"puntero" al siguiente nodo o elemento de la pila nuestro ejemplo anterior contiene
5 nodos. la clase quedaría algo así:
Código PHP:
/*
* Author: Crysfel Villa
* Created: Tuesday, June 14, 2005 7:41:24 PM
* Modified: Tuesday, June 14, 2005 7:41:24 PM
*/
public class Nodo{
public Nodo ptr;
public int contenido;
public Nodo(int c){
contenido = c;
ptr = null;
}
}
Ahora vamos a hacer la clase de la PILA, esta clase va a contener 3 metodos, PUSH, POP y PRINT, ademas contendra un puntero al primer elemento de la pila al que llamaremos “root”, el codigo queria algo asi:
Código PHP:
/*
* Author: Crysfel Villa
* Created: Tuesday, June 14, 2005 7:45:10 PM
* Modified: Tuesday, June 14, 2005 7:45:10 PM
*/
public class Pila
{
//PUNTERO AL PRIMER ELEMENTO DE LA PILA
private Nodo root;
//CONSTRUCTOR
public Pila(){
root = null;
}
//METODO PARA AGREGAR UN ELEMENTO A LA PILA
public void push(int num){
Nodo ptrTmp = root;
Nodo contenido = new Nodo(num);
if(ptrTmp == null){
root = contenido;
}else{
while(ptrTmp.ptr != null)
ptrTmp = ptrTmp.ptr;
ptrTmp.ptr = contenido;
}
}
//METODO QUE REGRESA EL ELEMENTO DE LA CIMA DE LA PILA
public int pop(){
Nodo ptrTmp = root;
Nodo ptrPenultimo = root;
int num = 0;
if(ptrTmp == null){
return 0;
}else if(root.ptr != null){
while(ptrTmp.ptr != null)
ptrTmp = ptrTmp.ptr;
while(ptrPenultimo.ptr != ptrTmp)
ptrPenultimo = ptrPenultimo.ptr;
num = ptrTmp.contenido;
ptrPenultimo.ptr = null;
}else{
num = root.contenido;
root = null;
}
return num;
}
//METODO PARA IMPRIMIR LA PILA
public void print(){
Nodo ptrTmp = root;
if(ptrTmp != null){
while(ptrTmp.ptr != null){
System.out.print(" [ " + ptrTmp.contenido + " ] ");
ptrTmp = ptrTmp.ptr;
}
System.out.print(" [ " + ptrTmp.contenido + " ] ");
}
}
}
Ahora solo nos falta hacer la aplicación que use esta clase, haré unos cuantos PUSH imprimo la lista luego un POP la imprimo de nuevo:
Código PHP:
/*
* Author: Crysfel Villa
* Created: Tuesday, June 14, 2005 7:58:02 PM
* Modified: Tuesday, June 14, 2005 7:58:02 PM
*/
public class appPila{
public static void main( String [] args )
{
Pila pila = new Pila();
for(int i=0;i<10;i++)
pila.push((int)(Math.random()*10)+1);
pila.print();
System.out.println();
pila.pop();
pila.print();
}
}
Ahora si ya tenemos lista nuestra alicacion usando una pila dinamica, puedes insertar N cantidad de nodos.
Tambien podemos aplicar el concepto de PILA usando arreglos, pero estariamos limitados a un numer N, en cambio esta aplicacion que acabamos de hacer no tenemos limite alguno :)
Pues bien esto a sido todo por ahora!! Espero que me halla explicado bien!! Hasta la proxima!!