BUSQUEDA HASH

La idea básica de este método consiste en aplicar una función que traduce un conjunto de posibles valores llave en un rango de direcciones relativas.

Hash se refiere a una función o método para generar claves o llaves que representen de manera casi unívoca a un registro, archivo, documentó, etc.

Una función de hash es una función para resumir o identificar probabilísticamente un gran conjunto de información, dando como resultado un conjunto imagen finito generalmente menor (un subconjunto de los números naturales).

ventajas

• žSe pueden usar los valores naturales de la llave, puesto que se traducen internamente a direcciones fáciles de localizar.
• žSe logra independencia lógica y física, debido a que los valores de las llaves son independientes del espacio de direcciones.
• No se requiere almacenamiento adicional para los índices.

desventajas

• No pueden usarse registros delongitud variable
• El archivo no esta clasificado
• žNo permite llaves repetidas
• žSolo permite acceso por una sola llave

Un problema potencial encontrado en este proceso, es que tal función no puede ser uno a uno; las direcciones calculadas pueden no ser todas únicas, cuando R(k1 )= R(k2)Pero : K1 diferente de K2 decimos que hay una colisión

costos

• žTiempo de procesamiento requerido para la aplicación de la función hash
• žTiempo de procesamiento y los accesos E/S requeridos para solucionar las colisiones.

funciones hash mas comunes

• žResiduo de la división
• žMedio del cuadrado
• žPliegue

hashing por residuo de la division 

La idea de este método es la de dividir el valor de la llave entre un numero apropiado, y después utilizar el residuo de la división como dirección relativa para el registro (dirección = llave módulo divisor).

medio del cuadrado

En esta técnica, la llave es elevada al cuadrado, después algunos dígitos específicos se extraen de la mitad del resultado para constituir la dirección relativa.

hashing por pliegue

En esta técnica el valor de la llave es particionada en varias partes, cada una de las cuales(excepto la ultima) tiene el mismo numero de dígitos que tiene la dirección relativa objetivo. Estas particiones son después plegadas una sobre otra y sumadas. El resultado, es la dirección relativa.

operaciones basica

Inserción(llave, valor) búsqueda(llave) que devuelve valor La mayoría de las implementaciones también incluyen borrar(llave). También se pueden ofrecer funciones como iteración en la tabla, crecimiento y vaciado.

insercion

Inserción(llave, valor) búsqueda(llave) que devuelve valor La mayoría de las implementaciones también incluyen borrar(llave). También se pueden ofrecer funciones como iteración en la tabla, crecimiento y vaciado.

busqueda

• žPara recuperar los datos, es necesario únicamente conocer la clave del elemento, a la cual se le aplica la función resumen.
• žEl valor obtenido se mapea al espacio de direcciones de la tabla.
• Si el elemento existente en la posición indicada en el paso anterior tiene la misma clave que la empleada en la búsqueda, entonces es el deseado. Si la clave es distinta, se ha de buscar el elemento según la técnica empleada para resolver el problema de las colisiones al almacenar el elemento.

http://www.youtube.com/watch?v=iBHR2ETg2po&feature=player_embedded

http://www.youtube.com/watch?v=0CIlFpwuj1Q&feature=related

http://www.youtube.com/watch?v=PHzFZMwhtp4&feature=related

http://www.youtube.com/watch?v=BSwmlqHCTMQ

GRAFOS

Cómo se conforma un grafo?
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 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).

 Qué es un vértice o nodo?

Ø Punto de intersección o unión de varios elementos que confluyen en el mismo lugar

En estructura de datos:

Un nodo es uno de los elementos de una lista enlazada, de un árbolo de un grafo . Cada nodo será una estructura o registro que dispondrá de varios campos , y al menos uno de esos campos será un puntero o referencia a otro nodo, de forma que, conocido un nodo, a partir de esa referencia, será posible en teoría tener acceso a otros nodos de la estructura. Los nodos son herramientas esenciales para la construcción de estructuras de datos dinámicas.

Un Arco o también llamado Arista corresponde a una relación entre dos vértices de un grafo .

Tipos de grafos dígrafo y no dirigido.
Un dígrafo o grafo dirigido es un grafo en el cual las aristas están dirigidas (y se acostumbra llamarles arcos). Es decir, la relación entre dos vértices adyacentes no necesariamente es simétrica ejemplo: si hay un arco que va de A a B (relación que se denota a veces como A→B ) entonces se dice que A domina a B .

