UNIDAD IV MÉTODOS DE ORDENAMIENTO

4.1 ALGORITMOS DE ORDENAMIENTO

Introducción

Ordenamiento

¿Qué es ordenamiento?

Es la operación que coloca los datos en un orden secuencial, basándose en un criterio de ordenamiento.
El ordenamiento se efectúa en base al valor del dato

¿Cuándo es conveniente usar un método de ordenamiento

1. Cuando se requiere hacer una cantidad considerable de búsquedas

 

  2.  Y cuando es importante el factor tiempo.

Tipos de ordenamiento

• Internos: 

Son aquellos en los que los valores a ordenar están en memoria principal, por lo que se asume que el tiempo que se requiere para acceder cualquier elemento sea el mismo (a[1], a[500], etc).

• Externos

Son aquellos en los que los valores a ordenar están en memoria secundaria (disco, cinta, cilindro magnético, etc), por lo que se asume que el tiempo que se requiere para acceder a cualquier elemento depende de la última posición accesada (posición 1, posición 500, etc).

Método Burbuja

Historia

Determinar con exactitud el origen del ordenamiento burbuja es un poco complicado, ya que no existe información precisa sobre su origen.

Aunque en 1956 se encuentra expresado en un artículo al que lo llamaron "Ordenamiento por intercambio".

Existe una amplia bibliografía de artículos del año 1962 donde mencionan tipos de ordenamiento basados en este patrón, pero ninguno de ellos usando el nombre como tal.

Ventajas 

• Bastante sencillo y más utilizado por su fácil comprensión y programación.
• Código reducido.
• Eficaz.

Desventajas

• Consume bastante tiempo de cálculo computarizado.
• Requiere de muchas lecturas/escrituras en memoria.

  Características

 

La ordenación de burbuja (Bubble Sort en inglés) es un sencillo algoritmo de ordenamiento. 

Funciona revisando cada elemento de la lista que va a ser ordenada con el siguiente, intercambiándolos de posición si están en el orden equivocado.

Es necesario revisar varias veces toda la lista hasta que no se necesiten más intercambios, lo cual significa que la lista está  ordenada.

Método de los más conocidos y más fáciles, pero a la ves es uno de los menos eficaces que se basa en la ordenación por intercambio de elementos. 

Código en Java

public class Burbuja {

    public static void main(String[] args) {

        int [] nums={34,25,13,24,8,1,11};

        int aux;

        for(int i=0; i<nums.length; i++)

        {

            for(int j=i+1;j<nums.length;j++)

            {

                if (nums[j]<nums[i])

                {

                    aux=nums[i];

                    nums[i]=nums[j];

                    nums[j]=aux;

                }

            }

        }

        System.out.println("El arreglo ordenado es:");

        for (int i=0; i<nums.length; i++)

        {

            System.out.println(nums[i]+"");

        }

    }

    

}

Esta es la corrida del programa.

Metodo Quick Sort

 (Ordenamiento Rápido) 

Es un algoritmo creado por el científico británico en computación C.A.R. Hoare, se basa en la técnica "Divide y vencerás", que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n.

Forma en que trabaja el algoritmo:

1-•Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote.

2-•Resituar los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos los menores que él, y al otro los mayores. 

3-•Se comparan para ver si el número pivote es mayor.

4-•Se vuelven a comparar para ver si es mayor el número pivote

5-•Este sigue siendo el número pivote.

6-La lista queda separada en dos sublistas, una formada por los elementos a la izquierda del pivote, y otra por los elementos a su derecha.

7-•Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados.

8-Elementos Ordenados.

Código en Java

public class quicksort {

    public static void main(String a[]){

  int i;

  int array[] = {12,9,4,99,120,1,3,10,13};

  System.out.println("    Quick Sort\n"); 

 System.out.println("Valores antes de QuickSort:\n");

 for(i = 0; i < array.length; i++)

    System.out.print( array[i]+"  ");

    System.out.println();

   quick_srt(array,0,array.length-1);

   System.out.print("\n\n\nValores despues de QuickSort:\n\n");

  for(i = 0; i <array.length; i++)

   System.out.print(array[i]+"  ");

    System.out.println();

             }

