LISTAS

Definicion.

Una lista es una estructura de datos lineal que se puede representar
simbólicamente como un conjunto de nodos enlazados entre sí. Entre las listas se distinguen tres tipos:
listas simplementes ligadas, listas doblementes ligadas y listas circulares.
Una lista simplemente ligada constituye una coleccion de elementos llamados nodos. El orden entre estos se
establece por medio de punteros, es decir, direcciones o referencias a otros nodos.

Elementos de las listas simplementes ligadas.

Nodos. Es un objeto que guarda una referencia a un elemento y una referencia, llamado siguiente, a otro nodo.
Punteros. Establecen el orden entre los nodos

Operaciones con listas simplementes ligadas.

Busqueda. Comprueba si existe un determinado elemento en la lista.
Insercion. Consiste en la introducción de un nuevo elemento en la lista.
Eliminacion. La operación borrar consiste en la eliminación de la lista de un elemento concreto. El elemento a borrar será escogido por el programador.
Recorre. Recorre toda la lista, realizando una operación en cada nodo.

Algoritmo con listas simplementes ligadas.

Crea inicio.

{Este algoritmo permite crear una lista simplemente ligada, agregando cada nuevo nodo al inicio de la misma}
{P y Q son variables de tipo puntero. Los campos del nodo son INFO, que sera del tipo de datos que se quiera  almacenar en la lista, y la LIGA de tipo apuntador. P apunta al inicio de la lista. RES es una variable de tipo entero}

Crea final

{Este algoritmo permite crear una lista simplemente ligada, agregando cada nuevo nodo al final de la misma}
{P, Q y T son variables de tipo apuntador. Los campos del nodo son INFO, que sera del tipo de datos que se quiera almacenar al final de la lista, y LIGA de tipo apuntador. P apunta al inicio de la lista. RES es una
variable de tipo entero}

Recorrido iterativo.

Recorre_iterativo(P)
{Este algoritmo recorre una lista cuyo primer nodo esta apuntando por P}
{Q es una variable de tipo apuntador. INFO y LIGA son los campos de cada nodo de la lista}

Recorrido recursivo.

Recorre_recursivo(P)
{Este algoritmo recorre una lista simplemente ligada en forma recursiva. P es un apuntador al nodo que se va a visitar. La primera vez trae la direccion del primer nodo de la lista}
{INFO y LIGA son los campos de cada nodo de la lista}

Insercion al inicio.

Inserta_inicio(P,DATO)
{Este algoritmo inserta un nodo al inicio de una lista simplemente ligada. P es el apuntador al primer nodo de
la misma, y DATO es la informacion que se almacenara en el nuevo nodo}
{Q es una variable de tipo apuntador. INFO y LIGA son los campos de cada nodo de la lista}

Insercion al final

Inserta_final(P,DATO)
{Este algoritmo inserta un nodo al final de una lista simplemente ligada. P es el apuntador al primer nodo de
la lista, y DATO es la informacion que se almacenara en el nuevo nodo}
{Q y T son variables de tipo puntero. INFO y LIGA son los campos de cada nodo de la lista}

Insercion de un nodo antes que otro

Inserta_antes_X(P,DATO,X)
{Este algoritmo inserta un nodo antes de un nodo dado como referencia en una lista simplemente ligada. P es el apuntador al primer nodo de la lista, DATO indica la informacion que se almacenara en el nuevo nodo, y X representa el contenido -informacion- del nodo dado como referencia}
{Q, X y T son variables de tipo apuntador. INFO y LIGA son los campos de los nodos de la lista. BAND es una variable de tipo entero}

Insercion de un nodo despues de otro

Inserta_despues_X(P,DATO,X)
{Este algoritmo inserta un nodo despues de otro dado como referencia en una lista simplemente ligada. P es el apuntador al primer nodo de la lista, DATO indica la informacion que se almacenara en el nuevo nodo, y X representa el contenido  -informacion- del nodo dado como referencia}
{Q y T son variables de tipo apuntador. INFO y LIGA son los campos de los nodos de la lista. BAND es una variable de tipo entero}

Eliminar el primer nodo

Elimina_inicio(P)
{Este algoritmo permite eliminar el primer elemento de una lista simplemente ligada. P es el apuntador al primer nodo de la lista}
{Q es una variable de tipo apuntador. INFO y LIGA son los campos de los nodos de la lista}

Eliminar el ultimo nodo

Elimina_ultimo(P)
{Este algoritmo permite eliminar el ultimo elemento de una lista simplemente ligada. P es el apuntador al primer nodo de la lista}
{Q y T son variables de tipo apuntador. INFO y LIGA son los campos de los nodos de la lista}

Eliminar un nodo con informacion X

Elimina_X(P,X)
{Este algoritmo elimina un nodo con informacion X de una lista simplemente ligada. P es el apuntador al primer nodo de la lista}
{Q y T son variables de tipo apuntador. BAND en una variable de tipo entero, INFO y LIGA son los campos de los nodos de la lista}

Busqueda desordenada

Busqueda_desordenada(P,X)
{Este algoritmo permite buscar el elemento con informacion X en una lista simplemente ligada que se encuentra  desordenada. P es el apuntador al primer nodo de la lista}
{Q es una variable de tipo apuntador. INFO y LIGA son campos de los nodos de la lista}

Busqueda ordenada