Grafo no dirigido es un conjunto de pares no ordenados de elementos.
Un par no ordenado es un conjunto de la forma {a,b} , de manera que {a,b} = {b,a} .

En que consiste el camino en un grafo
Un camino en un grafo es una sucesión finita en la que aparecen alternadamente vértices y aristas de dicho grafo
Tipos de caminos
Camino euleriano: es un camino o circuito que contiene todas las aristas apareciendo cada una de ellas exactamente una vez. Un grafo que admite dicho circuito se denomina grafo euleriano, y sus vértices o tienen grado par o dos de los vértices tienen grado impar.
Camino hamiltoniano: es un camino simple que contiene todos los vértices apareciendo cada uno de ellos exactamente una vez. Un ciclo que a su vez es un camino hamiltoniano se denomina ciclo hamiltoniano, y un grafo que contiene un ciclo hamiltoniano se denomina grafo hamiltoniano.

NOTACION o GRANDE

Definicion:
Se utiliza para hacer referencia a la velocidad de crecimiento de los valores de una funcion, es decir su utilidad radica en encontrar un limite superior de tiempo de ejecucion de un algoritmo en el peor de los casos.

 

La definicion de esta notacion es la siguiente.-

g(n) O(F(n)) si y solo si existen las constantes C y n tales que g(n) <= C * F(n).

 

para todo C>=n se tiene que T(n)<=Cn el orden de la magnitud de una funcion es el orden del termino de la funcion mas grande en terminos de n.

Nota: el orden de magnitud de una función es el orden del termino de la función mas grande respecto de n.

 

caracterisitcas:

• El análisis de algoritmos estima el consumo de recursos de un algoritmo.
•  Esto nos permite comparar los costos relativos de dos o más algoritmos para resolver el mismo problema.
• El análisis de algoritmos también les da una herramienta a los diseñadores de algoritmos para estimar si una solución propuesta es probable que satisfaga las restricciones de recursos de un problema.
• El concepto de razón de crecimiento, es la razón a la cual el costo de un algoritmo crece conforme el tamaño de la entrada crece.
• Usualmente se mide el tiempo de ejecución de un algoritmo, y el almacenamiento primario y secundario que consume.
• Consideración principal para estimar el desempeño de un algoritmo, es el número de operaciones básicas requeridas por el algoritmo para procesar una entrada de cierto tamaño.

ALGORITMOS

Un algooritmo es un procedimiento esquematico que comprende un conjunto de pasos secuenciales ordenados, para realizar una actividad especifica

Un Algoritmo es..
Preciso: cada instruccion tiene que ser clara y determinada a una accion
Definidido: por que debe obtenerse los resultados determinados con las instrucciones de entrada
Finito: por que su diseño debe tener un numero limitado en cuanto a los pasos
Ordenado: por que tienen una secuencia de pasos
Efectividad: El tiempo y esfuerzo por cada paso realizado debe ser preciso, no usando nada más ni nada menos que aquello que se requiera para y en su ejecución.

CODIGO DE ARBOL EN JAVA