    public static void quick_srt(int array[],int low, int n){

            int lo = low; 

            int hi = n;

            if (lo >= n) {

            return;

            }

            int mid = array[(lo + hi) / 2];

            while (lo < hi) {

            while (lo<hi && array[lo] < mid) {

                  lo++;

             }

             while (lo<hi && array[hi] > mid) {

               hi--;

             }

             if (lo < hi) {

              int T = array[lo];

              array[lo] = array[hi];

              array[hi] = T;

              }

              }

               if (hi < lo) {

               int T = hi;

               hi = lo;

               lo = T;

             }

               quick_srt(array, low, lo);

               quick_srt(array, lo == low ? lo+1 : lo, n);

             }

 }

Corrida del programa

Donald Shell

Método Shell sort

Se denomina “SHELL” en honor a su inventor Donald Shell. .

Es un algoritmo de ordenación interna muy sencillo pero muy ingenioso, basado en comparaciones e intercambios, y con unos resultados radicalmente mejores que los que se pueden obtener con el método de la burbuja, el de selección directa o el de inserción directa.




El Shell sort es una generalización del ordenamiento por inserción, teniendo en cuenta dos observaciones:

1.El ordenamiento por inserción es eficiente si la entrada está "casi ordenada".

2.El ordenamiento por inserción es ineficiente, en general, porque mueve los valores sólo una posición cada vez.

Ventajas

• No requiere memoria adicional. 
• Mejor rendimiento que el método de inserción rápido. 
• Fácil implementación.

Desventajas

• Su funcionamiento puede resultar confuso 
• Suele ser un poco lento. 
• Realiza numerosas comparaciones e intercambios.

Pasos para el ordenamiento shell sort

1. Obtener n. 
2. Obtener k ( k=n/2) 3.Clarificar cada grupo por separado, comparando las parejas de elementos y si no están ordenados se intercambian 
3. N se divide entre 2 y se vuelve a obtener k. 
4. Nuevamente se clasifica cada grupo por separado. 
5. El algoritmo termina cuando el tamaño de k es igual a 1.

Código en Java

public class shell_sort {

    

    public static void shellSort( int b[ ])

    { 

for(int k= b.length/2; k>0; k=k==2?1:(int)( k/2.2))

{ 

      for(int i=k;i<b.length; i++ )

      { 

        int tmp =b[i]; 

        int j; 

        for(j=i; j>=k&&tmp<b[j-k]; j-=k)

        { 

          b[j]=b[j-k]; 

        } 

        b[j]=tmp; 

     } 

} 

    } 

public static void main(String args[]){ 

int a[]={321, 6, 1, 234, 213, 4, 5, 123}; //Este es el array de elementos que vamos a ordenar 

    System.out.println("Antes del ordenamiento");

for(int i=0;i<a.length;i++)

{

    System.out.print(a[i]+" ");

    

}

shellSort(a); //llamada al metodo shellSort 

    System.out.println("\n");

System.out.println("Ordenado por el método Shell");

for (int i=0;i < a.length;i++){ //Este bucle imprime el contenido del array 

    

    System.out.print(a[i]+" "); 

}//fin del for 

}//fin del main 

}//class ShellSort

Corrida del programa

Método Radix

En informática, el ordenamiento Radix (radix sort en inglés) es un algoritmo de ordenamiento que ordena enteros procesando sus dígitos de forma individual. Como los enteros pueden representar cadenas de caracteres (por ejemplo, nombres o fechas) y, especialmente, números en punto flotante especialmente formateados, radix sort no está limitado sólo a los enteros.

Descripción

