Pilas

Continuando con el curso de Estructuras de datos, en esta entrada aprenderemos sobre las pilas, ¿Que son las pilas?, ¿Como funcionan? y sus operaciones.

¿Que es una pila?

Se podría decir que es una lista ordinal, o estructura de datos en la que el modo de acceso de sus elementos es de tipo LIFO "FAST IN FIRST, OUT" que en español es ultimo en entrar, primero en salir.

y que nos permite almacenar datos y recuperar datos.

Otro concepto podría ser:

Tipo especial de lista abierta en la que solo se pueden insertar y eliminar nodos en uno de los extremos de la lista

¿Como funcionan?

La pila es un contenedor de NODOS y tiene dos operaciones basicas que son PUSH(añade)  y POP(Quita)
Push añade un nodo en la parte superior de la pila, dejando por debajo el resto de los nodos y pop elimina y devuelve el actual nodo superior de la pila

Operaciones 

• Crear: se crea la pila vacía. 

• Apilar: se añade un elemento a la pila.(push)

• Quitar elemento: se elimina el elemento frontal de la pila.(pop)

• Cima pila: devuelve el elemento que esta en la cima de la pila. (top o peek)

• Pila Vacía: devuelve cierto si la pila está vacía o falso en caso contrario.

Listas Doblemente Enlazadas

Continuando con el curso de Estructuras de datos.!

En esta entrada aprenderemos sobre las listas doblemente enlazadas, ya hemos aprendido sobre las listas enlazadas así que sin mas preámbulo veamos que son las listas doblemente enlazadas.

¿Que son?

Podemos definir un lista doblemente enlazada como una estructura que consiste en un conjunto de nodos enlazados sucesivamente, y en este caso a diferencia de las listas simplemente enlazadas cada nodo contiene dos enlaces, que respectivamente un enlace hace referencia al nodo siguiente y el otro al nodo anterior en la secuencia de los nodos.

El enlace al nodo anterior del primer nodo apunta a NULL, así como el enlace al nodo siguiente del ultimo nodo también apunta a NULL.

A diferencia de la lista simplemente enlazada podemos decir que la lista doblemente enlazada posee o recorre dos direcciones, hacia siguiente y hacia anterior.

En este tipo de listas enlazadas podemos realizar el mismo tipo de operaciones básicas que se hacen en la lista simplemente enlazada para manipular los datos con la única diferencia que los datos los podemos manipular de los dos sentidos.

• Inicialización o Creación
• Insertar elementos a la lista: Inserta un Nodo "x" en la lista, pudiendo realizarse la inserción al principio o al final de la lista.
• Eliminar elementos de la lista: Elimina un Nodo de la lista, puede ser por su posición o por su dato.
• Buscar elementos de la lista: Busca un elemento de la lista.
• Recorrer la lista enlazada.
• Comprobar si la lista esta vacía.

Eliminar nodo especifico y buscar elemento en la lista.

Eliminar un nodo en especifico

El eliminar un nodo en especifico se puede realizar en base al siguiente algoritmo.

Algoritmo

1.       1. Sí la lista no está vacía.

a.       Sí inicio es igual a fin y elemento es igual a inicio de datos.

                                                               i.      Inicio apunta a inicio y fin apunta a nulo.

b.       Sí no elemento igual a inicio de dato.

                                                               i.      Inicio apunta a inicio de siguiente.

c.       Sí no

                                                               i.      Crear nodo, anterior y siguiente.

                                                             ii.      Anterior igual a inicio.

                                                           iii.      Temporal igual a inicio de siguiente.

                                                           iv.      Mientras temporal sea diferente a nulo y temporal de dato sea nulo a elemento.

1.       Anterior a igual de anterior de siguiente.

2.       Temporal igual temporal de siguiente.

                                                             v.      Sí temporal es diferente de nulo.

1.       Anterior de siguiente igual a temporal de siguiente.

2.       Sí temporal igual a fin.

a.       Fin igual a anterior.

 Codificado en JAVA seria de la siguiente manera:

Buscar un elemento.

Ejemplo codificado en JAVA para buscar un elemento en la lista.

Eliminar nodos de la lista.

Para eliminar un nodo al inicio de la lista se crea un método y tiene que cumplirse lo siguiente condición:

Sí inicio es igual a fin.

Es decir, que inicio y fin sean iguales y ambos apunten a nulo. Esto se realiza por el siguiente algoritmo.

Algoritmo.

1. Elemento es igual a inicio de dato.

2. Sí inicio es igual a fin.

     a) Inicio apunta a nulo.

     b) Fin apunta a nulo.

3. Sí no

     a) Inicio apunta a inicio de siguiente.

4. Retorna el elemento.

Codificado en Java quedaría de la siguiente manera:

Eliminar al final de la lista


Este es el ejemplo codificado para eliminar un elemento al final de la lista.