class NodoBinario{
 int dato;
 NodoBinario Hizq, Hder;
 //Constructores
 NodoBinario (int Elem){
  dato = Elem;
  NodoBinario Hizq, Hder = null;
 }
 //Insercion de un elemento
 public void InsertaBinario (int Elem){
  if(Elem < dato){
   if (Hizq == null)
    Hizq = new NodoBinario(Elem);
   else
    Hizq.InsertaBinario(Elem);
  }
  else{
   if (Elem > dato){
    if (Hder == null)
     Hder = new NodoBinario (Elem);
    else
     Hder.InsertaBinario(Elem);
   }
  }
 }
}
//Definicion de la clase Arbol
class Arbol{
 Cola Cola = new Cola();
 NodoBinario Padre;
 NodoBinario Raiz;
 //Constructor
 public Arbol(){
  Raiz = null;
 }
 //Insercion de un elemento en el arbol
 public void InsertaNodo(int Elem){
  if(Raiz == null)
   Raiz = new NodoBinario (Elem);
  else
   Raiz.InsertaBinario (Elem);
 }
 //Preorden Recursivo del arbol
 public void Preorden (NodoBinario Nodo){
  if(Nodo == null)
   return;
  else{
   System.out.print (Nodo.dato + " ");
   Preorden (Nodo.Hizq);
   Preorden (Nodo.Hder);
  }
 }
 //PostOrden recursivo del arbol
 public void PostOrden (NodoBinario Nodo){
  if(Nodo == null)
   return;
  else{
   PostOrden (Nodo.Hizq);
   PostOrden (Nodo.Hder);
   System.out.print (Nodo.dato + " ");
  }
 }
 //Inorden Recursivo del arbol
 public void Inorden (NodoBinario Nodo){
  if(Nodo == null)
   return;
  else{
   Inorden (Nodo.Hizq);
   System.out.print(Nodo.dato + " ");
   Inorden (Nodo.Hder);
  }
 }
 //Busca un elemento en el arbol
 void Busqueda (int Elem, NodoBinario A){
  if((A == null) | (A.dato == Elem)){
   System.out.print(A.dato + " ");
   return;
  }
  else{
   if(Elem>A.dato)
    Busqueda (Elem, A.Hder);
   else
    Busqueda ( Elem, A.Hizq);
  }
 }
 //Altura del arbol
 public int Altura (NodoBinario Nodo){
  int Altder = (Nodo.Hder == null? 0:1 + Altura (Nodo.Hder));
  int Altizq = (Nodo.Hizq == null? 0:1 + Altura (Nodo.Hizq));
  return Math.max(Altder,Altizq);
 }
 //Recorrido en anchura del arbol
 public void Anchura (NodoBinario Nodo){
  Cola cola= new Cola();
  NodoBinario T = null;
  System.out.print ("El recorrido en Anchura es: ");
  if(Nodo != null){
   cola.InsertaFinal (Nodo);
   while(!(cola.VaciaLista ())){
    T = cola.PrimerNodo.datos;
    cola.EliminaInicio();
    System.out.print(T.dato + " ");
    if (T.Hizq != null)
     cola.InsertaFinal (T.Hizq);
    if (T.Hder != null)
     cola.InsertaFinal (T.Hder);
   }
  }
  System.out.println();
 }
}
//Definición de la Clase NodoLista
class NodosListaA{
   NodoBinario datos;
    NodosListaA siguiente;
     //Construtor  Crea un nodo del tipo Object
 NodosListaA (NodoBinario  valor){
  datos =valor;
     siguiente = null;  //siguiente con valor de nulo
  }
 // Constructor Crea un nodo del Tipo Object y al siguiente nodo de la lista
 NodosListaA (NodoBinario valor, NodosListaA signodo){
  datos = valor;
     siguiente = signodo; //siguiente se refiere al siguiente nodo
 }
}
//Definición de la Clase Lista
class Cola{
 NodosListaA PrimerNodo;
 NodosListaA UltimoNodo;
 String Nombre;
 //Constructor construye una lista vacia con un nombre de List
 public Cola(){
  this ("Lista");
 }
 //Constructor
  public Cola (String s){
  Nombre = s;
     PrimerNodo = UltimoNodo =null;
 }
 //Retorna True si Lista Vacía
 public boolean VaciaLista() {
  return PrimerNodo == null;
 }
 //Inserta un Elemento al Frente de la Lista
 public void InsertaInicio (NodoBinario ElemInser){
  if(VaciaLista())
      PrimerNodo = UltimoNodo = new NodosListaA (ElemInser);
     else
      PrimerNodo = new NodosListaA (ElemInser, PrimerNodo);
 }
 //Inserta al Final de la Lista
 public void InsertaFinal(NodoBinario ElemInser){
  if(VaciaLista())
         PrimerNodo = UltimoNodo = new NodosListaA (ElemInser);
     else
         UltimoNodo=UltimoNodo.siguiente =new NodosListaA (ElemInser);
 }
 //Eliminar al Inicio
 public void EliminaInicio(){
  if(VaciaLista())
      System.out.println ("No hay elementos");
   // Restablecer  las referencias de PrimerNodo y UltimoNodo
   if(PrimerNodo.equals (UltimoNodo))
      PrimerNodo = UltimoNodo = null;
     else
      PrimerNodo = PrimerNodo.siguiente;
 }
 //Elimina al final
 public void EliminaFinal (){
     if(VaciaLista())
       System.out.println ("No hay elementos");
  // Restablecer  las referencias de PrimerNodo y UltimoNodo
  if (PrimerNodo.equals (UltimoNodo))
      PrimerNodo = UltimoNodo = null;
     else{
      NodosListaA Actual =PrimerNodo;
   while (Actual.siguiente != UltimoNodo)
    Actual = Actual.siguiente;
   UltimoNodo =Actual;
   Actual.siguiente = null;
     }
 }
}