Las representaciones de enteros que son procesadas por los algoritmos de ordenamiento se les llama a menudo "claves", que pueden existir por sí mismas o asociadas a otros datos. Radix sort LSD usa típicamente el siguiente orden: claves cortas aparecen antes que las claves largas, y claves de la misma longitud son ordenadas de forma léxica. Esto coincide con el orden normal de las representaciones de enteros, como la secuencia "1, 2, 3, 4, 5, 6, 7, 8, 9, 10". Radix sorts MSD usa orden léxico, que es ideal para la ordenación de cadenas de caracteres, como las palabras o representaciones de enteros de longitud fija. Una secuencia como "b, c, d, e, f, g, h, i, j, ba" será ordenada léxicamente como "b, ba, c, d, e, f, g, h, i, j". Si se usa orden léxico para ordenar representaciones de enteros de longitud variable, entonces la ordenación de las representaciones de los números del 1 al 10 será "1, 10, 2, 3, 4, 5, 6, 7, 8, 9", como si las claves más cortas estuvieran justificadas a la izquierda y rellenadas a la derecha con espacios en blanco, para hacerlas tan largas como la clave más larga, para el propósito de este ordenamiento.

Ejemplo

Vector original:

25 57 48 37 12 92 86 33

Asignamos los elementos en colas basadas en el dígito menos significativo de cada uno de ellos.0:
1:
2:12 92
3:33
4:
5:25
6:86
7:57 37
8:48
9:


Después de la primera pasada, la ordenación queda:

12 92 33 25 86 57 37 48

Colas basadas en el dígito más significativo.0:
1:12
2:25
3:33 37
4:48
5:57
6:
7:
8:86
9:92


Lista ordenada:

12 25 33 37 48 57 86 92

4.2 Métodos de Búsqueda

Método de búsqueda Secuencial

Se utiliza cuando el vector no está ordenado o no puede ser ordenado previamente. Consiste en buscar el elemento comparándolo secuencialmente (de ahí su nombre) con cada elemento del arreglo hasta encontrarlo, o hasta que se llegue al final. La existencia se puede asegurar cuando el elemento es localizado, pero no podemos asegurar la no existencia hasta no haber analizado todos los elementos del arreglo. A continuación se muestra el pseudocódigo del algoritmo:[cita requerida].

Pasos de la Búsqueda Secuencial:

1.Consiste en recorrer el arreglo elemento a elemento e ir comparando con el valor buscado.

2.Se empieza con la primera casilla del arreglo y se observa una casilla tras otra hasta que se encuentra el elemento buscado o se han visto todas las casillas.

3.El resultado de la búsqueda es un solo valor, y será la posición del elemento buscado o cero.

4.El método de búsqueda lineal funciona bien con arreglos pequeños o para arreglos no ordenados.

 

Ejemplo:

int busquedaSimple(int vector[], int n, int dato) { 

 int i; 

 for(i=0; i<n; i++)

{ 

       if(dato==vector[i]) 

     { 

          return i; 

       } 

 }

 return -1; 

 }

Método de búsqueda Binaria

Se utiliza cuando el vector en el que queremos determinar la existencia de un elemento está previamente ordenado. Este algoritmo reduce el tiempo de búsqueda considerablemente, ya que disminuye exponencialmente el número de iteraciones necesarias.

Está altamente recomendado para buscar en arrays de gran tamaño. Por ejemplo, en uno conteniendo 50.000.000 elementos, realiza como máximo 26 comparaciones (en el peor de los casos).

Para implementar este algoritmo se compara el elemento a buscar con un elemento cualquiera del array (normalmente el elemento central): si el valor de éste es mayor que el del elemento buscado se repite el procedimiento en la parte del array que va desde el inicio de éste hasta el elemento tomado, en caso contrario se toma la parte del array que va desde el elemento tomado hasta el final. De esta manera obtenemos intervalos cada vez más pequeños, hasta que se obtenga un intervalo indivisible. Si el elemento no se encuentra dentro de este último entonces se deduce que el elemento buscado no se encuentra en todo el array.


Ventajas:

• La búsqueda binaria es un método eficiente siempre que el vector esté ordenado.
• La búsqueda binaria proporciona un medio para reducir el tiempo requerido para buscar en una lista.
• Este método funciona a un 100% 

Desventajas:

• Si los datos del arreglo no están ordenados no hará la búsqueda
• Este método Necesita un método de ordenamiento como: Burbuja, Quicksort, shell sort, etc. Para que así funcione bien.

Código en Java

