algoritmo de busqueda radix sort

concepto

Es un algoritmo 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.

descripcion
Este método se puede considerar como una generalización de la clasificación por urnas.
Consiste en hacer diversos montones de fichas, cada uno caracterizado por tener en sus componentes un mismo digito (letra si es alfabética) en la misma posición; estos montones se recogen en orden ascendente y se reparte en montones según el siguiente digito de la clave.

clasificacion
el de dígito menos significativo (LSD)
el de dígito más significativo (MSD).
Radix sort LSD procesa las representaciones de enteros empezando por el dígito menos significativo y moviéndose hacia el dígito más significativo.
Radix sort MSD trabaja en sentido contrario.
el de dígito menos significativo (LSD)
el de dígito más significativo (MSD).
Radix sort LSD procesa las representaciones de enteros empezando por el dígito menos significativo y moviéndose hacia el dígito más significativo.
Radix sort MSD trabaja en sentido contrario.
Este método se puede considerar como una generalización de la clasificación por urnas.
Consiste en hacer diversos montones de fichas, cada uno caracterizado por tener en sus componentes un mismo digito (letra si es alfabética) en la misma posición; estos montones se recogen en orden ascendente y se reparte en montones según el siguiente digito de la clave.

clasificacion
el de dígito menos significativo (LSD)
el de dígito más significativo (MSD).
Radix sort LSD procesa las representaciones de enteros empezando por el dígito menos significativo y moviéndose hacia el dígito más significativo.
Radix sort MSD trabaja en sentido contrario.
el de dígito menos significativo (LSD)
el de dígito más significativo (MSD).
Radix sort LSD procesa las representaciones de enteros empezando por el dígito menos significativo y moviéndose hacia el dígito más significativo.
Radix sort MSD trabaja en sentido contrario.



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: 485: 57

6:

7:

8: 86

9: 92

Lista ordenada:

12 25 33 37 48 57 86 92

caracteristicas de los algoritmos

Características de los Algoritmos:
Las características fundamentales que debe cumplir todo algoritmo son:
·Un algoritmo debe ser preciso e indicar el orden de realización de cada paso.
·Un algoritmo debe estar definido. Si se sigue un algoritmo dos veces, se debe obtener el mismo resultado cada vez.
·Un algoritmo debe ser finito. Si se sigue un algoritmo se debe terminar en algún momento; o sea, debe tener un numero finito de pasos.
La definición de un algoritmo debe definir tres partes: Entrada, Proceso y Salida. En el algoritmo de receta de cocina citado anteriormente se tendrá:
Entrada: ingrediente y utensilios empleados.
Proceso: elaboración de la receta en la cocina.
Salida: terminación del plato (por ejemplo, cordero).
Ejemplo de Algoritmo:
Un cliente ejecuta un pedido a una fábrica. Esta examina en su banco de datos la ficha del cliente; si el cliente es solvente entonces la empresa acepta el pedido; en caso contrario rechazara el pedido

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

1.Carácter finito. "Un algoritmo siempre debe terminar después de un número finito de pasos".
2.Precisión. "Cada paso de un algoritmo debe estar precisamente definido; las operaciones a llevar a cabo deben ser especificadas de manera rigurosa y no ambigua para cada caso".
3.Entrada. "Un algoritmo tiene cero o más entradas: cantidades que le son dadas antes de que el algoritmo comience, o dinámicamente mientras el algoritmo corre. Estas entradas son tomadas de conjuntos específicos de objetos".
4.Salida. "Un algoritmo tiene una o más salidas: cantidades que tienen una relación específica con las entradas".
5.Eficacia. "También se espera que un algoritmo sea eficaz, en el sentido de que todas las operaciones a realizar en un algoritmo deben ser suficientemente básicas como para que en principio puedan ser hechas de manera exacta y en un tiempo finito por un hombre usando lápiz y papel".

bibliografia
algoritmos
caracteristicas

grafos

Un grafo es un conjunto, no vacío, de objetos llamados vértices (o nodos) y una selección de pares de vértices, llamados aristas (edges en inglés) que pueden ser orientados o no. Típicamente, un grafo se representa mediante una serie de puntos (los vértices) conectados por líneas (las aristas).

vertices
Los vértices constituyen uno de los dos elementos que forman un grafo. Como ocurre con el resto de las ramas de las matemáticas, a la Teoría de Grafos no le interesa saber qué son los vértices.
Diferentes situaciones en las que pueden identificarse objetos y relaciones que satisfagan la definición de grafo pueden verse como grafos y así aplicar la Teoría de Grafos en ellos.

Aristas dirigidas y no dirigidas