class ArbolBinarioA{
 public static void main (String[]args){
  Arbol A = new Arbol();
  A.InsertaNodo (10);
  A.InsertaNodo (7);
  A.InsertaNodo (8);
  A.InsertaNodo (6);
  A.InsertaNodo (12);
  A.InsertaNodo (11);
  A.InsertaNodo (5);
  A.InsertaNodo (4);
  A.InsertaNodo (3);
  A.InsertaNodo (2);
  System.out.print("El recorrido en Preorden es: ");
  A.Preorden (A.Raiz);
  System.out.println();
  System.out.print("El recorrido en Inorden es: ");
  A.Inorden (A.Raiz);
  System.out.println();
  System.out.print("El recorrido en Postorden es: ");
  A.PostOrden (A.Raiz);
  System.out.println();
  System.out.println("La altura del arbol es: " + A.Altura (A.Raiz));
  A.Anchura (A.Raiz);
 }
}

ARBOL GENEALOGICO

                 

archivo de árbol familiar

Ejemplo de arbol binario


opcion 2:

ARBOLES

Definicion:

Estructura no lineal y dinámica de datos. Dinámica: puede cambiar durante la ejecución de un programa. No lineal: a cada elemento del árbol pueden seguirle varios elementos. Están formados por un conjunto de nodos y un conjunto de aristas que conectan pares de nodos.

Nodo hijo: cualquiera de los nodos apuntados por uno de los nodos del árbol.

Nodo padre: nodo que contiene un puntero al nodo actual.

Posición dentro del árbol:

Nodo raíz: nodo que no tiene padre. Este es el nodo que usaremos para referirnos al árbol.

Nodo hoja: nodo que no tiene hijos.

Nodo rama: aunque esta definición apenas la usaremos, estos son los nodos que no pertenecen a ninguna de las dos categorías anteriores.

Operaciones:

• Añadir o insertar elementos.
• Buscar o localizar elementos.
• Borrar elementos.
• Moverse a través del árbol.
• Recorrer el árbol completo.

Existen dos recorridos típicos para listar los nodos de un árbol:  primero en profundidad y primero en anchura.
En el primer caso, se listan los nodos expandiendo el hijo actual de cada nodo hasta llegar a una hoja, donde se vuelve al nodo anterior probando por el siguiente hijo y así sucesivamente.
En el segundo, por su parte, antes de listar los nodos de nivel n + 1 (a distancia n + 1 aristas de la raíz), se deben haber listado todos los de nivel n. Otros recorridos típicos del árbol son preorden, postorden e inorden:
Recorrido en preorden, también llamado orden previo consiste en recorrer en primer lugar la raíz y luego cada uno de los hijos en orden previo.
Recorrido en inorden, también llamado orden simétrico (aunque este nombre sólo cobra significado en los árboles binarios) consiste en recorrer en primer lugar A1, luego la raíz y luego cada uno de los hijos en orden simétrico.
Recorrido en postorden, también llamado orden posterior consiste en recorrer en primer lugar cada uno de los hijos en orden posterior y por último la raíz.

Tipos de árboles

• Árboles Binarios
• Árbol de búsqueda binario auto-balanceable
• Árboles AVL
• Árboles Rojo-Negro
• Árbol AA
• Árboles Multicamino
• Árboles B (Arboles de búsqueda multicamino autobalanceados)
• Árbol-B+
• Árbol-B*

Aplicaciones

• Representación de datos jerárquicos.
• Ayuda para realizar búsquedas en conjuntos de datos

Bibliografias:
http://es.wikipedia.org/wiki/%C3%81rbol_(inform%C3%A1tica)
http://c.conclase.net/edd/?cap=006b#6_3

