Introduccion Estructuras de Datos

La Estrucutura de datos profundiza en la forma de organizar un conjunto de datos elementales con el objetivo de facilitar su manipulacion. El temario del curso es el siguiente:

1. Definiciones Basicas.
2. Estructuras líneas.
3. Estructuras recursivas.
4. Estructuras Relacionales.
5. Ordenamiento y busqueda.

Los textos de consulta se exponen a continuacion.

-> Estructuras de Datos & Algoritmos - Addison, Nesley
-> Diseño y Manejo de Estructuras - Villalobos McgrawHill
-> Estructuras de Datos - Cairo, Oswaldo
-> Estructuras de Datos - Becerra

Conceptos Basicos

A continuación se enumeran algunos conceptos básicos sobre la materia.

* Estructura*
Es la manera como se pueden organizar los datos para que puedan ser interpretados de forma lógica y ordenada.

*Dato*
Es la unidad mínima de información, por si misma no tiene significado pero al organizar de forma lógica una cantidad establecida, se logra obtener un significado coherente.

*Algoritmo*
Es un conjunto de pasos finitos ordenados con el cual obtenemos la resolución de un problema especifico.

*Programa*
Es un conjunto de instrucciones que puede interpretar un computador con el fin de realizar un proceso especifico.

*Recursividad*
Propiedad de algunos lenguajes de programación de permitir que un programa solicite su propia ejecución en el curso de su desarrollo.

*Iteratividad*
Las estructuras iterativas son aquellas que nos permiten repetir varias veces un proceso.

*Abstracción*
Consiste en aislar un elemento de su contexto o del resto de los elementos que lo acompañan.

*Clase*
Es una plantilla o un prototipo para crear objetos, por eso se dice que los objetos son instancias de clases.

*Objeto*
Se define como la unidad que en tiempo de ejecución realiza las tareas de un programa.

MAPA CONCEPTUAL


EFICIENCIA




Algoritmo mas efeiciente = menor tiempo de ejecucion.


Tiempos de ejecucion:


Entradas: n1,n2...n logn)
Complejidadx=1 -> 1Cont = cont + 1 -> n+1 ------> 2n + 3 Ta(n)=?; O(n)=?.If x -> n+1



Si Ta1(n) es O(f1(n)) -> Para todo c1n1 > 0 Para cualquier n > = n1 Ta1(n) <= c1*f1(n) n es 0 (f2(n)) => Para todo c1n1 > 0



Para cualquier c2,n2>0
Uso de memoria, datos simples y compuestos.
Mantenimiento a los programas. (reingenieria)Rapidez para hacer cambios, pra leer datos, modificacion. (reingenieria)
TORRES DE HANOI





Las Torres de Hanói es un rompecabezass o juego matemático inventado en 1883 por el matemático francés Éduard Lucas.
Consiste en tres varillas verticales y un número indeterminado de discos que determinarán la complejidad de la solución. No hay dos discos iguales, están colocados de mayor a menor en la primera varilla ascendentemente, y no se puede colocar ningún disco mayor sobre uno menor a él en ningún momento.


El juego consiste en pasar todos los discos a la tercera varilla colocados de mayor a menor ascendentemente.


Las reglas son:


Sólo se puede mover un disco cada vez.
Un disco de mayor tamaño no puede descansar sobre uno más pequeño que él mismo.
Sólo puedes desplazar el disco que se encuentre arriba en cada varilla.



RESOLUCION


El problema de las Torres de Hanói es curiosísimo porque su solución es muy rápida de calcular, pero el número de pasos para resolverlo crece exponencialmente conforme aumenta el número de discos.
Existen otras versiones del problema con un número diferente de varillas. Aunque se conocen algoritmos eficientes que resuelven el problema con 3 varillas de manera óptima, no se han encontrado aún sus contrapartidas para cualquier número (N igual o superior a 3) de ellas.


Otra manera de resolverlo es basándose en el disco más pequeño, en este caso el de hasta arriba. El movimiento inicial de este es hacia la varilla auxiliar. El disco número dos por regla, se debe mover a la varilla número tres. Luego el disco uno se mueve a la varilla tres para que quede sobre el disco dos. A continuación se mueve el disco que sigue de la varilla uno, en este caso el disco número tres, y se coloca en la varilla dos. Finalmente el disco número uno regresa de la varilla tres a la uno (sin pasar por la dos) y así sucesivamente. Es decir, el truco está en el disco más pequeño.


1- Mediante recursividad:


Este problema se suele plantear a menudo en ámbitos de programación, especialmente para explicar la recursividad.


Si numeramos los discos desde 1 hasta n, y llamamos X a la primera pila de discos (origen), Z a la tercera (destino) e Y a la intermedia (auxiliar) y a la función le llamaríamos hanoi (origen, auxiliar, destino), como parámetros, la función recibiría las pilas de discos.
El algoritmo de la función sería el siguiente:



Si origen == {0}: mover el disco 1 de pila origen a la pila destino (insertarlo arriba de la pila destino); terminar.
Si no: hanoi({0...n-1},destino, auxiliar) //mover todas las fichas menos la más grande (n) a la varilla auxiliar
mover disco n a destino //mover la ficha grande hasta la varilla final
hanoi (auxiliar, origen, destino) //mover todas las fichas restantes, {0...n-1}, encima de la ficha grande (n)
terminar