En algunos casos es necesario asignar un sentido a las aristas, por ejemplo, si se quiere representar la red de las calles de una ciudad con sus direcciones únicas. El conjunto de aristas será ahora un subconjunto de todos los posibles pares ordenados de vértices, con (a, b) ≠ (b, a). Los grafos que contienen aristas dirigidas se denominan grafos orientados, como el siguiente:
Las aristas no orientadas se consideran bidireccionales para efectos prácticos (equivale a decir que existen dos aristas orientadas entre los nodos, cada una en un sentido).
En el grafo anterior se ha utilizado una arista que tiene sus dos extremos idénticos: es un lazo (o bucle), y aparece también una arista bidireccional, y corresponde a dos aristas orientadas.
Aquí V = { a, b, c, d, e }, y A = { (a, c), (d, a), (d, e), (a, e), (b, e), (c, a), (c, c), (d, b) }.
Se considera la característica de "grado" (positivo o negativo) de un vértice v (y se indica como (v)), como la cantidad de aristas que llegan o salen de él; para el caso de grafos no orientados, el grado de un vértice es simplemente la cantidad de aristas incidentes a este vértice. Por ejemplo, el grado positivo (salidas) de d es 3, mientras que el grado negativo (llegadas) de d es 0.
Según la terminología seguida en algunos problemas clásicos de Investigación Operativa (p.ej.: el Problema del flujo máximo), a un vértice del que sólo salen aristas se le denomina fuente (en el ejemplo anterior, el vértice d); tiene grado negativo 0. Por el contrario, a aquellos en los que sólo entran aristas se les denomina pozo o sumidero (en el caso anterior, el vértice e); tiene grado positivo 0. A continuación se presentan las implementaciones en maude de grafos no dirigidos y de grafos dirigidos.En los dos casos, las especificaciones incluyen, además de las operaciones generadoras, otras operaciones auxiliares.

Ciclos y caminos hamiltonianos
Un ciclo es una sucesión de aristas adyacentes, donde no se recorre dos veces la misma arista, y donde se regresa al punto inicial. Un ciclo hamiltoniano tiene además que recorrer todos los vértices exactamente una vez (excepto el vértice del que parte y al cual llega).
Por ejemplo, en un museo grande (al estilo del Louvre), lo idóneo sería recorrer todas las salas una sola vez, esto es buscar un ciclo hamiltoniano en el grafo que representa el museo (los vértices son las salas, y las aristas los corredores o puertas entre ellas).
Se habla también de camino hamiltoniano si no se impone regresar al punto de partida, como en un museo con una única puerta de entrada. Por ejemplo, un caballo puede recorrer todas las casillas de un tablero de ajedrez sin pasar dos veces por la misma: es un camino hamiltoniano. Ejemplo de un ciclo hamiltoniano en el grafo del dodecaedro.
Hoy en día, no se conocen métodos generales para hallar un ciclo hamiltoniano en tiempo polinómico, siendo la búsqueda por fuerza bruta de todos los posibles caminos u otros métodos excesivamente costosos. Existen, sin embargo, métodos para descartar la existencia de ciclos o caminos hamiltonianos en grafos pequeños.
El problema de determinar la existencia de ciclos hamiltonianos, entra en el conjunto de los NP-completos.

Grafos simples
Un grafo es simple si hay sólo 1 arista QUE une dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única que une dos vértices específicos.
Un grafo que no es simple se denomina Multigráfica o Gráfo múltiple.

 Grafos conexos
Un grafo es conexo si cada par de vértices está conectado por un camino; es decir, si para cualquier par de vértices (a, b), existe al menos un camino posible desde a hacia b.
Un grafo es doblemente conexo si cada par de vértices está conectado por al menos dos caminos disjuntos; es decir, es conexo y no existe un vértice tal que al sacarlo el grafo resultante sea disconexo.
Es posible determinar si un grafo es conexo usando un algoritmo Búsqueda en anchura (BFS) o Búsqueda en profundidad (DFS).

En términos matemáticos la propiedad de un grafo de ser (fuertemente) conexo permite establecer con base en él una relación de equivalencia para sus vértices, la cual lleva a una partición de éstos en "componentes (fuertemente) conexas", es decir, porciones del grafo, que son (fuertemente) conexas cuando se consideran como grafos aislados. Esta propiedad es importante para muchas demostraciones en teoría de grafos.

Grafos ponderados o etiquetados

En muchos casos, es preciso atribuir a cada arista un número específico, llamado valuación, ponderación o coste según el contexto, y se obtiene así un grafo valuado.
Formalmente, es un grafo con una función v: A → R₊.
Por ejemplo, un representante comercial tiene que visitar n ciudades conectadas entre sí por carreteras; su interés previsible será minimizar la distancia recorrida (o el tiempo, si se pueden prever atascos). El grafo correspondiente tendrá como vértices las ciudades, como aristas las carreteras y la valuación será la distancia entre ellas.
Y, de momento, no se conocen métodos generales para hallar un ciclo de valuación mínima, pero sí para los caminos desde a hasta b, sin más condición.

bibliografia

grafos

arboles

tipos de recorrido

Recorrido en preorden
En este tipo de recorrido se realiza cierta acción (quizás simplemente imprimir por pantalla el valor de la clave de ese nodo) sobre el nodo actual y posteriormente se trata el subárbol izquierdo y cuando se haya concluido, el subárbol derecho. Otra forma para entender el recorrido con este metodo seria seguir el orden: nodo raiz, nodo izquierda, nodo derecha.
En el árbol de la figura el recorrido en preorden sería: 2, 7, 2, 6, 5, 11, 5, 9 y 4