public class secuencialdesordenado {
public void buscar()
{
Scanner leer=new Scanner(System.in);
int i=0;
boolean bandera=false;
int x;
int v[]= new int[10];
for(int c=0;c<v.length;c++)
{
System.out.println("introduce los datos del arreglo");
v[c]=leer.nextInt();
}
System.out.println("introduzca elemento a buscar");
x=leer.nextInt();


do{
if(v[i]==x)
{
bandera=true;
}
else {
bandera=false;
}
i++;
}while(i<v.length && bandera==false);

if(bandera==true)
{
System.out.println("el elemento esta en la posicion "+ i);
}
else if(bandera==false)
{
System.out.println("el elemento no esta en la lista");
}
}

UNIDAD III: ESTRUCTURAS NO LINEALES

Árboles

Definición

un árbol es una estructura de datos ampliamente usada que imita la forma de un árbol (un conjunto de nodos conectados). Un nodo es la unidad sobre la que se construye el árbol y puede tener cero o más nodos hijos conectados a él. Se dice que un nodo  "a" es padre de un nodo "b" si existe un enlace desde "a" hasta "b" (en ese caso, también decimos que "b" es hijo de "a"). Sólo puede haber un único nodo sin padres, que llamaremos raíz. Un nodo que no tiene hijos se conoce como hoja. Los demás nodos (tienen padre y uno o varios hijos) se les conoce como rama.

Propiedades:

GRADO: Número de descendientes directos de un determinado nodo.

GRADO DE ÁRBOL: Es el máximo grado de todos los nodos del árbol.

NIVEL: Es el número de arcos que pueden ser recorridos para llegar a un determinado nodo.

Por definición Raíz tiene nivel = 1.

Dado el sig. árbol determine: Raíz, hijos, padres, hermanos, grado, nivel y altura del árbol.

Raíz = A

A= Padre de B y C.

B= Hijo de A, Hermano de C, Padre de D & E.

C= Hijo de A, Hermano de B, padre de E & F.

D= Hijo de B, Hermano de  E, no tiene Hijos, se le considera Hoja.

E= Hijo de B, Hermano de D, no tiene Hijos, se le considera Hoja.

F= Hijo de C, Hermano de G, no tiene Hijos, se le considera Hoja.

Nivel de árbol:

El nodo A está en el nivel 1 sus descendientes directos están en el nivel 2 y así sucesivamente.
El nivel del árbol está dado por el nodo de máximo nivel.

Grado de nodo: es el número de nodos hijos que tiene dicho nodo
Ej. El nodo A tiene grado 2.
El nodo B tiene grado 2.
Nota: Los nodos sin hijos no tienen grado.

Grado de un árbol: Es el máximo de los grados de todos los nodos de un árbol.
Ej. El grado del árbol es 2.

Operaciones de árboles.

Las operaciones comunes en árboles son:

• Enumerar todos los elementos.
• Buscar un elemento.
• Dado un nodo, listar los hijos (si los hay).
• Borrar un elemento.
• Eliminar un subárbol (algunas veces llamada podar).
• Añadir un subárbol (algunas veces llamada injertar).
• Encontrar la raíz de cualquier nodo.

Longitud de camino interno:

Definición
Es la suma de longitudes de camino de todos los nodos del árbol.

h

LCI=Σni * i

i=1

i=nivel del árbol
h=altura
ni=número de nodos en el nivel i
Lci=número de nivel*número de nodos+número de nivel*número de nodos...
Ejemplo: (1*1+2*2+4*3+4*4=33)

Árbol extendido:

Aquel en el que el número de hijos de cada nodo es igual al grado del árbol, que no cumplir con esta característica se deben incorporar nodos especiales.

Nodos especiales:
Reemplazan las ramas vacías o nulas.

Longitud de camino Externo:
Es la suma de todos los nodos especiales.

Formula:

h+1

LCE=Σnei* i i=2




i=Nivel del árbol
h=altura
nei=número de nodos especiales

Árboles Binarios

Es un árbol ordenado en el cual cada nodo puede tener como máximo 2 subárboles.

>> Estructura homogénea, resultado de la concatenación de un elemento de tipo T, llamado Raíz, con 2 árboles disjuntos llamados Subárbol iquierdo y Subárbol derecho.

Árbol General - Árbol Binario

Nota: Éste no es un árbol Binario porque "B" tiene 3 hijos.

Pasos a seguir para convertir un Árbol General a Binario:

1. Enlazar los hijos de cada nodo en forma horizontal las raíces de los distintos arboles generales. 
2. Relacionar los hijos de cada nodo (los hermanos en forma horizontal).
3. Enlazar en forma vertical el nodo Padre con el hijo que se muestra mas a la izquierda . Además se debe eliminar el vinculo del padre con el resto de sus hijos.
4. Rotar el diagrama resultante aproximadamente 45 grados hacia la izquierda y así obtendrá un árbol binario correspondiente.

Bosques

Representa un conjunto normalmente ordenado de uno o más árboles.

Conversión a Árbol Binario:

1. Enlazar en forma horizontal las raíces de los distintos árboles generales.
2. Relacionar los hijos de cada nodo (los hermanos) en forma horizontal.
3. Enlazar en forma vertical el nodo padre con el hijo que se encuentra más a la izquierda. Además se debe eliminar el vínculo del padre con el resto de sus hijos.
4. Rotar el diagrama 45° grados aprox. hacia la izquierda y así obtendrá el árbol binario correspondiente.

Resultado:

Recorridos

Preorden: (raíz, izquierdo, derecho). Para recorrer un árbol binario no vacío en preorden, hay que realizar las siguientes operaciones recursivamente en cada nodo, comenzando con el nodo de raíz:

• Visite la raíz
• Atraviese el sub-árbol izquierdo  
• Atraviese el sub-árbol derecho

Inorden: (izquierdo, raíz, derecho). Para recorrer un árbol binario no vacío en inorden (simétrico), hay que realizar las siguientes operaciones recursivamente en cada nodo:

• Atraviese el sub-árbol izquierdo
• Visite la raíz
• Atraviese el sub-árbol derecho

Postorden: (izquierdo, derecho, raíz). Para recorrer un árbol binario no vacío en postorden, hay que realizar las siguientes operaciones recursivamente en cada nodo:
Atraviese el sub-árbol izquierdo
Atraviese el sub-árbol derecho
Visite la raíz

Programa de árbol Binario en Java.

public class Arbol {
    class Nodo
    {
        int info;
        Nodo izq, der;
    }
    Nodo raiz;
    int cant;
    int altura;
    public Arbol() {
        raiz=null;
    }
    public void insertar (int info) {
        if (!existe(info)) {
            Nodo nuevo;
            nuevo = new Nodo ();
            nuevo.info = info;
            nuevo.izq = null;
              nuevo.der = null;
            if (raiz == null)
                raiz = nuevo;
            else {
                Nodo anterior = null, reco;
                reco = raiz;
                while (reco != null)  {
                    anterior = reco;
                    if (info < reco.info)
                        reco = reco.izq;
                    else
                        reco = reco.der;
                }
                if (info < anterior.info)
                    anterior.izq = nuevo;
                else
                    anterior.der = nuevo;
            }
        }
    }
    public boolean existe(int info) {
        Nodo reco=raiz;
        while (reco!=null) {
            if (info==reco.info)
                return true;
            else
                if (info>reco.info)
                    reco=reco.der;
                else
                    reco=reco.izq;
        }
        return false;
    }
    private void imprimirEntre (Nodo reco)  {
        if (reco != null)  {
            imprimirEntre (reco.izq);
            System.out.print(reco.info + " ");
            imprimirEntre (reco.der);
        }
    }
    public void imprimirEntre () {
        imprimirEntre (raiz);
        System.out.println();
    }