2- Mediante Iteratividad:


Otra manera de resolver el problema, sin utilizar la recursividad, se basa en el hecho de que para obtener la solución más corta, es necesario mover el disco más pequeño en todos los pasos impares, mientras que en los pasos pares sólo existe un movimiento posible que no lo incluye. El problema se reduce a decidir en cada paso impar a cuál de las dos pilas posibles se desplazará el disco pequeño:


El algoritmo en cuestión depende del número de discos del problema.
Si inicialmente se tiene un número impar de discos, el primer movimiento debe ser colocar el disco más pequeño en la pila destino, y en cada paso impar se le mueve a la siguiente pila a su izquierda (o a la pila destino, si está en la pila origen).


La secuencia será DESTINO, AUXILIAR, ORIGEN, DESTINO, AUXILIAR, ORIGEN, etc.
Si se tiene inicialmente un número par de discos, el primer movimiento debe ser colocar el disco más pequeño en la pila auxiliar, y en cada paso impar se le mueve a la siguiente pila a su derecha (o a la pila origen, si está en la pila destino).
La secuencia será AUXILIAR, DESTINO, ORIGEN, AUXILIAR, DESTINO, ORIGEN, etc.

****_ ALGORITMO EN JAV@_****
import java.util.Stack;
class Hanoy {
// Las 3 pilas de discos
private Stack columnas[];
// Constructor, toma el nº de fichas total
public Hanoy(int fichas) {
columnas = new Stack[3];
// Inicializamos las columnas vacias
columnas[0] = new Stack();
columnas[1] = new Stack();
columnas[2] = new Stack();
// Colocamos en la primera las fichas, de mayor a menor
for (int i=fichas;i>0;i--) columnas[0].push(i);
}
// Muestra el estado actual
public void Mostrar() {
for (int i=0;i<3;i++)>
System.out.print("Col. "+i+": ");
for(int n : columnas[i]) System.out.print("["+n+"]");
System.out.println("");
}
}
// Mueve de la columna origen a la columna destino 1 disco
public void Mover(int origen, int destino) {
// Mostramos en pantalla lo que hacemos
Mostrar();
System.out.println("Movemos desde ("+origen+") hasta ("+destino+")"); System.out.println("");
// Y luego, lo hacemos, claro
columnas[destino].push(columnas[origen].pop());
}
// Mueve de la columna origen a la columna destino varios discos
public void MoverN(int origen, int destino, int cuantas) {
// Si solo es uno, se mueve sin más
if (cuantas <= 1) Mover(origen,destino);
else {
// Si son varios, entonces:
// - Primero movemos N-1 a la columna ni origen ni destino
MoverN(origen,3 - (origen+destino),cuantas-1);
// - Movemos la N, es decir, la grande
Mover(origen,destino);
// - Movemos las N-1 del primer paso, a la col. destino
MoverN(3 - (origen+destino),destino,cuantas-1);
}
}
// Programa principal
public static void main(String args[]) {
// Creamos una partida de 5 discos
Hanoy h = new Hanoy(5);
// Y la resolvemos (movemos de col.0 a col.2 los 5 discos
h.MoverN(0,2,5);
// Mostramos resultado, resuelto
h.Mostrar();
}
}

Estructuras Lineales





Listas


Conjunto de elementos llamados nodos.


------------------

Dato puntero

------------------



------------------ ------------------- ---------------------------
Dato puntero ->Dato Puntero -> Dato Puntero a Null
------------------ ------------------- ---------------------------

Arreglos:


Estructura estatica, tieen un tamaño definido.


Elementos Enlazados:


Estructura dinamica, tamaño indefinido.


Operaciones :


- Insertar, Borrar, Buscar, Recorrer, Vacio, Tamaño.



public class Estructuras_Lineales


{


public void insertar (String Elemento);

public boolean eliminar (string elemento);

public string eliminar();

public booelan buscar(string elemento);

public string recorrer(); public boolean vacio();

public int tamaño();


}