Recorrido en postorden
En este caso se trata primero el subárbol izquierdo, después el derecho y por último el nodo actual. Otra forma para entender el recorrido con este metodo seria seguir el orden: nodo izquierda, nodo derecha, nodo raiz. En el árbol de la figura el recorrido en postorden sería: 2, 5, 11, 6, 7, 4, 9, 5 y 2.

Recorrido en inorden
En este caso se trata primero el subárbol izquierdo, después el nodo actual y por último el subárbol derecho. En un ABB este recorrido daría los valores de clave ordenados de menor a mayor. Otra forma para entender el recorrido con este metodo seria seguir el orden: nodo izquierda,nodo raiz,nodo derecha. En el árbol de la figura el recorrido en inorden sería: 2, 7, 5, 6, 11, 2, 5, 4, 9.

Recorridos en amplitud (o por niveles)
En este caso el recorrido se realiza en orden por los distintos niveles del árbol. Así, se comenzaría tratando el nivel 1, que sólo contiene el nodo raíz, seguidamente el nivel 2, el 3 y así sucesivamente. En el árbol de la figura el recorrido en amplitud sería: 2, 7, 5, 2, 6, 9, 5, 11 y 4.
Al contrario que en los métodos de recorrido en profundidad, el recorrido por niveles no es de naturaleza recursiva. Por ello, se debe utilizar una cola para recordar los subárboles izquierdos y derecho de cada nodo.
El esquema algoritmo para implementar un recorrido por niveles es exactamente el mismo que el utilizado en la versión iterativa del recorrido en preorden pero cambiando la estructura de datos que almacena los nodos por una cola

arbol genealogico

raiz:yo
padres: yo, mama, papa
hermanos: abuelap,abuelop, abuela, abuelom, mama,papa
hijos: mama, papa, abuelop, abuelap, abuelom, abuelam
hojas: abuelop, abuelap, abuelom, abuelam
nivel:3
LCI: 1*1+2*2+3*4=17
LCE:2*3=6
recorridos:
preorden: abuelam, mama, yo, abuelop, papa, abuelap, abuelop
postorden: abuelam, abuelom, mama, abuelap, abuelom, papa, yo
inorden: abuelam, mama, abuelom,yo, abuelap, papa, abuelop
arbol general a binario

raiz:A
padres: A,B,E,C,G,M,D,H,I,J
hermanos:E,C D,F O,K
hijos: B,C,D,E,F,G,H,I,J,K,L,M,N,O
hojas: D,F,N,O,K
nivel: 8
LCI: 1*1+2*1+3*2+4*4+5*2+6*2+7*1+8*2=70
LCE:10*2=20
recorridos:
preorden: A,B,E,L,F,C,G,M,N,D,H,I,J,O,K
postorden: L,F,E,B,N,M,G,C,O,K,J,I,JHD,A
inorden: L,E,F,B,A,M,N,G,C,O,J,K,I,H,D

de bosque a binario

raiz: A
padres: A,B,C,D,F,G,H,J,K,L,M,N,O,Q,R,T
hermanos: no hay
hijos: B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U
hojas:S,U,P,I,E
nivel:10
LCI:1*1+2*2+3*2+4*3+5*4+6*4+7*3+8*3+9*1+10*1=131

ejemplo de un programa de arboles

package javaapplication3;

