UNIDAD I Y UNIDAD II

CONCEPTOS BÁSICOS 

Estructura de datos: Es una forma de organizar un conjunto de datos elementales con el objetivo de facilitar su manipulación. Un dato elemental es la mínima información que se tiene en un sistema.

Una estructura de datos define la organización e interrelación de estos y un conjunto de operaciones que se pueden realizar sobre ellos. Las operaciones básicas son:
Alta, adicionar un nuevo valor a la estructura.
Baja, borrar un valor de la estructura.
Búsqueda, encontrar un determinado valor en la estructura para realizar una operación con este valor, en forma secuencial o binario (siempre y cuando los datos estén ordenados).

Datos primitivos:Tipos de datos originales de un lenguaje de programación, esto es, aquellos que nos proporciona el lenguaje y con los que podemos (en ocasiones) construir tipos de datos abstractos y estructuras de datos.
Generalmente ejemplos de tipos primitivos son:
char (carácter)
int (entero)
float (real (coma flotante)).

Datos Compuestos: Son conjunto de partidas de datos simples con relaciones definidas entre ellos estructurados.
Arreglos 
Registros 
Archivos 

Abstracción de datos:Técnica que permite diseñar estructuras de datos que consiste en representar las características esenciales de una estructura de datos, olvidándose de los detalles específicos de implementación de los datos, escondiendo la complejidad a los usuarios para simplificar su interacción con el sistema.

UNIDAD II 

Estructuras de datos lineales y no lineales 

Estructura de datos lineales:Se caracterizan porque sus elementos están en secuencia, relacionados en forma lineal, uno luego del otro. Cada elemento de la estructura puede estar conformado por uno o varios sub-elementos o campos que pueden pertenecer a cualquier tipo de dato, pero que normalmente son tipos básicos.

Una estructura lineal de datos os lista esta conformada por ninguno, uno o varios elementos que tienen una relación dónde existe un primer elemento, seguido de un segundo elemento y así sucesivamente hasta llegar al último.
El valor contenido en los elementos pueden ser el mismo o diferente. En estas estructuras se realizan operaciones de agregar y/o eliminar elementos a la lista según un criterio particular.


Se clasifican en listas de acceso restringido y listas de acceso no restringido.
las listas de acceso restringido son las pilas, colas y dipolos.

Pilas: En las pilas, las operaciones de acceso se realizan por un unico extremo de la lista, al cual normalmente se denomina tope de la pila. Las operaciones básicas sobre una pila son: crearlo, destruirla, agregar un nuevo elemento, suprimir un elemento, consultar el elemento del tope verificar si esta vacía

Colas: En las colas, estas operaciones de acceso se realizan por ambos extremos de la lista llamados gralmente, inicio y fin de la cola. Operaciones básicas son: creación, destrucción, inserción al final de un nuevo elemento, consultar que elemento esta al inicio y cual al final, y verificar si la cola está vacía.

Lista:La lista es el tipo más general de estructura lineal donde las inserciones y eliminaciones se hacen en cualquier punto de la lista, por ello se debe especificar donde se requiere que se haga la operación.
Sus operaciones
básicas son: creación, destrucción, inserción, eliminación, consulta y verificación de lista vacía.

CÓDIGO DE  UNA PILApublic class PilaArray 
{
  
 private int vector[];
 private int cima, tamano;


  public PilaArray( int tamano_p)//tamano de la pila parametro constructor
  {
    if( tamano_p < 0)
    {    
      tamano = 0;  
      System.err.println("Error, tamano no valido");
    }//fin if
    else
    {
        
       vector = new int[ tamano_p ];
       tamano = tamano_p;
       cima = -1;
    }//fin else    
    
    
      
  }
    
//para saber si la pila esta vacia 
  public boolean vacia()
  {
   if(cima == -1)
       return true;
   
   return false;
  }
    
  
  //Devuelva true si logra insertar elemento
  public boolean inserta(int valor)
  {
    //si ya no hay espacio...  
    if( cima == tamano-1 )
    {
      System.err.println("OverFloat");
      return false;
    }    
    else
    {
      vector [ ++cima ] = valor;
      System.out.println("Agregado correctamente");
      return true;
    }    
  }
  
  //devuelve el valor de la cima de la pila
  public int cima()
  {
    //si la pila esta vacia...  
    if( vacia() )  
    { 
       System.err.println("La pila esta vacia"); 
       //si la pila esta vacia se retorna un 0 ... solo por ejemplo
       
       return 0;
    }  
    else
    {
      return vector[ cima-- ];  
    }    
  }
  
  //limpia la pila
  public void vaciar()
  {
     cima = -1; 
  }
  
  

}//fin clase pila