PILA CON ARREGLOS EN C#

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int tam;
            Console.WriteLine("capture el tamaño de la pila");
            tam = int.Parse(Console.ReadLine());
            string[] pila = new string[tam];
            string Elemento = string.Empty;
            string op = string.Empty;

            do
            {
                Console.Write("\n\nMenú  \n 1)Meter elemento a la pila  \n 2)Muestra pila \n 3)Suprime elemento de la cima \n 0)Salir \n\n");

                op = Console.ReadLine();

                switch (op)
                {
                    case "1":
                        Console.Write("INGRESAR VALORES A LA PILA \n");
                        Console.Write("Escriba el dato a ingresar a la pila:");
                        Elemento = Console.ReadLine();

                        while (string.IsNullOrEmpty(Elemento))
                        {
                            Console.Write("Ingrese un valor válido a la pila:");
                            Elemento = Console.ReadLine();
                        }

                        if (estaLlena(pila))
                        {
                            Console.Write("La pila está llena, imposible agregar nuevo valor \n");
                        }
                        else
                        {
                            Meter(pila, Elemento);
                        }

                        break;

                    case "2":
                        Console.Write("MOSTRAR PILA \n");

                        if (esVacia(pila))
                        {
                            Console.Write("La pila está vacia \n");
                        }
                        else
                        {
                            Mostrar(pila);
                        }
                        break;


                    case "3":
                        Console.Write("SUPRIME ELEMENTO DE LA PILA \n");

                        if (esVacia(pila))
                        {
                            Console.Write("La pila tiene espacio en la disponible \n");
                        }
                        else
                        {
                            Suprime(pila);
                            Console.Write("El elemento de la cima suprimido");
                        }
                        break;

                    default:
                        Console.Write("saliendo");
                        break;
                }
            } while (!op.Equals("0"));
        }
        static public bool esVacia(string[] _pila)
        {
           bool fl = true;

            for (int i = _pila.Length - 1; i >= 0; i--)
            {
                if (_pila[i] != null)
                {
                    fl = false;
                    break;
                }
            }
            return fl;
        }

        static public bool estaLlena(string[] _pila)
        {
            bool fl = false;
            int count = 0;

            for (int i = _pila.Length - 1; i >= 0; i--)
            {
                if (_pila[i] != null)
                {
                    count += 1; ;
                }
            }

            if (count == _pila.Length) { fl = true; }

            return fl;
        }
        static public bool Suprime(string[] _pila)
        {
            bool fl = false;

            for (int i = _pila.Length - 1; i >= 0; i--)
            {
                if (_pila[i] != null)
                {
                    _pila[i] = null;
                    fl = true;
                    break;
                }
            }

            return fl;
        }
        static public bool Meter(string[] _pila, string _elemento)
        {
            bool fl = false;

            for (int i = _pila.Length - 1; i >= 0; i--)
            {
                if (_pila[i] != null)
                {
                    _pila[i + 1] = _elemento;
                    fl = true;
                    break;
                }
                else if (_pila[i] == null && i == 0)
                {
                    _pila[i] = _elemento;
                    fl = true;
                   break;
                }
           }
           return fl;
       }
        static public void Mostrar(string[] _pila)
        {
            for (int i = _pila.Length - 1; i >= 0; i--)
            {
                if (_pila[i] != null)
                {
                    Console.Write(_pila[i] + "\n");
                }
            }

        }
    }
}



           
           

PILA DINÁMICA EN JAVA

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);   }            }

CÓDIGO DE PILA

package javaapplication;
import java.util.Scanner;

public class Main {

      public static void main(String[] args) {
     
     int dato;
        int pila[] = new int[5];
        Scanner Captura = new Scanner(System.in);
        for(int tope = 0; tope <= 4; tope++){
            System.out.println("Proporcione datos para la pila");
            dato = Captura.nextInt();
            pila[tope] = dato;
        }
        for(int tope = 4; tope >= 0; tope--){
            System.out.println("La pila tiene los siguientes datos: " + pila[tope]);
        }
        }
    }

COLAS

Definición:
Una cola es un tipo especial de lista abierta en la que sólo se pueden insertar nodos en uno de los extremos de la lista y sólo se pueden eliminar nodos en el otro. Además, como sucede con las pilas, las escrituras de datos siempre son inserciones de nodos, y las lecturas siempre eliminan el nodo leído.

Este tipo de lista es conocido como lista FIFO (First In First Out), el primero en entrar es el primero en salir.

tipos

Existen tres tipos de colas:

• cola lineal (sencilla)
• cola circular
• cola doble (bicola)

Cola sencilla

La cola lineal es un tipo de almacenamiento creado por el usuario que trabaja bajo la técnica FIFO (primero en entrar primero en salir). Las colas lineales se representan gráficamente de la siguiente manera:

 

Las colas lineales tienen un grave problema, como las extracciones sólo pueden realizarse por un extremo, puede llegar un momento en que el apuntador sea igual al máximo número de elementos en la cola, siendo que al frente de la misma existan lugares vacíos, y al insertar un nuevo elemento nos mandará un error de overflow (cola llena).

Cola circular

En este tipo de cola existe un apuntador desde el último elemento al primero de la cola. 

La representación gráfica de esta estructura es la siguiente: 

La condición de vacío en este tipo de cola es que el apuntador F sea igual a cero.

Las condiciones que debemos tener presentes al trabajar con este tipo de estructura son las siguientes: 

• Over flow, cuando se realice una inserción. 

• Under flow, cuando se requiera de una extracción en la cola. 