import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import javax.swing.tree.*;
import java.util.*;
public class SimpleTree
{  public static void main(String[] args)
   {  JFrame frame = new SimpleTreeFrame();
      frame.show();
   }
}
class SimpleTreeFrame extends JFrame
{
   DefaultMutableTreeNode root = new DefaultMutableTreeNode("Mundo");
   DefaultMutableTreeNode arge = new DefaultMutableTreeNode("Argentina");
   DefaultMutableTreeNode sant = new DefaultMutableTreeNode("Santa Fe");
   DefaultMutableTreeNode rafa = new DefaultMutableTreeNode("Rafaela");
   DefaultMutableTreeNode rosa = new DefaultMutableTreeNode("Rosario");
   DefaultMutableTreeNode safe = new DefaultMutableTreeNode("Santa Fe");
   DefaultMutableTreeNode vena = new DefaultMutableTreeNode("Venado Tuerto");
   DefaultMutableTreeNode vill = new DefaultMutableTreeNode("Villa Constitucion");
   DefaultMutableTreeNode cord = new DefaultMutableTreeNode("Cordoba");
   DefaultMutableTreeNode codo = new DefaultMutableTreeNode("Cordoba");
   DefaultMutableTreeNode cbro = new DefaultMutableTreeNode("Cura Brochero");
   DefaultMutableTreeNode rcua = new DefaultMutableTreeNode("Rio Cuarto");
   DefaultMutableTreeNode chac = new DefaultMutableTreeNode("Chaco");
   DefaultMutableTreeNode resi = new DefaultMutableTreeNode("Resistencia");
   DefaultMutableTreeNode vang = new DefaultMutableTreeNode("Villa Angela");
   DefaultMutableTreeNode chil = new DefaultMutableTreeNode("Chile");
   DefaultMutableTreeNode regi = new DefaultMutableTreeNode("Region Metropolitana");
   DefaultMutableTreeNode schi = new DefaultMutableTreeNode("Santiago de Chile");
   public SimpleTreeFrame()
   {  setTitle("SimpleTree");
      setSize(300, 200);
      addWindowListener(new WindowAdapter()
         {  public void windowClosing(WindowEvent e)
            {  System.exit(0);
            }
         } );
      root.add(arge);                                                   // Enlazado de nodos
      arge.add(sant);                                                   // Enlazado de nodos
      sant.add(rafa);                                                   // Enlazado de nodos
      sant.add(rosa);                                                   // Enlazado de nodos
      sant.add(safe);                                                   // Enlazado de nodos
      sant.add(vena);                                                   // Enlazado de nodos
      sant.add(vill);                                                   // Enlazado de nodos
      arge.add(cord);                                                   // Enlazado de nodos
      cord.add(codo);                                                   // Enlazado de nodos
      cord.add(cbro);                                                   // Enlazado de nodos
      cord.add(rcua);                                                   // Enlazado de nodos
      arge.add(chac);                                                   // Enlazado de nodos
      chac.add(resi);                                                   // Enlazado de nodos
      chac.add(vang);                                                   // Enlazado de nodos
      root.add(chil);                                                   // Enlazado de nodos
      chil.add(regi);                                                   // Enlazado de nodos
      regi.add(schi);                                                   // Enlazado de nodos
      JTree tree = new JTree(root);
      Container contentPane = getContentPane();
      contentPane.add(new JScrollPane(tree));
      Enumeration hijos = sant.children();                              // Enumeracion de hijos
      while ( hijos.hasMoreElements() )                                 // Enumeracion de hijos
      {                                                                 // Enumeracion de hijos
        System.err.println("Hijos de Santa Fe : "+hijos.nextElement()); // Enumeracion de hijos
      }                                                                 // Enumeracion de hijos
      boolean hoja = vena.isLeaf();                                     // Consulta Hoja
      System.err.println("Es Venado Tuerto hoja : "+hoja);              // Consulta Hoja
      Enumeration breadth = root.breadthFirstEnumeration();             // Enumeracion Nodos
      while ( breadth.hasMoreElements() )                               // Enumeracion Nodos
      {                                                                 // Enumeracion Nodos
        System.err.println("Breadth First : "+breadth.nextElement());   // Enumeracion Nodos
      }                                                                 // Enumeracion Nodos
      Enumeration depth = root.depthFirstEnumeration();                 // Enumeracion Nodos
      while ( depth.hasMoreElements() )                                 // Enumeracion Nodos
      {                                                                 // Enumeracion Nodos
        System.err.println("Depth First : "+depth.nextElement());       // Enumeracion Nodos
      }                                                                 // Enumeracion Nodos
      Enumeration preorder = root.preorderEnumeration();                // Enumeracion Nodos
      while ( preorder.hasMoreElements() )                              // Enumeracion Nodos
      {                                                                 // Enumeracion Nodos
        System.err.println("Pre Order : "+preorder.nextElement());      // Enumeracion Nodos
      }                                                                 // Enumeracion Nodos
      Enumeration postorder = root.postorderEnumeration();              // Enumeracion Nodos
      while ( postorder.hasMoreElements() )                             // Enumeracion Nodos
      {                                                                 // Enumeracion Nodos
        System.err.println("Post Order : "+postorder.nextElement());    // Enumeracion Nodos
      }                                                                 // Enumeracion Nodos
   }
}

bibliografia
arboles
tipos de recorridos

colas

Una cola es una estructura de datos, caracterizada por ser una secuencia de elementos en la que la operación de inserción push se realiza por un extremo y la operación de extracción pop por el otro. También se le llama estructura FIFO (del inglés First In First Out), debido a que el primer elemento en entrar será también el primero en salir.
Las colas se utilizan en sistemas informáticos, transportes y operaciones de investigación (entre otros), dónde los objetos, personas o eventos son tomados como datos que se almacenan y se guardan mediante colas para su posterior procesamiento. Este tipo de estructura de datos abstracta se implementa en lenguajes orientados a objetos mediante clases, en forma de listas enlazadas.

La particularidad de una estructura de datos de cola es el hecho de que sólo podemos acceder al primer y al último elemento de la estructura. Así mismo, los elementos sólo se pueden eliminar por el principio y sólo se pueden añadir por el final de la cola.

Ejemplos de colas en la vida real serían: personas comprando en un supermercado, esperando para entrar a ver un partido de béisbol, esperando en el cine para ver una película, una pequeña peluquería, etc. La idea esencial es que son todos líneas de espera.

operaciones con colas

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

• Colas circulares (anillos): en las que el último elemento y el primero están unidos.

• Colas de prioridad: En ellas, 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. Hay 2 formas de implementación:

1. Añadir un campo a cada nodo con su prioridad. Resulta conveniente mantener la cola ordenada por orden de prioridad.
2. Crear tantas colas como prioridades haya, y almacenar cada elemento en su cola.