CÓDIGO DE UNA COLA

public class Cola {
    
    class Nodo {
        int info;
        Nodo sig;
    }
    
    private Nodo raiz,fondo;
    
    Cola() {
        raiz=null;
        fondo=null;
    }
    
    boolean vacia (){
        if (raiz == null)
            return true;
        else
            return false;
    }

    void insertar (int info)
    {
        Nodo nuevo;
        nuevo = new Nodo ();
        nuevo.info = info;
        nuevo.sig = null;
        if (vacia ()) {
            raiz = nuevo;
            fondo = nuevo;
        } else {
            fondo.sig = nuevo;
            fondo = nuevo;
        }
    }

    int extraer ()
    {
        if (!vacia ())
        {
            int informacion = raiz.info;
            if (raiz == fondo){
                raiz = null;
                fondo = null;
            } else {
                raiz = raiz.sig;
            }
            return informacion;
        } else
            return Integer.MAX_VALUE;
    }

    public void imprimir() {
        Nodo reco=raiz;
        System.out.println("Listado de todos los elementos de la cola.");
        while (reco!=null) {
            System.out.print(reco.info+"-");
            reco=reco.sig;
        }
        System.out.println();
    }
        
    public static void main(String[] ar) {
        Cola cola1=new Cola();
        cola1.insertar(5);
        cola1.insertar(10);
        cola1.insertar(50);
        cola1.imprimir();
        System.out.println("Extraemos uno de la cola:"+cola1.extraer());
        cola1.imprimir();        
    }
}

CÓDIGO DE UNA LISTA
public class Pila {

    class Nodo {
        int info;
        Nodo sig;
    }

    private Nodo raiz;
    
    public Pila () {
        raiz=null;
    }
    
    public void insertar(int x) {
    Nodo nuevo;
        nuevo = new Nodo();
        nuevo.info = x;
        if (raiz==null)
        {
            nuevo.sig = null;
            raiz = nuevo;
        }
        else
        {
            nuevo.sig = raiz;
            raiz = nuevo;
        }
    }
    
    public int extraer ()
    {
        if (raiz!=null)
        {
            int informacion = raiz.info;
            raiz = raiz.sig;
            return informacion;
        }
        else
        {
            return Integer.MAX_VALUE;
        }
    }
    
    public void imprimir() {
        Nodo reco=raiz;
        System.out.println("Listado de todos los elementos de la pila.");
        while (reco!=null) {
            System.out.print(reco.info+"-");
            reco=reco.sig;
        }
        System.out.println();
    }
    
    public static void main(String[] ar) {
        Pila pila1=new Pila();
        pila1.insertar(10);
        pila1.insertar(40);
        pila1.insertar(3);
        pila1.imprimir();
        System.out.println("Extraemos de la pila:"+pila1.extraer());
        pila1.imprimir();        
    }

}

Estructura de datos no lineales: Las estructuras de datos no lineales se les llama 

también estructuras de datos multienlazadas. Cada elemento puede estar enlazado a cualquier otro componentes. Se trata de estructuras de datos en las que cada 
elemento puede tener varios sucesores y/o varios predecesores.

Árboles: Cada elemento sólo puede estar enlazado con su predecesor y sus sucesores. Puede tener varios sucesores

Bicola La bicola o doble cola es un tipo de cola especial que permiten la inserción y eliminación de elementos de ambos extremos de la cola.
Puede representarse a partir de un vector y dos índices, siendo su representación más frecuente una lista circular doblemente enlazada.
Todas las operaciones de este tipo de datos tienen coste constante.