PRINCIPAL . JAVA
package invent;import util.Lectura;
public class Principal {
public static void main (String argv[]) {
int opcion;
Lista lista = new Lista();
Lista aux=new Lista();
for(;;){
System.out.println("\n MENU PRINCIPAL");
System.out.println(" ==============");
System.out.println(" 1.Adicionar un elemento");
System.out.println(" 2.Generar listado de inventario");
System.out.println(" 3.Generar listado de subtotales de todo el inventario"); System.out.println(" 4.Modificar un valor");
System.out.println(" 5.Modificar la existencia");
System.out.println(" 6.Salir");
System.out.println("Digite Opcion : ");
opcion=Lectura.datoInt();
switch(opcion){
case 1:
lista.adicionar();
break;
case 2:
while (aux!= null){
aux.Lista_nodo();
aux = aux.sig;
break;
}
case 3:{
} case 4:{
}
case 5:{
}
case 6: System.exit(0);
default : System.out.println("\nDigito Opcion Errada");
}
}
}
}
LISTA . JAVA
package invent;import util.*;
public class Lista {
int codg_elemento; Lista aux;
Lista aux_a;
int aux1;
String nombre_elemento;
long valor_elemento;
int existencias;
Lista sig;
static Lista cab= null;
static Lista ult=null;
public void adicionar(){
Lista nuevo;
if (cab==null){
cab=new Lista();
cab.cargar();
cab.sig= null;
ult=cab;
}else{
nuevo=new Lista();
nuevo.cargar();
if (cab.codg_elemento>nuevo.codg_elemento){
nuevo.sig=cab;
cab=nuevo;
}else{
if (ult.codg_elemento
ult=nuevo;
ult.sig=null;
}else{
aux=cab;
while (aux!=null){
if (nuevo.codg_elemento
break;
aux_a=aux;
aux=aux.sig; }
nuevo.sig=aux;
aux_a.sig=nuevo;
}
}
}
}
public void cargar(){
System.out.println("Digite codigo del elemento:");
codg_elemento=Lectura.datoInt();
System.out.println("Digite nombre del elemento:");
nombre_elemento=Lectura.datoCadena();
System.out.println("Digite valor del elemento:");
valor_elemento=Lectura.datoLong();
System.out.println("Digite existencia:");
existencias=Lectura.datoInt(); }
public void Lista_nodo(){
System.out.println("Codigo del elemento="+codg_elemento);
System.out.println("Nombre elemento="+nombre_elemento);
}
}
PROGRAMA ALUMNOS
1- El programa pide el nombre del alumno y tres calificaciones para luego calcular su promedio. Se puede agregar cualquier cantidad de elementos a la lista.
Aqui vemos el Algoritmo respectivo:

import java.util.*;
public class ListaAlumnos{
static double prom;
public static void main( String args[] ){
Scanner leer = new Scanner(System.in);
NodoLista4 nodo = new NodoLista4();
int op;
ArrayList lista = new ArrayList(); do{
System.out.println( "Ingrese el nombre del alumno:" );
nodo.nom = leer.next();
System.out.println( "Ingrese la primera calificación:" );
nodo.calif1 = leer.nextInt();
System.out.println( "Ingrese la segunda calificación:" );
nodo.calif2 = leer.nextInt();
System.out.println( "Ingrese la tercera calificación:" );
nodo.calif3 = leer.nextInt();
lista.add("Nombre del alumno:\n"+nodo.nom);
lista.add("Calificación 1:\n"+nodo.calif1);
lista.add("Calificación 2:\n"+nodo.calif2);
lista.add("Calificación 3\n"+nodo.calif3);
promedio(nodo.calif1, nodo.calif2, nodo.calif3);
lista.add("Su promedio es:\n"+prom);
System.out.println( "¿Desea ingresar otro alumno?" );
System.out.println( "1.-Si\t 2.-No" ); op = leer.nextInt(); }
while(op != 2);
List lista2 = new ArrayList(lista);
Iterator it = lista2.iterator();
while (it.hasNext()){
System.out.println(it.next()+"");
}
} private static double promedio(int calif1, int calif2, int calif3){
int suma = calif1 + calif2 + calif3;
prom = suma/3; return prom;
}
}

LISTAS SIMPLES Y DOBLES

Listas simples enlazadas :





La lista enlazada básica es la lista enlazada simple la cual tiene un enlace por nodo. Este enlace apunta al siguiente nodo en la lista, o al valor NULL o a la lista vacía, si es el último nodo.







Lista Doblemente Enlazada :





Un tipo de lista enlazada más sofisticado es la lista doblemente enlazada o lista enlazadas de dos vías. Cada nodo tiene dos enlaces: uno apunta al nodo anterior, o apunta al valor NULL o a la lista vacía si es el primer nodo; y otro que apunta al siguiente nodo siguiente, o apunta al valor NULL o a la lista vacía si es el último nodo.






Aplicaciones de las listas enlazadas :



Las listas enlazadas son usadas como módulos para otras muchas estructuras de datos, tales como pilas, colas y sus variaciones.
El campo de datos de un nodo puede ser otra lista enlazada. Mediante este mecanismo, podemos construir muchas estructuras de datos enlazadas con listas; esta practica tiene su origen en el lenguaje de programación Lisp, donde las listas enlazadas son una estructura de datos primaria (aunque no la única), y ahora es una característica común en el estilo de programación funcional.
A veces, las listas enlazadas son usadas para implementar arrays asociativos, y estas en el contexto de las llamadas listas asociativas. Hay pocas ventajas en este uso de las listas enlazadas; hay mejores formas de implementar éstas estructuras, por ejemplo con árboles binarios de búsqueda equilibrados. Sin embargo, a veces una lista enlazada es dinámicamente creada fuera de un subconjunto propio de nodos semejante a un árbol, y son usadas más eficientemente para recorrer ésta serie de datos






OPERACIONES CON LISTAS SIMPLES:







1. Insertar
2. Borrar
3. Buscar
4. Recorrer
5. Vacio
6.Tamaño





OPERACIONES CON LISTAS DOBLES:




1. Buscar

2. Insertar

3. Eliminar

4. Recorrer

5. Vacio





// EN LISTAS SIMPLES:

PUBLIC VOID ( INSERTAR) ( STRING ELEMENTO);
PUBLIC BOOLEAN ELIMINAR ( STRING ELEMENTO);
PUBLIC STRING ELIMINAR ();
PUBLIC BOOLEAN BUSCAR ( STRING ELEMENTO);
PUBLIC STRING RECORRER();
PUBLIC BOOLEAN VACIO();
PUBLIC INT TAMAÑO ();
// EN LISTAS DOBLES:
FUNCIONES:


- get_first: Obtiene el primero y regresa los datos a el nodo cabecera.
- get_last: Obtiene el ultimo y regresa los datos al nodo cola.
- IS_empty: (Vacio) Regresa informacion sobre la lista esta vacia o no?
- java.util




El siguiente código inserta un elemento a continuación de otro en una lista simple. El diagrama muestra como funciona:














De forma similar, también tenemos funciones para borrar un nodo dado ó para borrar un nodo del principio de la lista:



SIMPLES:

Insertar

ANTES / DESPUES

Pseudocodigo:

p __cab

mensaje (antes/ despues);

Si antes entonces

Mientras que p < > null Haga

Si p (dato) = " x " entonces

new (q)

leer

(q (dato)

Aant[ ]

Bdes----

EN JAVA:

Nodo inicio

public Lista ( ) {

inicio = null;

}

public boolean vacia ( ) {

return ( inicio = null );

}

public int tamaño ( ){

int n = o

Nodotemporal = inicio

While ( temporal ! = null ) {

n ++

temporal = temporal.enlace

}

return n;

}

public boolean Buscar ( string elemento ){

Nodotemporal = inicio;

while ( temporal ! = null

if elemento.equals ( temporal.dato))

return true;

else

temporal = temporal.enlace

}

return false;

}

LISTAS ENLAZADAS

-isEmpty: Determina su la lista esta vacia.

-Size: Determina el numero de elementos en la lista.

DECLARAR UN NODO

Declare ClassNodo

Declare String Name

Declare NodoNext

end declare

Declare Nodo top = null

top = new nodo

top.name= " a"

top.next = null

* Informacion

- Entero

- Real

- String

EN LISTAS DOBLES:

Insertar un nodo en la ultima posicion:

temp = new nodo

temp.name = " c "

temp.next = null

while temp2. next is not null

temp2 = temp2.next

end while

temp2. next = temp

SERIE DE FIBONACCI




Gráfica de la sucesión de Fibonacci hasta f10
En matemáticas, la sucesión de Fibonacci es la siguiente sucesión infinita de números naturales:

El primer elemento es 0, el segundo es 1 y cada elemento restante es la suma de los dos anteriores. A cada elemento de esta sucesión se le llama número de Fibonacci. Esta sucesión fue descrita en Europa por Leonardo de Pisa, matemático italiano del siglo XIII también conocido como Fibonacci. Tiene numerosas aplicaciones en ciencias de la computación, matemáticas y teoria de juegos.
Una sucesión de Fibonacci es aquella cuya ley de recurrencia es:

an = an-1 + an-2
Es decir, cada término de la sucesión se obtiene sumando los dos anteriores. Para empezar a construirla necesitamos, por tanto, dos números de partida, a1 y a2. De esta forma, a3 sería a2 + a1 ; a4 sería a3 + a2 y así sucesivamente. La más conocida es la que tiene a1 = 1 y a2 = 1, cuyos términos son:

1 1 2 3 5 8 13 21 34 55 89 144 233 377 ...
números que son conocidos como Números de Fibonacci.Los términos de cualquier sucesión de Fibonacci tienen la particularidad de que el cociente entre dos términos consecutivos se aproxima al Número de Oro (1.6180339887499...), es decir, el límite de los cocientes an+1/an tiende al Número de Oro cuando n tiende a infinito.Además, las series de Fibonacci cumplen otras curiosas propiedades, como por ejemplo, que la suma de n términos es igual al término n+2 menos uno:

a1 + a2 + a3 + a4 + ..... + an-1 + an = an+2 - 1
Definición formal

Los números de Fibonacci quedan definidos por las ecuaciones:

(1) f=0
(
2) f=1
(
3) fn=fn-1+fn-2 para n= 2,3,4,5,.......
Esto produce los números
* F0= 0
* F1= 1
* F2= 1
* F3= 2
* F4= 3
* F5= 5
* F6= 8
y así sucesivamente hasta el infinito.







ALGORITMO EN JAVA

import java.io.*;

public class Fibonacci
{
public static void main (String [] args)
{
double f1=1, f2=1;
int cantidad=0;

BufferedReader teclado = new BufferedReader(new InputStreamReader(System.in));

try
{
System.out.println("Digita cuantos numeros de las serie quieres ver: ");
cantidad=Integer.parseInt(teclado.readLine());
}
catch(IOException e)
{
System.exit(0);
}
catch(NumberFormatException e1)
{
System.out.println("No Digito Un Numero!");
System.exit(0);
};

System.out.println (f1);

for(int i=0; i{
System.out.println(f2);
f2+=f1;
f1 = f2 - f1;
}
}
}

ESTRUCTURAS LINEALES: PROGRAMA PARA ESCOGER CUANTAS EDADES DESEAMOS INGRESAR Y BUSCAR LA DESEADA

public class problema1
{public static void main(String[] args)
{System.out.print("¿Cuántas edades desea ingresar?");
int n=Leer.datoInt();
int[] edades=new int[n];
int i;
for(i=0;i
{
System.out.println("ingrese edad No "+(i+1)+":");
edades[i]=Leer.datoInt();
}System.out.println("\nbuscar edad\n");
System.out.print("ingrese edad a buscar:");
int E=Leer.datoInt();
boolean encontrado=false;for(i=0;i
if (edades[i]==E){System.out.println("edad encontrada en el indice:"+i);
encontrado=true;}
}if (encontrado==false)System.out.println("no se encuentra la edad buscada en el array");
System.out.println("\nEdades almacenadas\n");
for(i=0;i
System.out.println("edades["+i+"]:"+edades[i]);
}
}
}




2. PROGRAMA " CLASS DINERO"





import java.io.*;
public class Dineroc {
public static void main(String[] args) throws IOException{
int b200,b100,b50,b20,b10,m5,m2,m1,n,r;
String cad="";
InputStreamReader dsf;
BufferedReader buffer;
dsf=new InputStreamReader(System.in);
buffer=new BufferedReader(dsf);
System.out.print("INGRESE CANTIDAD DE DINERO:");
cad=buffer.readLine();
n=Integer.parseInt(cad);
b200=n/200;
r=n%200;
b100=r/100;
r=r%100;
b50=r/50;
r=r%50;
b20=r/20;
r=r%20;
b10=r/10;
r=r%10;
m5=r/5;
r=r%5;
m2=r/2;
r=r%2;
m1=r/1;
r=r%1;
System.out.println("Billete de 200 :"+b200);
System.out.println("Billete de 100:"+b100);
System.out.println("Billete de 50:"+b50);
System.out.println("Billete de 20 :"+b20);
System.out.println("Billete de 10:"+b10);
System.out.println("moneda de 5:"+m5);
System.out.println("moneda de 2:"+m2);
System.out.println("moneda de 1:"+m1);
}
}

PROGRAMA SOBRE LISTAS

import java.io.Serializable;

class Empleados implements Serializable{
private String cedula;
private String nombres;
private String apellidos;
private String cargo;
private double basico=0;
private double comision=0;
private double auxilioT=0;
Empleados siguiente;

public Empleados(String vcedula,String vnombres, String vapellidos,String vcargo,double vbasico, double vcomision, double vauxilio ){
cedula=vcedula;
nombres=vnombres;
apellidos=vapellidos;
cargo=vcargo;
basico=vbasico;
comision=vcomision;
auxilioT=vauxilio;
}

public void setCedula(String valor){
cedula=valor;
}

public String getCedula(){
return cedula;
}

public void setNombres(String valor){
nombres=valor;
}
public void setApellidos(String valor){
apellidos=valor;

}
public void setCargo(String valor){
cargo=valor;
}
public void setBasico(double valor){
basico=valor;
}
public void setComision(double valor){
comision=valor;
}
public void setAuxilioT(double valor){
auxilioT=valor;
}

public String getNombres(){
return nombres;
}
public String getApellidos(){
return apellidos;

}
public String getCargo(){
return cargo;
}
public double getBasico(){
return basico;
}
public double getComision(){
return comision;
}
public double getAuxilioT(){
return auxilioT;
}
public double getSalario(){
return basico+comision+auxilioT;
}

public void mostrar(){
System.out.println(cedula);
System.out.println(nombres);
System.out.println(apellidos);
System.out.println(cargo);
System.out.println(basico);
System.out.println(comision);
System.out.println(auxilioT);
System.out.print("Total a Pagar");
System.out.println(getSalario());
}

}
class LstaEmpleados{
Empleados datos;
Empleados inicio;
public void agregar(Empleados dato){
if(datos==null){
datos=dato;
inicio=datos;
datos.siguiente=null;
}
else{
datos.siguiente=dato;
datos=datos.siguiente;
datos.siguiente=null;
}
}

public void mostrar(){
datos=inicio;
int i=1;
while(datos!=null){
System.out.print("Empleado #");
System.out.println(i);
datos.mostrar();
datos=datos.siguiente;
i++;
}
}
public void leer(){
String ced=javax.swing.JOptionPane.showInputDia...
String nom=javax.swing.JOptionPane.showInputDia...
String apel=javax.swing.JOptionPane.showInputDi...
String cargo=javax.swing.JOptionPane.showInputD...
double Basico=Double.parseDouble(javax.swing.JO...
double comisiones=Double.parseDouble(javax.swin...
double auxilio=Double.parseDouble(javax.swing.J... de Transporte:"));

Empleados dato=new Empleados(ced, nom, apel, cargo, Basico, comisiones, auxilio);
agregar(dato);
}
public void menu(){
int op=0;
String texto="ESTRUDATOS\nDigite el numeros de la opcion que desea utilizar\n1. Agregar\n2. Mostrar\n3. Salir \n\nOpción";
do{
op=Integer.parseInt(javax.swing.JOptionP...
switch (op){
case 1: leer();
break;
case 2: mostrar();
break;
default: if(op>3 op<1) aplicacion="new">

QUE ES UNA PILA

Una Pila es en la que el modo de acceso a sus elementos es de tipo LIFO (del inglés Last In First Out, último en entrar, primero en salir) que permite almacenar y recuperar datos. Se aplica en multitud de ocasiones en informática debido a su simplicidad y ordenación implícita en la propia estructura.

Para el manejo de los datos se cuenta con dos operaciones básicas: apilar (push), que coloca un objeto en la pila, y su operación inversa, retirar (o desapilar, pop), que retira el último elemento apilado.
En cada momento sólo se tiene acceso a la parte superior de la pila, es decir, al último objeto apilado (denominado TOS, Top of Stack en inglés). La operación retirar permite la obtención de este elemento, que es retirado de la pila permitiendo el acceso al siguiente (apilado con anterioridad), que pasa a ser el nuevo TOS.
Por analogía con objetos cotidianos, una operación apilar equivaldría a colocar un plato sobre una pila de platos, y una operación retirar a retirarlo.




Las pilas suelen emplearse en los siguientes contextos:




Evaluación de expresiones en notación postfija (notación polaca inversa).
Reconocedores sintácticos de
lenguajes independientes del contexto
Implementación de
recursividad.



OPERACIONES:



Una pila cuenta con 2 operaciones imprescindibles: apilar y desapilar, a las que en las implementaciones modernas de las pilas se suelen añadir más de uso habitual.



Crear: se crea la pila vacía.
Apilar: se añade un elemento a la pila.(push)
Desapilar: se elimina el elemento frontal de la pila.(pop)
Cima: devuelve el elemento que esta en la cima de la pila. (top o peek)
Vacía: devuelve cierto si la pila está vacía o falso en caso contrario.






METODOS PILAS

Metodo_Principal.java (Metodo Principal)
JAVA:
import java.io.*;

public class Metodo_Principal{

//Declaramos el metodo principal
public static void main (
String args[])throws IOException {

BufferedReader entrada = new BufferedReader (new InputStreamReader(System.in));
int Espacios = 0;
char Resp, op;
String aux;

//--- Imprimir Menu ---- \\

System.out.println("\n :: XROM RELOADED :: 19/07/07 \n");

System.out.print("\t Cuantos espacios quiere en la Pila (entre 3 y 30 recomendable)? :");
Espacios =
Integer.parseInt(entrada.readLine());

Pila Ejecutar = new Pila(Espacios);

System.out.println("\n\n\t --- //---- Menu Pila------\\\\---- \n");

do {

System.out.println("\n\n1.- Imprimir Pila"); // Mostrar
System.out.println("2.- Agregar Elemento a la pila"); // Push
System.out.println("3.- Quitar Elemento de la pila"); // Pop


System.out.print("\n\n Elija una Opcion : ");

aux = entrada.readLine();
op = aux.charAt(0);



//---- Elegir opcion ---\\

switch (op) {

case '1':

Ejecutar.Imprimir();

break;

case '2':


Ejecutar.Push();


break;

case '3':

Ejecutar.Pop();

break;


default:

System.out.println("opcion fuera de rango !!");



} // Fin del switch


System.out.print("Desea hacer otra operacion ?? S / N ");
aux = entrada.readLine();
Resp = aux.charAt(0);



} while (Resp == 'S' Resp == 's');

System.out.println(" Garcias por utilizar este programa.. ");
System.out.println("\t para mas informacion en :: WWW.XROMRELOADED.TK ::");


} // Fin del metodo main

} // Fin de la calse
Pila.java (Clase y Metodos)
JAVA:
// Libreria necesaria para introducir datos desde el Teclado
import java.io.*;

// Inicio de la Clase Pila
public class Pila {


//----- Atributos de la pila ------\\


public int Pila []; // Estructura de la pila

public int Top, Max , Elem; // variables para la pila

//Top : El Tope de la pila , referencia al ultimo elemento que esta en la pila
//Max : Maximo de espacios que tiene la pila
//Elem : Elemento que se agrega a la pila (Tecleado por el usuario)

public char Resp; // Variables para SubMenus.
public
String aux;


//----- Contructor -------\\


public Pila (int Espacios){ // se recibe como parametro los Espacios de la pila

Pila = new int [Espacios]; // Asignamos los espacios en la Pila
Max = Pila.length - 1;
Top = -1; // Top se declara como -1 como referencia a que no existen datos en la pila


} // fin del constructor


//----- Metodos de la pila -------\\


// Metodo Imprimir

public void Imprimir () {

for (int n = 0 ; n <= Max ; n++ ) {
System.out.println(n + ".- " + Pila [n]);


}

} // Fin del Metodo Imprimir



// Metodo Push


public void Push ( ) throws
IOException { // Metodo para ingresar datos ...

BufferedReader entrada = new BufferedReader (new InputStreamReader(System.in));

do {

// if (1)

if(Top != Max) { // Si la pila No esta llena ....

// Se puede agregar un nuevo dato a la pila ....

System.out.print("\t Ingrese un numero entero : ");
Elem =
Integer.parseInt(entrada.readLine());
Top ++; // Se incrementa Top como referencia de que se agrego un nuevo dato
Pila[Top] = Elem; // Se agrega el nuevo elemento a la pila

// if (1.1)

if (Top == Max) { // Si la pila quedo llena entoces ...

// Imprimir mensaje
System.out.print("\n La Pila a quedado llena !! ");

// con esta variable detenemos el bucle do - while
Resp = 'N';

} // Fin del if (1.1)



} else {

System.out.println("\n Pila llena !! Imposible introducir un valor a la pila");

Resp = 'N'; // detenemos el bucle


} // Fin del if (1)


// if (2)

if (Resp != 'N') {
// Si es diferente de No , entoces seguir preguntado si se desea introducir mas datos

System.out.print("Desea introducir un dato mas ??");

aux = entrada.readLine();
Resp = aux.charAt(0);

} // Fin del if (2)


} while (Resp == 'S' Resp == 's'); // Continuar ciclando simpre y cuando sea Resp = 's'

} // Fin del Metodo Push



// Metodo Pop

public void Pop () {

if(Top != -1) { // Si la pila no esta vacia entonces ....

System.out.println("Se borro el Dato : " + Pila[Top]);

// Eliminar dato

Pila[Top] = 0; // remplaza el valor por un cero (Eliminado)

Top --; // Top se reduce para decir que un elemento se borro

} else { // De lo contrario imprime .."que la pila esta vacia"

System.out.println("Pila Vacia... Imposible Eliminar");

} // fin del if

} //Fin del Metodo Pop

} // Fin de la Clase Pila
2- PROGRAMA_PILAS
class PilaLi implements Pila
{
private Nodo tope;

public PilaLi()
{
tope = null;
}

public boolean esVacia()
{
return tope == null;
}

public void vaciar()
{
tope = null;
}

public void push(Object x)
{
tope = new Nodo(x,tope);
}

public Object info() throws Exception
{
if ( esVacia() )
throw new Exception("info");

return tope.dato;
}


public void pop() throws Exception
{
if ( esVacia() )
throw new Exception("pop");

tope = tope.siguiente;
}

}

interface Pila
{
void push(Object x);
void pop() throws Exception;
Object info() throws Exception;
boolean esVacia();
void vaciar();
}

class Nodo
{
public Object dato;
public Nodo siguiente;

public Nodo(Object elemento, Nodo sgte)
{
this.dato = elemento;
this.siguiente = sgte;
}

public Nodo(Object elemento)
{
this(elemento,null);
}
}
import java.io.*;

class test2
{
public static void convertirBase(int numero,int base)
{
Pila p = new PilaLi();

while(numero != 0)
{
p.push(new Integer( numero % base ));
numero /= base;
}

try
{
for(;;)
{
System.out.print(p.info());
p.pop();
}

} catch(Exception e) {}
}


public static void main(String arg[])
{
BufferedReader in = new BufferedReader(new
InputStreamReader(System.in));

int num,base;
boolean seguir = true;

while(seguir)
{
try
{

System.out.print("\n\tIngrese un numero : ");
num = Integer.parseInt(in.readLine());

System.out.print("\tIngrese la nueva base : ");
base = Integer.parseInt(in.readLine());

System.out.print("\tEl numero " + num + " en base " + base + " es : ");
convertirBase(num,base);

System.out.print("\n\tQuiere seguir : s/n : ");
String resp = in.readLine();

if (resp.charAt(0) == 's') seguir = true;
else seguir = false;

}
catch (Exception e)
{
System.out.println("\tError de entrada : " + e);
}


} // fin while

} // fin main
}
class TestPila
{
public static void main(String arg[])
{
Pila p = new PilaLi();

for(int i = 0; i < pilaaux =" duplicar(pila);" e =" pilaAux.tope();" pila2 =" (Pila)pila.getClass().newInstance();" pilaaux =" (Pila)pila.getClass().newInstance();" e =" pila.tope();" e =" pilaAux.tope();" pilaaux =" new" colaaux =" duplicar(cola);" e =" colaAux.primero();" cola2 =" (Cola)cola.getClass().newInstance();" e =" pilaAux.tope();">

IMPLEMENTACIONES

package pilaBasadaLista;
import pilaException.*;
import listaException.*;
import listaSimpleEnlazada.*;
public class Pila implements pilaInterface.Pila {
private Lista lista;
public Pila() {
lista = new Lista();
}
public boolean vacia() {
return lista.vacia();
}
public Object tope() throws PilaVaciaException {
if (vacia()) throw new PilaVaciaException();
try {
return lista.recupera(lista.primero());
} catch (ListaException e) {
System.err.println("Error interno de la Pila: "+e);
return null;
}
}
public void push(Object elemento) {
try {
if (vacia()) lista.inserta(lista.fin(),elemento);
else lista.inserta(lista.primero(),elemento);
} catch (ListaVaciaException e) {
System.err.println("Error interno de la Pila");
}
}
public void pop() throws PilaVaciaException{
if (vacia()) throw new PilaVaciaException();
try {
lista.suprime(lista.primero());
} catch (ListaException e) {
System.err.println("Error interno de la Pila");
}
}
} // fin class Pila

*************************************
IMPLEMENTACION CON VECTORES

package pilaContigua;
import pilaException.*;
public class Pila implements pilaInterface.Pila {
private static int max = 100;
private Object elementos[];
private int tope;
public Pila() {
elementos = new Object[max];
tope=max;
}
public boolean vacia() {
return (tope==max);
}
**********************************
public Object tope() throws PilaVaciaException {
if (vacia()) throw new PilaVaciaException();
return elementos[tope];
}
public void push(Object elemento) {
tope--;
elementos[tope]=elemento;
}
public void pop() throws PilaVaciaException{
if (vacia()) throw new PilaVaciaException();
tope++;
}
} // fin class Pila

IMPLEMENTACIÓN CON APUNTADORES

package pilaSimpleEnlazada;
import pilaException.*;
public class Pila implements pilaInterface.Pila {
class Celda {
Object elemento;
Celda sig;
}
private Celda pila;
public Pila() {
pila = null;
}
public boolean vacia() {
return (pila==null);
}
public Object tope() throws PilaVaciaException {
if (vacia()) throw new PilaVaciaException();
return pila.elemento;
}
public void push(Object elemento) {
Celda aux = new Celda();
aux.elemento = elemento;
aux.sig = pila;
pila = aux;
}
public void pop() throws PilaVaciaException{
if (vacia()) throw new PilaVaciaException();
pila = pila.sig;
}
} // fin class Pila

public class Prueba{
public static void main(String[]args){
//creamos nuestros arrays de enterosint array1[]= {1,2,3,4,5,6,7};
int array2[]= {1,2,3,4
array3[]= {1,2};
int array4[]= {1,2,3,4,5,6,7,8,9,10};
int array5[]= {1};
int array6[]= {1,2,3,4,5};
int array7[]= {1,2,3,4,5,6};
//rellenamos los vectoresVectorEnteros v1=new VectorEnteros();
v1.añadir(array1);
VectorEnteros v2=new VectorEnteros();
v2.añadir(array2);
VectorEnteros v3=new VectorEnteros();
v3.añadir(array3);
VectorEnteros v4=new VectorEnteros();
v4.añadir(array4);
VectorEnteros v5=new VectorEnteros();
v5.añadir(array5);
VectorEnteros v6=new VectorEnteros();
v6.añadir(array6);
VectorEnteros v7=new VectorEnteros();
v7.añadir(array7);
//creamos una pila con los 7 vectores de enteros Pila p1=new Pila(7);
p1.push(v1);
p1.push(v2);
p1.push(v3);
p1.push(v4);
p1.push(v5);
p1.push(v6);
p1.push(v7);
//creamos varias pilas para almacenar en la cola y hacer pruebas con ellas Pila p2=new Pila(7); p2=p1;
Pila p3=new Pila(7);
p3=p1;
Pila p4=new Pila(7);
p4=p1;
Pila p5=new Pila(7);
p5=p1;
Pila p6=new Pila(7);
p6=p1;
Pila p7=new Pila(4);
//cambiamos el orden y el tamañop7.push(v4);
p7.push(v2);p7.push(v3);
p7.push(v1);
Cola c1=new Cola();
c1.encolar(p1);
c1.encolar(p7);
c1.encolar(p3);
c1.encolar(p7);
Cola c2=new Cola();
c2.encolar(p7);
c2.encolar(p6);
c2.encolar(p5);
Cola c3=new Cola();
Cola c4=new Cola();
c4.encolar(p7);
c1.desencolar();
c1.imprimir();
c2.imprimir();
c3.imprimir();
c4.imprimir();
}
}
//Fin clase

//Clase Cola implementada como lista dinámica en la que se almacenan pilas. Observar que se cumple FIFO:

public class Cola{private Nodo primero;
private Nodo ultimo;
public Cola(){primero = null;ultimo = null;}
public boolean vacia(){return (primero == null);}
public void encolar(Pila p)
{Nodo nuevo = new Nodo(p,null);
if(vacia())primero = nuevo;
lseultimo.siguiente = nuevo;
ultimo = nuevo;}
public Pila desencolar(){if(vacia())
{System.err.println(”No hay elementos en la cola\n”);
return null;}
else{Pila p = primero.pila;primero = primero.siguiente;
if(vacia()){ultimo = null;}
return p;
}
}
public void imprimir(){int j=1;
if(!vacia()){
System.out.println(”CONTENIDO DE LA COLA\n”);
while(!vacia())
{System.out.println(”Pila “+j+”: \n”);
Pila p = primero.pila;
primero = primero.siguiente;
ultimo = null;
p.imprimir();
j++;}
System.out.println(”\n”);
}else
{System.out.println(”ESTA COLA ESTÁ VACÍA”);
System.out.println(”\n\n”);}
}
}
//Fin clase

//Clase Pila implementada como array en la que se almacenan vectores de enteros. Observar que se cumple LIFOpublic
class Pila{private int numElementos;private VectorEnteros elementos[];
private int indice;
public Pila(int numElementos)
{this.numElementos=numElementos;indice=-1;
elementos= new VectorEnteros[numElementos];
for(int i=0;
i
i++){elementos[i]=new VectorEnteros();}
}
public int vacia(){return(indice =-1);}
public int llena(){return (indice=numElementos-1);}
public void push(VectorEnteros v){indice++;elementos[indice]=v;}
public VectorEnteros pop(){VectorEnteros v= elementos[indice];
indice–;return v;}
public void imprimir()
{int j=0;
for (int i=elementos.length-1;
i>=0;i–){System.out.print(”Vector “+(j+1)+”\t”);
elementos[i].imprimir();j++;
}System.out.println(”");
}
}
//Fin clase

CLASE VECTOR DE ENTEROS

import java.util.Vector;
import java.util.Enumeration;
public class VectorEnteros {
//vector que va a guardar los enterosprivate Vector vectorenteros;
/*Por simplicidad creamos un array que contenga inicialmente los enteros que queremos guardar.Si queremos modificar el vector, solo hay que modificar el array correspondiente en la
clase Prueba*/private int numeros[];
public VectorEnteros(){
//Creo el vectorvectorenteros=new Vector();}
public void añadir(int n[])
{numeros=n;for (int i=0;
i<>
i++){Integer num=new Integer(numeros[i]);
vectorenteros.addElement(num);}
}
public void imprimir(){Enumeration e=vectorenteros.elements();
while(e.hasMoreElements()){
//Hay que hacer cambio de tipoInteger entero=(Integer)e.nextElement();
System.out.print(entero+” “);
}System.out.println(”");
}
}
//Fin clase