• Bicolas: son colas en donde los nodos se pueden añadir y quitar por ambos extremos; se les llama DEQUE (Double Ended QUEue). Para representar las bicolas lo podemos hacer con un array circular con Inicio y Fin que apunten a cada uno de los extremos. Hay variantes:
• Bicolas de entrada restringida: Son aquellas donde la inserción sólo se hace por el final, aunque podemos eliminar al inicio ó al final.
• Bicolas de salida restringida: Son aquellas donde sólo se elimina por el final, aunque se puede insertar al inicio y al final.

Aplicaciones de las Colas

Las Colas también se utilizan en muchas maneras en los sistemas operativos para planificar el uso de los distintos recursos de la computadora. Uno de estos recursos es la propia CPU (Unidad Central de Procesamiento).
Si esta trabajando en una sistema multiusuario, cuando le dice a la computadora que ejecute un programa concreto, el sistema operativo añade su petición a su "cola de trabajo".
Cuando su petición llega al frente de la cola, el programa solicitado pasa a ejecutarse. Igualmente, las colas se utilizan para asignar tiempo a los distintos usuarios de los dispositivos de entrada/salida (E/S), impresoras, discos, cintas y demás. El sistema operativo mantiene colas para peticiones de imprimir, leer o escribir en cada uno de estos dispositivos.

programa de colas
este programa es un ejemplo de una cola
import javax.swing.*;
public class ColaJava {
static Cola accion=new Cola();
public static void main(String[] args) {
int opc=0; while(true){ opc=Integer.parseInt(JOptionPane.showInputDialog(null, "---------------------------------------\n" + "Cola en Java\n" + "---------------------------------------\n" + "1. Introducir dato\n" + "2. Sacar dato\n" + "3. Ver datos introducidos\n" + "4. Borrar los datos de la cola\n" + "---------------------------------------\n" + "5. Salir\n" + "---------------------------------------\n" +
"Teclea el numero de la accion a relizar:"
));
switch(opc){ case 1: accion.Introducir(); break;
case 2: accion.Sacar();
break;
case 3: accion.Mostrar();
break;
case 4: accion.Borrar();
break;
case 5: System.exit(0);
break;
default: JOptionPane.showMessageDialog(null,"No se realizo ningunaaccion\nOpcion no valida"); break; } } } }class Cola{ int tamaño=5;
String cola[]=new String [tamaño];
int frente=0;
int ultimo=-1;
public void Introducir(){
if(ultimo==cola.length-1){
JOptionPane.showMessageDialog(null,"No se realizo ninguna accion");
JOptionPane.showMessageDialog(null,"La cola esta llena\nSaca un datopara poder introducir uno nuevo"); }else{ ultimo++; cola[ultimo]=JOptionPane.showInputDialog(null,"Que dato deseas introducir:"); } }public void Sacar(){ if(ultimo==-1){
JOptionPane.showMessageDialog(null,"No se realizo ninguna accion");
JOptionPane.showMessageDialog(null,"La cola esta vacia\nIntroduce unnuevo dato para poder sacar uno"); }else{ JOptionPane.showMessageDialog(null,"Se saco el dato ( "+cola[frente]+" )"); for(int i=frente;i<ultimo;i++){ cola[i]=cola[i+1]; }cola[ultimo]=null; ultimo--; } }public void Mostrar(){ if(ultimo==-1){ JOptionPane.showMessageDialog(null,"La cola esta vacia\nNo hay datos que mostrar"); } else{ String mostrar=""; for(int i=frente;i<=ultimo;i++){ mostrar=mostrar+cola[i]; }JOptionPane.showMessageDialog(null,"El dato frente es: "+cola[frente]); JOptionPane.showMessageDialog(null,"El dato ultimo es: "+cola[ultimo]); JOptionPane.showMessageDialog(null,"Los datos almacenados son:\n"+mostrar); } }public void Borrar(){ frente=0;
ultimo=-1;
JOptionPane.showMessageDialog(null,"Todos los datos fueron borrados:\n");
}
}
bibliografia
colas

PILAS

concepto
pila es una estructura de datos en la que la inserción y la extracción de elementos se realiza sólo por un extremo que se denomina cabeza. como consecuencia, los elementos de una pila serán eliminados en orden inverso al que se insertaron. es decir, el último elemento que se metió en la pila será el primero en salir de ella.

debido al orden en que se insertan y eliminan los elementos en una pila, también se le conoce como estructura lifo (last in, first out: último en entrar, primero en salir).

ejemplo grafico:

en resumen: una pila es una estructura de datos homogénea (elementos del mismo tipo), secuencial y de tamaño variable. sólo es

posible un modo de acceso a esta estructura: a través de la cabeza de la pila.

en donde se logran a través de funciones como:

*insertar

*mostrar

*extraer

*mostrar

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.

tres programas de pilas
1) pila estatica
package estructuradedatos;
import java.util.Scanner;
/**
 *
 * @author EDDY
 */