Cola circular: Una cola circular o anillo es una estructura de datos en la que los elementos están de forma circular y cada elemento tiene un sucesor y un predecesor. Los elementos pueden consultarse, añadirse y eliminarse únicamente desde la cabeza del anillo que es una posición distinguida. Existen dos operaciones de rotaciones, una en cada sentido, de manera que la cabeza del anillo pasa a ser el elemento sucesor, o el predecesor, respectivamente, de la cabeza actual.

Cola estática 
import java.util.Vector;

public class Cola {

//private int inicio;
//private int fin;
private int size;
private Vector elementos;

public Cola() {
super();
elementos = new Vector();
//inicio = fin = 0;
size = 0;
}

public boolean colaVacia () {
//if ( (fin-inicio)==0) {
if ( size==0) {
return true;
}
return false;
}

public void encolar ( Tipo o ) {
//elementos.add(fin++, o);
elementos.add(size++, o);
}

public Tipo desencolar () {
Tipo retorno;

try {
if(colaVacia())
throw new ErrorColaVacia();
else {
//return elementos.get(inicio++);
retorno = elementos.get(0);
elementos.remove(0);
size--;
return retorno;
}
} catch(ErrorColaVacia error) {
System.out.println("ERROR: la cola esta vacía");
return null;
}
}

/*
public int getFin() {
return fin;
}

public int getInicio() {
return inicio;
}
*/
public int getSize() {
//return (fin-inicio);
return (size);
}
}

@SuppressWarnings("serial")
class ErrorColaVacia extends Exception {
public ErrorColaVacia() {
super();
}
}
[/JAVA]


[JAVA]
package colas;

public class Test {

@SuppressWarnings("unchecked")
public static void main(String[] args) {
Cola cola;

cola = new Cola();
System.out.println("Elementos en cola: " + cola.getSize());

cola.encolar("Uno");
System.out.println("Elementos en cola: " + cola.getSize());

cola.encolar("Dos");
System.out.println("Elementos en cola: " + cola.getSize());

System.out.println("Extraigo.........: " + cola.desencolar().toString());
System.out.println("Elementos en cola: " + cola.getSize());

cola.encolar("Tres");
System.out.println("Elementos en cola: " + cola.getSize());

System.out.println("Extraigo.........: " + cola.desencolar().toString());
System.out.println("Elementos en cola: " + cola.getSize());

System.out.println("Extraigo.........: " + cola.desencolar().toString());
System.out.println("Elementos en cola: " + cola.getSize());

System.out.println("Extraigo.........: " + cola.desencolar().toString());
System.out.println("Elementos en cola: " + cola.getSize());

}


}

Pila dinámica
package estructuradedatospilas;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
public class pilas {
     public static void main(String[] args) {
        Scanner leer = new Scanner (System.in);
        int num;
        int op;
        LinkedList pila = new LinkedList();
        do{
            System.out.println("\t menu \t");
            System.out.println("operaciones con pilas");
            System.out.println("1.-insertar al principio");
            System.out.println("2.-insertar al final");
            System.out.println("3.-borrar al final");
            System.out.println("4.-mostrar la pila");
            System.out.println("5.-salir");
            System.out.println("\n");
            System.out.println("elija la operacion que desee");
            op=leer.nextInt();
            switch (op){
                case 1:
                    System.out.println("inserte numero");
                    num=leer.nextInt();
                    pila.addFirst(num);
                    break;

                case 2:
                        System.out.println("inserte numero");
                        num=leer.nextInt();
                        pila.addLast(num);
                        break;


                case 3:
                    System.out.println("se borra el nodo final");
                    pila.removeLast();
                    break;

                case 4:
                    System.out.println("la pila es la siguiente");
                    List pila2= new ArrayList(pila);
                    Iterator it = pila2.iterator();
                    while (it.hasNext()){
                        System.out.println(it.next()+"");

                    }
                    break;
                    case 5:
                     System.out.println("al rato");
                     break;
            }
        }
        while (op !=5);   }         
   }