PDF de programación - Estructuras de Datos en Lenguaje Java

Universidad de Santiago de Chile
Facultad de Ingeniería
Departamento de Ingeniería Industrial



Estructuras de Datos
Abstractas en Lenguaje

Java

Listas Enlazadas, Colas, Pilas y Árboles Binarios



Creado por Carlo Casorzo G. para el curso Fundamentos

de Informática Industrial



Índice

Consideraciones previas .................................................................................. 3

1. Almacenamiento de datos ............................................................................ 4
1.1 El problema de los arreglos ......................................................................... 4
1.2 Una solución: la Lista Enlazada y las
estructuras de datos en base a punteros ....................................................... 5

2. Lista Enlazada Simple .................................................................................. 7
2.1 Qué es una lista enlazada ............................................................................. 7
2.2 Cómo acceder a un elemento de una lista .................................................... 9
2.3 Diseño de la clase ListaEnlazada.................................................................. 10
2.3.1 Método añadir() ............................................................................................ 11

2.3.2 Método encontrar() ....................................................................................... 13

2.3.3 Método remover() ......................................................................................... 13

2.3.4 Desafíos para el alumno ............................................................................... 15


3. Pila ..................................................................................................................... 16
3.1 Qué es una pila ............................................................................................. 16
3.2 Diseño de la clase Pila ..................................................................................17
3.2.1 Método verPrimero() .....................................................................................17

3.2.2 Método sacar() .............................................................................................. 18

3.2.3 Método apilar() ............................................................................................. 18

3.2.4 Desafíos para el alumno ............................................................................... 20


4. Cola ................................................................................................................... 21
4.1 Qué es una cola ............................................................................................ 21
4.2 Diseño de la clase Cola ................................................................................ 22
4.2.1 Método enfilar() ............................................................................................ 22

4.2.2 Método sacar() ............................................................................................. 23

4.2.3 Desafíos para el alumno ............................................................................... 24


5. Árbol Binario .................................................................................................. 25
5.1 Conceptos básicos ........................................................................................ 25
5.2 Qué es un árbol binario ................................................................................ 28
5.2.1 Recorrido en árboles binarios........................................................................ 29

5.3 Diseño de la clase ArbolBinario................................................................... 31
5.3.1 Método buscar() ........................................................................................... 33

5.3.2 Método insertar() ......................................................................................... 33

5.3.3 Método mostrarPreOrden() .......................................................................... 34

5.3.4 Método mostrarInOrden () ........................................................................... 34

5.3.5 Método mostrarPosOrden () ......................................................................... 35

5.3.6 Desafíos para el alumno ............................................................................... 35


6. La aplicación ilustrativa ............................................................................... 36



2

Consideraciones previas


1) Sobre la estructura de programación usada.

La forma en que se muestran las estructuras de datos Lista Enlazada, Cola y Pila es sólo
una manera alternativa de implementación. La idea de este tutorial es complementar los
ejemplos de implementación propuestos en el laboratorio y cátedra, para que el alumno se
de cuenta que puede diseñar estas estructuras de la manera que estime más conveniente o
que más se ajuste al problema a solucionar, mientras entienda el concepto fundamental de
la implementación de ellas.



2) Pre requisitos para entender este tutorial

Para la total comprensión de este tutorial, es necesario que el alumno domine los temas
propuestos en el libro Sam’s Teach Yourself Java in 21 Days, desde el capítulo 1 hasta el
7, en especial la sección “Referencia a objetos”, capitulo 4, página 99. También es
importante echar un vistazo al capítulo 16, “Circunstancias excepcionales, manejo de
errores y seguridad”.



3) Sobre los códigos y la aplicación ilustrativa

Los códigos de lista enlazada, cola y pila usados en este tutorial están incluidos en las
carpetas “Lista Enlazada Simple”, “Cola” y “Pila”. La aplicación ilustrativa está en la
carpeta “Aplicación Ilustrativa”. Para ejecutarla, solo se debe hacer doble clic en
AplicaciónIlustrativa.exe.



3

1. Almacenamiento de datos

1.1 El problema de los arreglos

Los arreglos y las estructuras de datos (listas, colas, pilas, etc.) son entes informáticos
abstractos que nos permiten almacenar datos, es decir, en un lenguaje de programación
como Java, objetos y/o tipos primitivos (int, double, char, boolean, etc...).

Los arreglos son, probablemente, la estructura más usada para almacenar y ordenar datos
dentro de la programación, debido a que la sintaxis para acceder a sus datos es muy
amigable para el programador. Por ejemplo, si tenemos un arreglo de int’s, y queremos
sumar el segundo número de un arreglo con el cuarto, simplemente usamos la notación [ ]
para acceder a ellos:



O, por ejemplo, si queremos llenar un arreglo con todas las letras minúsculas, desde la a la
z, simplemente hacemos:



(*)

(*) ver “Conversión por cast”, capitulo 4, página 100


Y así, minúsculas sería igual a {'a', 'b', 'c', 'd',..., 'z'}.
Si tratamos de representar gráficamente lo que un arreglo significa en la memoria,
podríamos analizar el siguiente esquema:



Y para acceder a un objeto en el arreglo, simplemente hacemos referencia a su índice y
usamos la notación [ ].



4

Pero esta forma de almacenamiento tiene ciertas desventajas, por ejemplo:


1) Los arreglos tienen una capacidad de almacenamiento determinada y no
modificable, lo que se transforma realmente en un problema si queremos
almacenar datos sin saber cuantos almacenaremos en total, o si la cantidad de datos
es variable.

2) Por (1), los programadores utilizan arreglos “lo suficientemente grandes”,
desperdiciando espacio de memoria que nunca se utiliza. Por ejemplo, si queremos
registrar a los clientes que compraron en nuestra tienda cada día, podríamos crear
un arreglo de una capacidad estimada de 100 espacios para cada día. Pero en el
caso que en una ocasión sólo entraran a comprar 22 clientes, 78 espacios del
arreglo son desperdiciados, y, por lo tanto, espacio en la memoria es desperdiciado.
O peor aún, que entraran 150 personas a comprar y que nuestro arreglo no fuera
capaz de almacenar a todos los clientes. En estos casos, los arreglos no son la
herramienta indicada.

3) La inserción de un objeto al principio del arreglo, sin sobrescribir el primer
espacio, se torna mas complicada, pues debemos correr en un espacio a la derecha
a todo el resto de los datos. Es decir, los arreglos no manejan los datos de forma
dinámica.



Para arreglar este problema, haremos uso de una nueva forma de almacenamientos: las
estructuras datos basadas en punteros, con su principal exponente, la Lista Enlazada.



1.2 Una solución: la Lista Enlazada y
estructuras de datos en base a punteros

Para entender este tipo de estructuras es necesario tener claro algunos conceptos:

puntero/apuntado: un puntero es un espacio en la memoria que almacena una referencia
o dirección de memoria de otra variable, conocida como su apuntado. El valor de un
puntero puede ser null, lo que significa actualmente no se refiere a ningún apuntado.

referencia: la operación de referencia en un puntero sirve para tener acceso a su apuntado.

Asignación de puntero: una operación de asignación entre dos punteros, como p=q, hace
que los dos punteros se refieran (o apunten) al mismo apuntado. No se copia dos veces en
la memoria al apuntado, sino que los dos punteros almacenan la dirección de memoria del
apuntado.


Ahora bien, para solucionar el problema encontrado al usar arreglos en ese tipo de
situaciones, introduciremos un nuevo tipo de