public class pila_estatica {
    int pila[]=new int[10];
    int pilai[]=new int[10];
    public void agregar(int dato)
    {
        Scanner cap = new Scanner (System.in);
        Scanner cap1 = new Scanner (System.in);
        String resp;
        System.out.println("desea agregar datos?");
        resp=cap.nextLine();
        System.out.println("ingrese los datos");
        for(int t=0;t<10;t++)
        {
        if(resp.equalsIgnoreCase("si"))
            {       
                dato=cap1.nextInt();
        }
            pila[t]=dato;
            pilai[t]=pila[t];
        }
    }
    public void imprimir ()
    {
        for(int s=9;s>0;s--)
        {
            System.out.println("dato "+s+" "+ pila[s]);
        }
    }
    public static void main(String[] args) {
        pila_estatica p = new pila_estatica();
        int dato=0;
        p.agregar(dato);
        p.imprimir();
    }
}

2) pila estatica con menu

package estructuradedatos;
import java.util.Scanner;
/**
 *
 * @author EDDY
 */
public class pila_pushpop {
    int pila[]=new int[10];
    int tope;
    int x=-1;
    public void tamaño()
    {
        System.out.println("¿de que tamaño quieres que sea la pila?");
        System.out.println("ten en cuenta que el valor 0 es una pila de un elemento");
        Scanner cap = new Scanner (System.in);
        tope=cap.nextInt();
    }
    void push()
    {
        x++;
        if (x==tope){
            System.err.println("la pila esta llena");
        }
        else{
        System.out.println("¿que valor desea ingresar?");
        Scanner cap1=new Scanner(System.in);
        int dato=cap1.nextInt();
        pila[x]=dato;
        }
    }
    void pop()
    {
        if (x==-1){
            System.err.println("la pila esta vacia");
        }
        else{
            x--;
            System.err.println("dato borrado");
        }
    }
    public void imprimir ()
    {
        if (x==-1){
            System.err.println("la pila esta vacia");
        }
        else{
        for(int s=x;s>=0;s--)
        {
            System.out.println("dato "+s+" "+ pila[s]);
        }
        }
    }
    void vaciar(){
        x=-1;
        System.err.println("la pila esta vacia");
    }
    public static void main(String[] args) {
        pila_pushpop p = new pila_pushpop();
        int menu=0;
        p.tamaño();
        Scanner cap1= new Scanner (System.in);
        do{
            System.out.println("1.-ingresar un dato");
            System.out.println("2.-borrar un dato");
            System.out.println("3.-mostrar pila");
            System.out.println("4.-vaciar pila");
            System.out.println("5.-salir");
            menu=cap1.nextInt();
            switch (menu){
                case 1:
                    p.push();
                    break;
                case 2:
                    p.pop();
                    break;
                case 3:
                    p.imprimir();
                    break;
                case 4:
                    p.vaciar();
                    break;
                case 5:
                    System.out.println("adios");
                    break;
                default:
                    System.out.println("la opcion no es correcta");
                    break;
        }
    }
        while (menu!=5);
}
}

3) pila dinamica (editada de un programa de lista)

package estructuradedatos;
import java.util.*;
/**
 *
 * @author EDDY
 */
public class pilaDinamica {
    public static void main(String[] args) {
        Scanner leer = new Scanner(System.in);
        int num, op;
        LinkedList lista = new LinkedList();
        do{
            System.out.println("\t menu\t");
            System.out.println("operaciones con pilas");
            System.out.println("1.- insertar al final");
            System.out.println("2.- borrar al final");
            System.out.println("3.- mostrar pila");
            System.out.println("4.- borrar toda 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();
                    lista.addLast(num);
                    break;
                case 2:
                    System.out.println("se borrara el noso final");
                    lista.removeLast();
                    break;
                case 3:
                    System.out.println("la lista es la siguiente");
                    List lista2 = new ArrayList(lista);
                    Iterator it = lista2.iterator();
                    while (it.hasNext()){
                        System.out.println(it.next());
                    }
                    break;
                case 4:
                    System.out.println("se borraran todos los elementos");
                    lista.clear();
                    break;
                case 5:
                    System.out.println("al rato");
                    break;
            }
        }
        while (op !=5);
    }
}



bibliografia
concepto
operaciones

LISTAS CIRCULARES

listas circulares

concepto:
Una lista circular es una lista lineal en la que el último nodo a punta al primero.
Las listas circulares evitan excepciones en la operaciones que se realicen sobre ellas. No existen casos especiales, cada nodo siempre tiene uno anterior y uno siguiente.
En algunas listas circulares se añade un nodo especial de cabecera, de ese modo se evita la única excepción posible, la de que la lista esté vacía.


concepto:
En una lista enlazada circular, el primer y el último nodo estánunidos juntos. Esto se puede hacer tanto para listas enlazadas simplescomo para las doblemente enlazadas. Para recorrer un lista enlazadacircular podemos empezar por cualquier nodo y seguir la lista encualquier dirección hasta que se regrese hasta el nodo original. Desdeotro punto de vista, las listas enlazadas circulares pueden ser vistascomo listas sin comienzo ni fin. Este tipo de listas es el más usadopara dirigir buffers para “ingerir” datos, y para visitar todos losnodos de una lista a partir de uno dado.

TIPOS DE LISTAS CIRCULARES:

Listas enlazadas circulares simples