    private void cantidad(Nodo reco) {
        if (reco!=null) {
            cant++;
            cantidad(reco.izq);
            cantidad(reco.der);
        }
    }
    public int cantidad() {
        cant=0;
        cantidad(raiz);
        return cant;
    }
    private void cantidadNodosHoja(Nodo reco) {
        if (reco!=null) {
            if (reco.izq==null && reco.der==null)
                cant++;
            cantidadNodosHoja(reco.izq);
            cantidadNodosHoja(reco.der);
        }
    }
    public int cantidadNodosHoja() {
        cant=0;
        cantidadNodosHoja(raiz);
        return cant;
    }
    private void imprimirEntreConNivel (Nodo reco,int nivel)  {
        if (reco != null) {
            imprimirEntreConNivel (reco.izq,nivel+1);
            System.out.print(reco.info + " ("+nivel+") - ");
            imprimirEntreConNivel (reco.der,nivel+1);
        }
    }
    public void imprimirEntreConNivel () {
        imprimirEntreConNivel (raiz,1);
        System.out.println();
    }
    private void retornarAltura (Nodo reco,int nivel)    {
        if (reco != null) {
            retornarAltura (reco.izq,nivel+1);
            if (nivel>altura)
                altura=nivel;
            retornarAltura (reco.der,nivel+1);
        }
    }
    public  int retornarAltura () {
        altura=0;
        retornarAltura (raiz,1);
        return altura;
    }
    public void mayorValorl() {
        if (raiz!=null) {
            Nodo reco=raiz;
            while (reco.der!=null)
                reco=reco.der;
            System.out.println("Mayor valor del įrbol:"+reco.info);
        }
    }
    public void borrarMenor() {
        if (raiz!=null) {
            if (raiz.izq==null)
                raiz=raiz.der;
            else {
                Nodo atras=raiz;
                Nodo reco=raiz.izq;
                while (reco.izq!=null) {
                    atras=reco;
                    reco=reco.izq;
                }
                atras.izq=reco.der;
            }
        }
    }
    public static void main (String [] ar)
    {
        Arbol abo = new Arbol ();
        abo.insertar (100);
        abo.insertar (50);
        abo.insertar (25);
        abo.insertar (75);
        abo.insertar (150);
        System.out.println ("Impresion entreorden: ");
        abo.imprimirEntre ();
        System.out.println ("Cantidad de nodos del įrbol:"+abo.cantidad());
        System.out.println ("Cantidad de nodos hoja:"+abo.cantidadNodosHoja());
        System.out.println ("Impresion en entre orden junto al nivel del nodo.");
        abo.imprimirEntreConNivel();
        System.out.print ("Artura del arbol:");
        System.out.println(abo.retornarAltura());
        abo.mayorValorl();
        abo.borrarMenor();
        System.out.println("Luego de borrar el menor:");
        abo.imprimirEntre ();
    }
}

UNIDAD II: ESTRUCTURAS LINEALES

2.1 Listas

Concepto:

Consiste en una secuencia de nodos, en los que se guardan campos de datos arbitrarios y una o dos referencias, enlaces o punteros al nodo anterior o posterior.