• Vació

Cola doble o bicola

Esta estructura es una cola bidimensional en que las inserciones y eliminaciones se pueden realizar en cualquiera de los dos extremos de la bicola. Gráficamente representamos una bicola de la siguiente manera: 

Existen dos variantes de la doble cola: 

• Doble cola de entrada restringida. 

• Doble cola de salida restringida. 

La primer variante sólo acepta inserciones al final de la cola, y la segunda acepta eliminaciones sólo al frente de la cola

Operaciones

Las colas sólo permiten añadir y leer elementos:

• Añadir: Inserta un elemento al final de la cola.
• Leer: Lee y elimina un elemento del principio de la cola.

código de colas en java

class ColaArreglo{

Object[] ArregloCola;

int frente=0,fondo=0,Num_elem;

int Cant_elem=5;

//Constructor

ColaArreglo(){

ArregloCola=new Object[Cant_elem];

frente=0;

fondo=-1;

Num_elem=0;

}

//Encola un elemento

public void Encolar(Object x){

if(fondo==-1){

fondo++;

ArregloCola[fondo]=x;

}

else{

fondo++;

if(fondo==Cant_elem)

System.out.println("No hay campo");

else

ArregloCola[fondo]=x;

}

}

//Desencola un elemento

public void Desencolar(){

if(VaciaCola())

System.out.println("No hay Elementos");

else{

for(int i=frente;i<fondo; i++){

ArregloCola[i]=ArregloCola[i+1];

}

ArregloCola[fondo]=null;

fondo--;

}

}

//Retorna si esta vacia la cola

public boolean VaciaCola(){

return (fondo<frente);

}

//Imprime al cola

public void Imprimir(){

int i=0;

System.out.print("La Cola es: ");

while(i<ArregloCola.length){

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

i++;

}

System.out.println("");

System.out.println("");

}

}

class ColasA{

public static void main(String[]args){

ColaArreglo nuevo=new ColaArreglo();

nuevo.Encolar("9");

nuevo.Encolar("10");

nuevo.Encolar("11");

nuevo.Encolar("12");

nuevo.Encolar("13");

nuevo.Desencolar();

nuevo.Encolar("1133");

nuevo.Imprimir();

    }

}

videos de colas

Fuentes:

http://c.conclase.net/edd/?cap=003b

estructura de datos

PILAS

                                                                Difinicion:

Las pilas son otro tipo de estructura de datos lineales, las cuales presentan restricciones en cuanto a la posición en la cual pueden realizarse las inserciones y las extracciones de elementos.

Una pila es una lista de elementos en la que se pueden insertar y eliminar elementos sólo por uno de los extremos.

Las pilas solo tiene 2 operaciones, Push(Inserción) y Pop(Eliminación) la cual solo se puede efectuar por un extremo llamado Top. Sin Embargo se le pueden aplicar todas las operaciónes al igual que a las listas.

Operaciones:

Push:  Es simplemente el método por el cual va agregando un Dato nuevo a la Pila tomando en cuenta la 

capacidad Máxima (Max) de almacenar un dato.

Pop: Es simplemente el método por el cual va sacando el ultimo Dato de la Pila, basándose únicamente en el Top.

Recorrido Ya que las pilas son LIFO(Last in  First Out) el Recorrido se hace sacando el ultimo dato que se inserto hasta que no encuentre ningún otro. 

Detalle: Apuntador toma el Top, después ve si la condición cumple para efectuar un Ciclo mientras Apuntador sea diferente de Nulo, si cumple lo que hace es que despliega el contenido de la Pila(Pila[Apuntador]), después Apuntador se le resta 1. Este proceso se repite hasta que Apuntador sea igual Nulo(Cuando llega a este punto la Pila ya fue Recorrida).

Algoritmo:

Recorrido(Pila, Top) 

Apuntador ←- Top 

Repetir mientras Apuntador &ne; Nulo 

Imprimir Pila[Apuntador] 

Apuntador ←- Apuntador - 1 

Fin del ciclo 

Salir 

<>

Búsqueda 

Definición: 

Este método usa el recorrido para encontrar Elemento y desplegar un mensaje si la búsqueda es exitosa. 

Detalle: 

El algoritmo compara para determinar si la Pila tiene algún dato, si no simplemente desplegara Lista Vacía y saldrá. De otra manera hará un Recorrido y comparara con cada uno de los Datos de la Pila hasta encontrar el dato que desea buscar. Si lo encuentra desplegara “El Dato fue encontrado” de otra manera “El Dato no se encontró”. 