Cada nodo tiene un enlace, similar al de las listas enlazadas simples,excepto que el siguiente nodo del último apunta al primero. Como en unalista enlazada simple, los nuevos nodos pueden ser solo eficientementeinsertados después de uno que ya tengamos referenciado. Por esta razón,es usual quedarse con una referencia solamente al último elemento enuna lista enlazada circular simple, esto nos permite rápidasinserciones al principio, y también permite accesos al primer nododesde el puntero del último nodo.

Lista Enlazada Doblemente Circular 

En una lista enlazada doblemente circular, cada nodo tienedos enlaces, similares a los de la lista doblemente enlazada, exceptoque el enlace anterior del primer nodo apunta al último y el enlacesiguiente del último nodo, apunta al primero. Como en una listadoblemente enlazada, las inserciones y eliminaciones pueden ser hechasdesde cualquier punto con acceso a algún nodo cercano. Aunqueestructuralmente una lista circular doblemente enlazada no tiene niprincipio ni fin, un puntero de acceso externo puede establecer el nodoapuntado que está en la cabeza o al nodo cola, y así mantener el ordentan bien como en una lista doblemente enlazada.


BUSCAR O LOCALIZAR UN ELEMENTO DE UNA LISTA CIRCULAR: A la hora de buscar elementos en una lista circularsólo hay que tener una precaución, es necesario almacenar el puntero del nodoen que se empezó la búsqueda, para poder detectar el caso en que no exista elvalor que se busca. Por lo demás, la búsqueda es igual que en el caso de laslistas abiertas, salvo que podemos empezar en cualquier punto de la lista.
ELIMINAR UN NODO EN UNA LISTA CIRCULAR CON MÁS DE UN ELEMENTO:
Es el caso más simple. Partiremos de una lista con uno o más nodos, y usaremos un puntero auxiliar, nodo:

1. Hacemos que nodo apunte al primer elemento de la lista, es decir a Lista.
2. Asignamos a Lista la dirección del segundo nodo de la lista: Lista->siguiente.
3. Liberamos la memoria asignada al primer nodo, el que queremos eliminar.

Si no guardamos el puntero al primer nodo antes de actualizar Lista, después nos resultaría imposible liberar la memoria que ocupa. Si liberamos la memoria antes de actualizar Lista, perderemos el puntero al segundo nodo.
                             
Si la lista sólo tiene un nodo, el proceso es también válido, ya que el valor de Lista->siguiente es NULL, y después de eliminar el primer nodo la lista quedará vacía, y el valor de Lista será NULL.
De hecho, el proceso que se suele usar para borrar listas completas es eliminar el primer nodo hasta que la lista esté vacía.

Eliminar un nodo cualquiera de una lista abierta:

En todos los demás casos, eliminar un nodo se puede hacer siempre del mismo modo. Supongamos que tenemos una lista con al menos dos elementos, y un puntero al nodo anterior al que queremos eliminar. Y un puntero auxiliar nodo.


El proceso es parecido al del caso anterior:

1. Hacemos que nodo apunte al nodo que queremos borrar.
2. Ahora, asignamos como nodo siguiente del nodo anterior, el siguiente al que queremos eliminar: anterior->siguiente = nodo->siguiente.
3. Eliminamos la memoria asociada al nodo que queremos eli minar.

Si el nodo a eliminar es el último, es procedimiento es igualmente válido, ya que anterior pasará a ser el último, y anterior->siguiente valdrá NULL.

Aplicacion

La lista circular, así como en el ejemplo donde guardamos nombre, DNI, edad y sueldo, podemos guardar mas datos y generar una lista que se valla expandiendo, lo podemos usar en un programa de Matriculas de una Institucion Educativa, Control de personal de una Empresa, y asi como muchas otras aplicaciones.

una parte del codigo del programa descrito arriba