 Ejemplo.

Listas enlazadas: Son colecciones de elementos de información “formados en la fila”. Se hacen inserciones o eliminaciones por cualquier lugar de la lista.

2.2 Pilas estáticas y dinámicas

 Es una lista ordenada en la que el modo de acceso a sus elementos es de tipo Last In First Out, último en entrar, primero en salir) que permite almacenar y recuperar datos.

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.

1. Crear: se crea la pila vacía. (constructor)
2. Tamaño: regresa el número de elementos de la pila. (size)
3. Apilar: se añade un elemento a la pila.(push)
4. Desapilar: se elimina el elemento frontal de la pila.(pop)
5. Cima: devuelve el elemento que esta en la cima de la pila. (top o peek)
6. Vacía: devuelve cierto si la pila está vacía o falso en caso contrario (empty).

Ejemplo en Java de Pila Estática.

package PILA;

import java.util.Scanner;
public class PilaEstatatica {
public static int op;
public static int tope;
    int pila[]= new int[10];
    public void insertar(){
        if(tope==10)
            System.out.println("Pila llena");
        else
    {
       for(int i=0;i<pila.length;i++ ){
        System.out.println("Proporciona el dato para la pila");
        System.out.println("dato " + tope);
        Scanner cap= new Scanner(System.in);
        pila[tope]=cap.nextInt();
        tope++;
    } }
}
    public void imprimir(){
        if(tope!=0){
            for(int topeL=tope-1;topeL>=0;topeL--){
                System.out.println("\n\n" + pila [topeL]);
            }
        }
        else
            System.err.println("Pila vacia no hay nada que mostrar");
    }
    public void eliminar(){
        if(tope<0){
            System.out.println("Pila vacia");
        }
        else
            if(tope==10){//Esto se usa cuando la pila esta totalmente llena,
                //ya que se incremento en insertar y quedo en 10, de lo contrario
                //noz arrojara un error de array
                tope--;
                pila[tope]=0;
                tope--;//se vuelve a decrementar para que este en la pocision correcta,porque
                //tenia un numero de mas
            }
            else{
            pila[tope]=0;
            tope--;
            }     
    }
    public static void main(String[] args) {
       PilaEstatatica p = new PilaEstatatica();
       String r;
       Scanner cap1=new Scanner(System.in);
       Scanner cap=new Scanner(System.in);
       tope=0;
       do{
           System.out.println("Menu principal:\n¿Qué desea hacer con la pila?");
           System.out.println("1.-Insertar elemento");
           System.out.println("2.- Eliminar elemento");
           System.out.println("3.- Imprimir Pila");
           System.out.println("4.-Salir");
           op=cap.nextInt();
           switch(op){
               case 1: p.insertar();break;
               case 2:if(tope==10)
                   p.eliminar();
               else
                       System.out.println("No hay nada que eliminar :) ");
                   break;
               case 3:p.imprimir();break;
               case 4:break;
               default:
                   System.out.println("Opcion no valida, vuelva a intentarlo");break;
           }
    }while(op!=4);

}
}

