.jpg)
Listas Enlazadas, Pilas y Colas
Tabla de contenidos
.png)
Sesión 3 (teoría): Pilas y Colas
.png)
Transparencias
-trans.png)
Lecturas
-
Data Structures and Problem Solving Using Java de Mark A. Weiss (3ª edición): secciones 6.3 (Colas) y 6.4 (Listas Enlazadas); introducción a la sección 15.1 (Implementaciones Dinámicas con Arrays) y sección 15.1.2 (Colas); introducción a la sección 15.2 (Implementaciones con Listas Enlazadas) y sección 15.2.2 (Colas); sección 15.4 (Colas Dobles); section 6.8 (Colas con Prioridad).
-
Data Structures and Algorithms in Java de Michael T. Goodrich y Roberto Tamassia (1ª ed.): apartados 3.2 (Colas), 3.3 (Listas Enlazadas), 3.4 (Colas Dobles) y 6.1 (El Tipo Abstracto Cola con Prioridad).
-
Data Structures and Algorithms in Java de Michael T. Goodrich y Roberto Tamassia (4ª ed.): secciones 3.2 (Listas Simplemente Enlazadas), 5.2 (Colas), 5.3 (Colas Dobles) y 8.1 (El Tipo Abstracto Cola con Prioridad).
.png)
Actividades para casa
Repaso
Repasa la materia de esta clase y lee los textos recomendados.
Cuestión
Desarrolla teóricamente (no es necesario programarlo en detalle) una solución al problema de balanceo de múltiples símbolos en lenguajes de programación que se ha introducido en la primera sesión de esta unidad.
Cuestión
Indica por qué en una pila implementada sobre una lista enlazada es más eficiente asociar la cima de la pila al principio de la lista, y no al revés.
Ejercicio
Programa una pila mediante un array de tal forma que, en la operación push, no se lance una excepción cuando se sobrepase el tamaño del array, sino que se sustituya el array por uno nuevo con el doble de tamaño.
Cuestión
En la implementación de una cola mediante lista enlazada se insertan datos por el final de la lista, y se extraen por el principio de la misma. Es posible hacerlo al contrario, esto es, extrayendo datos por el final e insertándolos por el principio. Sin embargo, sería considerablemente menos eficiente. Razona por qué.
Ejercicio
Programa una cola utilizando un array.
.png)