package clistacircularse;
import javax.swing.*;
public class Formulario {

public static void main (String[] args)
{
    Lista lcse = new Lista();
    String nombre,lmenu,ldni,lnom,led,lsue;
    double suel;
    int vmenu,vdni,vedad;
    vmenu=0;
    while (vmenu!=8){
        if (vmenu == 0){
            /////////////
            lmenu = JOptionPane.showInputDialog("Menu:\n"+"1: Añadir final\n"+"2: Añadir Principio\n"+"3: Mostrar lista\n"+"4: Borrar elemento primero\n"+"5: Borrar Todo\n"+"6: Mostrar uno\n"+"7: modificar\n"+"8: salir\n");
            vmenu=Integer.parseInt(lmenu);
            //////////////
        }
        if (vmenu == 1){
            //ingresar los datos del trabajador
            JOptionPane.showMessageDialog(null,"INGRESAR DATOS DEL trabajador");
            vdni=1;
           
            while (vdni!= 0){

                 lnom = JOptionPane.showInputDialog("nombre");
                
                 while ((nombre = lnom)!= null){
                    ldni=JOptionPane.showInputDialog("DNI");
                    vdni = Integer.parseInt(ldni);
                    led = JOptionPane.showInputDialog("edad");
                    vedad = Integer.parseInt(led);
                    lsue = JOptionPane.showInputDialog("sueldo");
                    suel = Double.parseDouble(lsue);

                    if (vdni != 0)
                    {
                    lcse.añadirfinal(vdni,lnom,vedad,suel);
                    lnom=JOptionPane.showInputDialog("nombre");
                    }
                    else
                    {
                        lnom = null;
                    }
                    }

            }
            /////////////
              lmenu = JOptionPane.showInputDialog("Menu:\n"+"1: Añadir final\n"+"2: Añadir Principio\n"+"3: Mostrar lista\n"+"4: Borrar elemento primero\n"+"5: Borrar Todo\n"+"6: Mostrar uno\n"+"7: modificar\n"+"8: salir\n");
              vmenu=Integer.parseInt(lmenu);
           //////////////
        }
        if (vmenu == 2){
            //ingresar los datos de un trabajador al principio
            JOptionPane.showMessageDialog(null,"INGRESAR DATOS DEL trabajador al principio");
            lnom = JOptionPane.showInputDialog("nombre");
            ldni=JOptionPane.showInputDialog("DNI");
            vdni = Integer.parseInt(ldni);
            led = JOptionPane.showInputDialog("edad");
            vedad = Integer.parseInt(led);
            lsue = JOptionPane.showInputDialog("sueldo");
            suel = Double.parseDouble(lsue);
            lcse.añadirprincipio(vdni,lnom,vedad,suel);
            /////////////
            lmenu = JOptionPane.showInputDialog("Menu:\n"+"1: Añadir final\n"+"2: Añadir Principio\n"+"3: Mostrar lista\n"+"4: Borrar elemento primero\n"+"5: Borrar Todo\n"+"6: Mostrar uno\n"+"7: modificar\n"+"8: salir\n");
            vmenu=Integer.parseInt(lmenu);
            //////////////
        }
        if (vmenu == 3){
            //muestra los datos del trabajador
            JOptionPane.showMessageDialog(null,"lista");
            lcse.mostrar(lcse);
            /////////////
            lmenu = JOptionPane.showInputDialog("Menu:\n"+"1: Añadir final\n"+"2: Añadir Principio\n"+"3: Mostrar lista\n"+"4: Borrar elemento primero\n"+"5: Borrar Todo\n"+"6: Mostrar uno\n"+"7: modificar\n"+"8: salir\n");
            vmenu=Integer.parseInt(lmenu);
            //////////////
        }
       
        if (vmenu == 4){
            //borra el trabajador del principo
            lcse.borrar();
            /////////////
            lmenu = JOptionPane.showInputDialog("Menu:\n"+"1: Añadir final\n"+"2: Añadir Principio\n"+"3: Mostrar lista\n"+"4: Borrar elemento primero\n"+"5: Borrar Todo\n"+"6: Mostrar uno\n"+"7: modificar\n"+"8: salir\n");
            vmenu=Integer.parseInt(lmenu);
            //////////////
        }

        if (vmenu == 5){
            //borra todo
            lcse.borrartodo(lcse);
            /////////////
            lmenu = JOptionPane.showInputDialog("Menu:\n"+"1: Añadir final\n"+"2: Añadir Principio\n"+"3: Mostrar lista\n"+"4: Borrar elemento primero\n"+"5: Borrar Todo\n"+"6: Mostrar uno\n"+"7: modificar\n"+"8: salir\n");
            vmenu=Integer.parseInt(lmenu);
            //////////////
        }

        if (vmenu == 6){
            //busca un trabajador buscado por su dni
            String ldn;
            int vdn;
            ldn = JOptionPane.showInputDialog("Ingresar DNI:");
            vdn=Integer.parseInt(ldn);
            lcse.mostraruno(lcse,vdn);
            /////////////
            lmenu = JOptionPane.showInputDialog("Menu:\n"+"1: Añadir final\n"+"2: Añadir Principio\n"+"3: Mostrar lista\n"+"4: Borrar elemento primero\n"+"5: Borrar Todo\n"+"6: Mostrar uno\n"+"7: modificar\n"+"8: salir\n");
            vmenu=Integer.parseInt(lmenu);
            //////////////
        }

         if (vmenu == 7){
             //modifica los datos de un trabjador buscado por su dni
            String ldn;
            int vdn;
            ldn = JOptionPane.showInputDialog("Ingresar DNI:");
            vdn=Integer.parseInt(ldn);
            lnom = JOptionPane.showInputDialog("nombre");
             led = JOptionPane.showInputDialog("edad");
            vedad = Integer.parseInt(led);
            lsue = JOptionPane.showInputDialog("sueldo");
            suel = Double.parseDouble(lsue);
            lcse.modificar(lcse,vdn,lnom,vedad,suel);
            /////////////
            lmenu = JOptionPane.showInputDialog("Menu:\n"+"1: Añadir final\n"+"2: Añadir Principio\n"+"3: Mostrar lista\n"+"4: Borrar elemento primero\n"+"5: Borrar Todo\n"+"6: Mostrar uno\n"+"7: modificar\n"+"8: salir\n");
            vmenu=Integer.parseInt(lmenu);
            //////////////
        }

    }

}
}


bibliografia: listas circulares