Busqueda_ordenada(P,X)
{Este algoritmo permite buscar el elemento con informacion X en una lista simplemente ligada que se encuentra ordenada en forma ascendente. P es el apuntador al primer nodo de la lista}
{Q es una variable de tipo apuntador. INFO y LIGA son los campos de los nodos de la lista}

Busqueda de manera recursiva(P,X)

Busqueda_recursivo
{Este algoritmo permite buscar recursivamente a un elemento con informacion X en una lista simplemente ligada que se encuentra desordenada. P es el apuntador al primer elemento de la lista}

Aplicaciones.

Se puede señalar que las listas son muy utiles para aquellas aplicaciones donde se necesite dinamismo
en el crecimiento y reduccion de la estructura de datos usada para el almacenamiento de la informacion.

COLAS

Definición.

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.

Política.

Las colas también reciben el nombre de estructuras FIFü (First-In, First-Out: el primero en entrar es el primero en
salir).

Elementos.

Cuando se implementan con arreglos unidimensionales, es importante definir un
tamaño máximo para la cola y dos variables auxiliares. Una de ellas para que almacene
la posición del primer elemento de la cola -FRENTE- y otra para que guarde:
la posición del último elemento de la cola -FINAL-.

Operaciones con colas.

Insertar un elemento en la cola. Las inserciones se llevaran a cabo por el FINAL.
Eliminar un elemento de la cola. La eliminaciones se harán por el FRENTE.
Cola vacía. Es un método que nos indica si la cola esta vacía.
Cola llena. Es un método que nos dice si la cola esta llena.

Algoritmos.

Insertar

Inserta_cola(COLA,MAX,FRENTE,FINAL,DATO)
{Este algoritmo inserta el elemento DATO al final de una estructura tipo cola. FRENTE y FINAL son los punteros
que indican, respectivamente, el inicio y fin de COLA. La primera vez FRENTE y FINAL tienen el valor 0, ya que
la cola esta vacía. MAX es el máximo numero de elementos que puede almacenar la cola.}

Eliminar

Elimina_cola(COLA,FRENTE,FINAL,DATO)
{Este algoritmo elimina el primer elemento de una estructura tipo cola y lo almacena en DATO. FRENTE y FINAL
son los punteros que indican, respectivamente, el inicio y fin de la cola.}

Cola vacía

Cola_vacía(COLA,FRENTE,BAND)
{Este algoritmo determina si una estructura de tipo cola esta vacía, asignando a BAND el valor de verdad
correspondiente.}

        1. Si (FRENTE = 0)

Cola llena

Cola_llena(COLA,FINAL,MAX,BAND)
{Este algoritmo determina si una estructura de tipo cola esta llena, asignando a BAND el valor de verdad
correspondiente. MAX es el numero máximo de elementos que puede almacenar COLA.}

Aplicaciones.

Una aplicación común de las colas se presenta cuando se envía a imprimir algún documento o programa
en las colas de impresión. Cuando hay una sola impresora para atender a varios usuarios, suele suceder
que algunos de ellos soliciten los servicios de impresión al mismo tiempo o mientras el dispositivo este
ocupado. En estos casos se forma una cola con los trabajos que esperan para ser impresos; estos se procesaran en el orden el cual fueron introducidos en la cola.

PILAS

Definición.
Una pila (stack en inglés) es una lista ordinal o estructura de datos que permite almacenar y recuperar datos.
Una pila representa una estructura lineal de datos en las que se puede agregar o quitar elementos unicamente por los dos extremos.
En consecuencia, los elementos de una pila se eliminan en orden inverso al que se insertaron. Las pilas son estructuras de datos lineales,
como los arreglos, ya que los componentes ocupan lugares sucesivos en la estructura y cada uno de ellos tiene un único sucesor y un único predecesor, con excepción del último y del primero, respectivamente.

Politica.
se le conoce como estructura LIFO (Last-Input, First-Output: el último en entrar es el primero en salir).

Elementos.
1.- Un vector que sera el contenedor de los elementos que deseamos agregar en la pila.
private Vector [] pila = new Vector[5];
2.- Un indice del vector al que llamaremos cima el cual apunta al ultimo elemento que esta en la pila considerando la politica de estas.
private int cima = 0;

Operaciones con pilas.
Pila vacia. Es un metodo que nos indica si la pila esta vacia.
Pila llena. Es un metodo que nos dice si la pila esta llena.
Push. Operación de la pila que nos permite agregar elementos en la misma.
Pop. Operación de las pilas que se usa para sacar elementos de la misma.

Algoritmo.

Pila llena.

private boolean pilaLlena(){
        if(cima==pila.length){
            return true;
        }else{
            return false;
        }
    }

Pila vacia.

private boolean pilaVacia(){
        if(cima<0){
            return true;
        }else{
            return false;
        }
    }

Push.

public void push(Vector v){
        if(pilaLlena()){
            System.out.println("Ya no puede agregar");
        }else{
            Vector[cima]=v;
            cima++;
        }
    }

Pop.

 public Vector pop(){
        Vector v = null;
        if(pilaVacia()){
            System.out.println("La pila esta vacia");
        }else{
            cima--;
            v=Vector[cima];
        }
        return v;
    }

Aplicaciones.

Las pilas son utilizadas ampliamente para solucionar una amplia variedad de problemas.
Se utiliza en compiladores, sistemas operativos y en programas de aplicación.