Listas Enlazadas

Una lista enlazada es un TDA que nos permite almacenar datos de forma ordenada, al igual que los vectores pero con la diferencia que esta estructura es dinámica.

También podemos verlo como una secuencia de elementos dispuestos uno detrás de otro, en el cual cada elemento se conecta al siguiente por medio de un enlace.

En una lista enlazada cada elemento apunta al siguiente, excepto el ultimo que apunta a null, Los elementos de una lista reciben el nombre de NODOS. 

En una lista enlazada el elemento principal es el NODO.

Pero ¿Que es un nodo?
Es una estructura sencilla que almacena información y ademas hace referencia a algún otro nodo y para hacer esa referencia utilizamos el puntero, la idea es que el puntero haga referencia a otro objeto de tipo nodo.

¿Que es un puntero?

Es una variable que contiene una dirección de memoria de un dato o de otra variable que contiene al dato en un arreglo.

 El NODO se compone de dos campos:

• La información (Dato o Información)
• La referencia (Enlace)

Para que esta estructura sea un TDA de tipo lista enlazada debe de tener algún tipo de operadores que nos permitan la manipulación de los datos que contiene.

Las operaciones básicas en una lista enlazada son:

• Inicialización o Creación
• Insertar elementos a la lista: Inserta un Nodo "x" en la lista, pudiendo realizarse la inserción al principio o al final de la lista.

• Eliminar elementos de la lista: Elimina un Nodo de la lista, puede ser por su posición o por su dato.
• Buscar elementos de la lista: Busca un elemento de la lista.
• Recorrer la lista enlazada.
• Comprobar si la lista esta vacía.

Existen distintos tipos de listas enlazadas las cuales son:

• Listas Simplemente Enlazadas
• Listas Doblemente Enlazadas
• Listas Circular Simplemente Enlazadas
• Listas Circular Doblemente Enlazadas

Mas adelante estaremos hablando de cada una de ellas.!

    

RECURSIVIDAD

¿Qué es la recursividad?

Es un proceso de recurrencia con n repeticiones, replicando algo que ya ocurrió. En Java es un procedimiento para resolver un problema complejo reduciéndolo a uno o más subproblemas; un método se puede llamar a si mismo.

Características de la Recursividad.

• Tiene las misma estructura que el problema original.
• Más simple de resolver.
• Los subproblemas se dividen usando el mismo procedimiento.
• Los subproblemas se hacen más simples.

Estructura general de un algoritmo recursivo.

Un ejemplo puede ser el factorial de un numero donde: 

n! = 1 * 2 * 3 * 4 ... *(n - 1) * n

Codificado en Java seria: 

Public int factorial(int n) {

   if (n == 0){                                      

      return 1;

   } else {

      return n  * factorial(n - 1);

   }

}

Donde el caso base es:

 Public int factorial(int n) {

   if (n == 0){                                      

      return 1;

   }

}

Y el dominio es:

else {

      return n  * factorial(n - 1);

   }

Otro ejemplo es la solución de la sucesión de Fibonacci, que es la suma de los dos números anteriores. Iniciando esta serie con 0 y 1, dicha sucesión es infinita...

Vídeo de ejemplo... ↓↓

Memoria Dinámica

¿Qué es memoria dinámica?

Es un espacio de memoria la cual su tamaño puede variar durante la ejecución del programa, es decir los datos que su tamaño pude variar ya que los datos pueden crearse o destruirse a lo largo de la ejecución del programa, a este tipo de datos se le puede llamar Datos Dinámicos.

Esto permite dimensionar la estructura de datos de una forma precisa: se va asignando memoria en tiempo de ejecución según se va necesitando.

Para implementar la memoria dinámica utilizaremos la clase ArrayList, que es una clase que nos permite almacenar datos en memoria de forma similar a los Arrays, con la ventaja que el numero de elementos que almacena lo hace de forma dinámica.

Es decir los ArrayList nos permiten añadir, eliminar y modificar elementos en tiempo de ejecución.

y los principales métodos para trabajar con Arrays son los siguientes:

Ejemplos de declaración de cada uno de los métodos:

// Añade el elemento al ArrayList

nombreArrayList.add("Elemento");

// Añade el elemento al ArrayList en la posición 'n'

nombreArrayList.add(n, "Elemento 2");

// Devuelve el numero de elementos del ArrayList

nombreArrayList.size();

// Devuelve el elemento que esta en la posición '2' del ArrayList

nombreArrayList.get(2);

// Borra el elemento de la posición '5' del ArrayList  

nombreArrayList.remove(5);

// Borra la primera ocurrencia del 'Elemento' que se le pasa como parámetro. 

nombreArrayList.remove("Elemento");

 AQUÍ UN EJEMPLO DE ARRAYLIST  | VÍDEO | ↓↓