Ejemplo de Pila dinámica en Java

package PILA;
import java.util.*;
public class PilaDinamica {
    public static void main(String[] args) {
        Scanner leer =new Scanner(System.in);
        int num;
        int op;
        LinkedList lista = new LinkedList();
        do{
            System.out.println("\t Menuº \t");
            System.out.println("Operaciones con pilas");
            System.out.println("1.- Insertar");
            System.out.println("2.- Borrar");
            System.out.println("3.- Mostrar la pila");
            System.out.println("4.- Salir");
            System.out.println("\n");
            System.out.println("Elija la operación que desee");
            op =leer.nextInt();
            switch(op){
            case 1:
                System.out.println("Inserte Numero");
                num =leer.nextInt();
                lista.addLast(num);
                break;
            case 2:
                System.out.println("Se borrará el nodo final");
                lista.removeFirst();
                break;
            case 3:
                System.out.println("La lista es la siguiente");
                 List lista2 = new ArrayList (lista);
                 Iterator it = lista2.iterator();//añade otro nodo ,es un ciclo
                 //sirve para recorrer la lista
                 while (it.hasNext()){
                     System.out.println(it.next() + "");
                 }
                 break;
            case 4:
                System.out.println("Al rato");
                break;
            }
        }
        while(op != 4);
    }
}

Expresiones Aritméticas

Cuando se agrupan varios números u operaciones, es importante conocer el orden o jerarquía en que deben resolverse para obtener un resultado correcto.

Ejemplo:

Para resolver 3 x 6 + 4.
Podría interpretarse como: 3 x (6 + 4) = 3 x 10 = 30.
O bien, como: (3 x 6) + 4 = 18 + 4 = 22.
De igual manera, 8 x 3 + 5 se podría interpretar como:
8 x (3 + 5) = 8 x 8 = 64 o también como (8 x 3) + 5 = 24 + 5 = 29.
¿Cuáles serían los resultados correctos?

Para evitar confusiones y errores se ha convenido en que cuando no hay paréntesis, dado que los signos + y – separan cantidades, se efectúan las operaciones en el siguiente orden:
Potencias
Multiplicaciones
Divisiones
Adiciones
Sustracciones

Por tanto, retomando los ejemplos del principio:

3 x 6 + 4 = 18 + 4 = 22

8 x 3 + 5 = 24 + 5 = 29

Esto es importante, sobre todo cuando se manejan fórmulas de geometría o de cualquier otra ciencia.

Notación Infija

La notación de infija es la notación común de fórmulas aritméticas y lógicas, en la cual se escriben los operadores entre los operandos.