Algoritmo: 

Busqueda(Pila, Top, Elemento) 

Si Top &ne; Nulo 

Apuntador ←- Top 

Repetir mientras Apuntador &ne; Nulo 

Si Pila[Apuntador] = Elemento 

Imprimir “El Dato fue encontrado” y Salir 

Apuntador ←- Apuntador - 1 

Fin del ciclo 

Imprimir “El Dato no se encontró” 

Si no: 

Imprimir “Pila Vacía” 

Salir 

Eliminacion:

Definición:

Este método busca un Dato dentro de la pila y lo elimina.

Detalle:

El algoritmo compara para determinar si la Pila tiene algún dato, si no simplemente desplegara Pila Vacía y saldrá. De otra manera hará un Recorrido y comparara con cada uno de los Datos de la Pila hasta encontrar el dato que desea eliminar, mientras hace esto copia cada uno de los datos a un arreglo Temp para cuando encuentre el Dato regresar esos valores a la Pila. Si lo encuentra desplegara “Eliminado el Dato” y le restara 1 a Top, de otra manera “El Dato no encontrado”.

Algoritmo:

Borrar(Pila, Temp, Top, Elemento)

Si Top &ne; Nulo

Apuntador1 ←- Top

Repetir mientras Apuntador1 &ne; Nulo

Si Pila[Apuntador1] = Elemento

Imprimir “Eliminando el Dato…”

Repetir mientras Apuntador2 &ne; Nulo

Pila[Apuntador1]=Temp[Apuntador2]

Fin del ciclo

Top ←- Top - 1 y Salir

Si No:

Temp[Apuntador2] ←- Pila[Apuntador1]

Apuntador1 ←- Apuntador1 - 1

Apuntador2 ←- Apuntador2 + 1

Fin del ciclo

Imprimir “Dato no encontrado”

Si no:

Imprimir “Pila Vacía”

Salir

aplicaciones

• Un ejemplo típico de pila lo constituye un montón de platos: Cuando se quiere introducir un nuevo plato, éste se coloca en la posición más accesible, encima del último plato. Cuando se toma un  plato, éste se extrae, igualmente, del punto más accesible, el último que se ha introducido. 

• Si somos más estrictos, otro ejemplo sería una caja llena de libros. Sólo podemos ver cuál es el libro que está más arriba en la caja, y si ponemos o tomamos un libro, sólo podremos actuar sobre este primer libro. No podemos siquiera saber el número total de libros guardados en la pila. Sólo sabremos el número de elementos de la pila de libros si previamente los sacamos hasta vaciar la caja.

• Otro ejemplo natural de la aplicación de la estructura pila aparece durante la ejecución de un programa de ordenador, en la forma en que la máquina procesa las llamadas a los procedimientos. Cada llamada a un procedimiento (o función) hace que el sistema almacene toda la información asociada con ese procedimiento (parámetros, variables, constantes, dirección de retorno, etc...) de forma independiente a otros procedimientos y permitiendo que unos procedimientos puedan invocar a otros distintos (o a si mismos) y que toda esa información almacenada pueda ser recuperada convenientemente cuando corresponda. Como en un procesador sólo se puede estar ejecutando un procedimiento, esto quiere decir que sólo es necesario que sean accesibles los datos de un procedimiento (el último activado, el que está en la cima).

videos relacionados

Código de pila en java

fuentes
http://www.programacionfacil.com/estructura_de_datos:pilas
http://www.lcc.uma.es/~lopez/modular/tads/pilas_colas.pdf

Una lista enlazada es un conjunto ordenado de datos, y utilizando la clase base List ...

Clase List
La clase List proporciona un área desplegable que contiene ítems seleccionables (uno por línea). Generalmente, un usuario selecciona una opción pulsando sobre ella, e indica que una acción debe ocurrir cuando hace doble-click sobre ella o pulsa la tecla Return. Las Listas (Lists) pueden permitir múltiples selecciones o sólo una selección a la vez. Otros componentes que pérmiten al usuario elegir entre varias opciones son checkbox, choice, y menu.
CheckBox: permite seleccionar una opción al usuario del programa o tomar una decisión, directamente en pantalla.
choice: permiten el rápido acceso a una lista de elementos. Por ejemplo, podríamos implementar una selección de colores y mantenerla en un botón Choice.

Linkedlist
La clase linkedlist proporciona métodos para obtener de manera uniforme el nombre, eliminar e insertar un elemento al principio y al final de la lista. Estas operaciones permiten a las listas enlazadas para ser utilizado como una pila, una cola o de dos extremos de la cola.