Ejemplo:

Notación Infija.

Notación Posfija

La notación  notación posfija, , es un método algebraico alternativo de introducción de datos, en donde primero están los operandos y después viene el operador que va a realizar los cálculos sobre ellos. 

Ejemplo:

Notación Prefija

La notación prefija, es una forma de notación para la lógica, la aritmética, y el álgebra. Su característica distintiva es que coloca los operadores a la izquierda de sus operandos.

Ejemplo:

2.3 Colas estáticas y dinámicas

Concepto:

Una cola constituye una estructura lineal de datos en la que los nuevos elementos se

introducen por un extremo y los ya existentes se eliminan por el otro. Es importante

señalar que los componentes de la cola se eliminan en el mismo orden en el cual se

insertaron. Es decir, el primer elemento que se introduce en la estructura será el que

se eliminará en primer orden. Debido a esta característica, las colas también reciben el

nombre de estructuras FIFO (First-In, First-Out: el primero en entrar es el primero en

salir).

Existen numerosos casos de la vida real en los cuales se usa este concepto. Por ejemplo,

la cola de los bancos en las que los clientes esperan para ser atendidos -;..

primera persona de la cola será la primera en recibir el servicio-, la cola de los niño.

que esperan a veces pacientemente para subir a un juego mecánico, las colas de 1 vehículos

esperando la luz verde del semáforo, las colas para entrar a un cine, teatro'

estadio de fútbol, etcétera.

Representación de colas

Las colas, al igual que las pilas, no existen como estructuras de datos estándar en lo

lenguajes de programación. Este tipo de estructura de datos se puede representar mediante

el uso de:

• Arreglos

• Listas'

Operaciones Básicas

• Crear: se crea la cola vacía.
• Encolar (añadir, entrar, insertar): se añade un elemento a la cola. Se añade al final de esta.
• Desencolar (sacar, salir, eliminar): se elimina el elemento frontal de la cola, es decir, el primer elemento que entró.
• Frente (consultar, front): se devuelve el elemento frontal de la cola, es decir, el primer elemento que entró.

Tipos de colas

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 de Prioridad

Una cola de prioridades es una estructura de datos en la que los elementos se atienden en el orden indicado por una prioridad asociada a cada uno. Si varios elementos tienen la misma prioridad, se atenderán de modo convencional según la posición que ocupen

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.

Ejemplo en Java de Pila Estática.

Package COLA;

import.java.util.Scanner;

public class ColaEstatica {

public static int op;

public static int tope;

    int cola[]= new int[10];

    public void insertar(){

        if(tope==10)

            System.out.println("Cola llena");

        else

    {

       for(int i=0;i<cola.length;i++ ){

        System.out.println("Proporciona el dato para la Cola");

        System.out.println("dato " + tope);

        Scanner cap= new Scanner(System.in);

        cola[tope]=cap.nextInt();

        tope++;

    } }

}

    public void imprimir(){

       if(tope>0){

            for(int topeL=0;topeL<10;topeL++){

                System.out.println("\n\n" + cola [topeL]);

                System.out.println(tope);

            }

        }

        else

            System.err.println("cola vacia no hay nada que mostrar");

    }

    public void eliminar(){

        if(tope<0){

            System.out.println("cola vacia");

        }

        else

                for(int topeL=0;topeL<10;topeL++){

                     cola[topeL]=0;

            }

            }

    public static void main(String[] args) {

       ColaEstatica p = new ColaEstatica();

       String r;

       Scanner cap1=new Scanner(System.in);

       Scanner cap=new Scanner(System.in);

       tope=0;

       do{

           System.out.println("Menu principal:\n¿Que desea hacer con la pila?");

           System.out.println("1.-insertar");

           System.out.println("2.- eliminar");

           System.out.println("3.- imprimir");

           System.out.println("4.-salir");

           op=cap.nextInt();

           switch(op){

               case 1: p.insertar();break;

               case 2:p.eliminar();break;

               case 3:p.imprimir();break;

               case 4:break; default:

                   System.out.println("opcion no valida");break;

           }

    }while(op!=4);

}}