Arraylist
Es una objeto lista que implemente la interfaz Collection de java. Esta clase permite contener y ordenar objetos, incluso, puede almacenar objetos dupicados. Su tamaño es dinámico, es decir, esta lista crecera a medida que se inserten en ella mas elementos. Debememos recordar que el índice de un ArrayList empieza en 0, es decir, el primer elemento del ArrayList tiene como índice el 0

Nota: Los objetos ArrayList se comportan igual que un objeto Vector desincronizado, por lo tanto, un ArrayList se ejecuta mas rápido que un Vector, ya que el ArrayList no tiene que implementar los métodos de sincronización de procesos.

Un ArrayList contiene tantos objetos como necesitemos.
ArrayList tiene varios constructores, dependiendo de cómo necesitemos construir el ArrayList . Los siguientes dos constructores nos ayudarán a empezar:
ArrayList() construye un ArrayList con capacidad cero por defecto, pero crecerá según le vayamos añadiendo:
 ArrayList al = new ArrayList();
ArrayList(int initialCapacity) construye un ArrayList vacío con una capacidad inicial especificada:
 ArrayList al2 = new ArrayList(5);

Iterator
Un Iterator o Iterador es un patrón de diseño que nos ofrece una interfaz estándar para recorrer una estructura de datos sin que nos tengamos que preocupar por la representación interna de los datos de dicha estructura.
Esta forma de recorrer estructuras de datos ofrece muchas ventajas entre las que podemos destacar que nuestro código no depende de la estructura de datos.
Por lo tanto la “estructura” puede ser un árbol binario o una lista doblemente enlazada ya que el iterador nos abstrae del modo de realizar el recorrido. De este modo podemos sustituir de manera sencilla estructuras de datos en nuestro código sin que se nos presenten problemas desagradables.

Este patrón lo podemos sustituir por un bucle for, que haría básicamente lo mismo, pero la velocidad en la búsqueda es superior en el patrón iterator con respecto al bucle for.
En Java tenemos reflejado el patrón Iterator en la clase java.util.Iterator que es ampliamente utilizada en las conocidas Collections.

Listas Circulares

Definición:        

Una lista circular es una lista lineal en la que el último nodo a punta al primero.

No existen casos especiales, cada nodo siempre tiene uno anterior y uno siguiente.

Se representa:

 Operaciones básicas

Mostrar:

A la hora de buscar elementos en una lista circular, es necesario almacenar el puntero del nodo en que se empezó la búsqueda, para poder detectar el caso en que no exista el valor que se busca. Por lo demás, la búsqueda es igual que en el caso de las listas abiertas.

Inserción por la cabeza de lista enlazada 
 1. Crear un nuevo nodo. 

 2. Almacenar el dato en el campo correspondiente (datos). 

 3. Como va a ser el primer nodo, su enlace deberá apuntar al que hasta ahora era el primer nodo (apuntado por el enlace externo). 

 4. El enlace externo deberá apuntar al nuevo nodo (que ahora es el primero). 

Eliminacion 
Para ésta operación podemos encontrar tres casos diferentes:

• Eliminar un nodo cualquiera, que no sea el apuntado por lista. 

• Eliminar el nodo apuntado por lista, y que no sea el único nodo.
• Eliminar el único nodo de la lista.

  

eliminar un nodo en una lista circular con mas de  un elemento 

En el primer caso necesitamos localizar el nodo anterior al que queremos borrar. Como el principio de la lista puede ser cualquier nodo, haremos que sea precisamente lista quien apunte al nodo anterior al que queremos eliminar. 

Esto elimina la excepción del segundo caso, ya que lista nunca será el nodo a eliminar, salvo que sea el único nodo de la lista.

Una vez localizado el nodo anterior y apuntado por lista, hacemos que lista->siguiente apunte a nodo->siguiente.

Y a continuación borramos nodo. 

En el caso de que sólo exista un nodo, será imposible localizar el nodo anterior, así que simplemente eliminaremos el nodo, y haremos que lista valga NULL.

Tipos de listas

•          Listas enlazadas circulares simples.

•          Listas enlazada doblemente circular.

Listas enlazadas circulares simples.

Cada nodo tiene un enlace, similar al de las listas enlazadas simples, excepto que el siguiente nodo del ultimo apunta al primero.

 

 Listas enlazada doblemente circular.

En una lista enlazada doblemente circular, cada nodo tiene dos enlaces, las insercciones y eliminaciones se realizan desde cualquier punto.