Tipos de Datos Abstractos — pila, cola, lista enlazada
Introducido| English | Significado |
|---|---|
| queue/kjuː/ | cola |
| push/pʊʃ/ | empujar |
| abstract data type/ˈæbstrækt ˈdeɪtə taɪp/ | tipo de dato abstracto |
| stack/stæk/ | Pila |
| linked list/lɪŋkt lɪst/ | lista enlazada |
| LIFO/ˈlaɪfəʊ/ | LIFO (último en entrar, primero en salir) |
| pop/pɒp/ | sacar |
| pointer/ˈpɔɪntə/ | puntero |
| FIFO/ˈfaɪfəʊ/ | FIFO (primero en entrar, primero en salir) |
| enqueue/enˈkjuː/ | insertar en cola |
| dequeue/diːˈkjuː/ | extraer de cola |
| node/nəʊd/ | nodo |
| traverse/trəˈvɜːs/ | recorrer |
El botón Atrás y la cola de impresión
- Cada página que visitas se apila; el botón Atrás toma la superior. La página que dejaste más recientemente es la primera a la que vuelves.
- En el pasillo, una impresora procesa trabajos en el orden en que llegaron. El documento enviado primero sale primero, sin importar lo pequeños que sean los que están detrás.
- Dos estructuras, reglas opuestas, y usas ambas antes del recreo. Ninguna dice cómo está almacenada; cada una dice solo qué hacen sus operaciones.
- Eso es un tipo de dato abstracto (TDA). Esta lección cubre los tres que menciona el programa, las operaciones de cada uno y cómo justificar la elección de uno para una situación concreta.
¿Qué es un TDA?
- Un tipo de dato abstracto (TDA) es una colección de datos junto con un conjunto de operaciones sobre esos datos. Esa única oración es la definición de una marca.
- Se define por qué hacen las operaciones, no por cómo se almacenan los datos. La implementación está oculta, por lo que puede cambiar sin afectar al código que la utiliza.
- Una pila, una cola, una lista enlazada, un árbol binario y un array son todos TDAs.
Un Tipo de Dato Abstracto (ADT) se define por:
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Un ADT especifica las operaciones (la interfaz); la implementación está oculta y puede cambiar libremente.
La pila
- Una pila es una lista en la que los elementos se añaden y se eliminan por el mismo extremo, el tope, de modo que el último elemento añadido es el primero en eliminarse: LIFO (Last In, First Out / Último en entrar, Primero en salir).
- Operaciones: push añade al tope, pop elimina del tope, peek mira el tope, y pruebas para ver si está vacía o llena.
- Usos: historial de deshacer, el botón Atrás, direcciones de retorno de llamadas a funciones, comprobación de paréntesis, retroceso (backtracking).

Todo sucede en el tope
¿En qué orden funciona una pila?
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Una pila es LIFO: el elemento empujado más recientemente es el primero en ser extraído.
Ejemplo resuelto: rastrear la pila
- Una pila contiene, desde abajo
'P' 'N' 'Z' 'X' 'Y' 'W'; el puntero superior está en'W'. Se realizan las operacionesPOP,POP,PUSH 'A',PUSH 'B',POP. ¿Qué contiene la pila y dónde está el puntero? - Los dos pops eliminan
'W'luego'Y'. Los pushes colocan'A'luego'B'en su lugar. El último pop elimina'B'. - La pila contiene
'P' 'N' 'Z' 'X' 'A', con el puntero en'A'. El elemento más antiguo en la pila es el inferior,'P'; son posibles cinco pops más, y un sexto sería un error, por eso el pop comprueba primero si está vacía.
Una pila contiene P N Z X Y W (W está en la parte superior). Después de POP, POP, PUSH 'A', PUSH 'B', POP, ¿qué elemento queda en la parte superior?
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Se extraen W e Y, se empujan A luego B, se extrae B. La parte superior es A, sobre X.
La cola
- Una cola es una lista en la que los elementos se añaden en la parte trasera y se eliminan por el frente, de modo que el primer elemento añadido es el primero en eliminarse: FIFO (First In, First Out / Primero en entrar, Primero en salir).
- Operaciones: enqueue añade en la parte trasera, dequeue elimina del frente, y pruebas para ver si está vacía o llena.
- Usos: spooling de impresión, buffers de teclado, planificación, clientes en una tienda, búsqueda en anchura (breadth-first search).

Añade por atrás, sal por delante
Pilas, colas y listas enlazadas
LIFO vs FIFO
Una pila es último-en-primer-salir; el push y el pop ocurren en el mismo extremo (la parte superior).
Una cola es primero-en-entrar-primer-salir: los elementos se eliminan desde el ______ y se añaden en la parte trasera.
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
FIFO: dequeue desde el frente, enqueue en la parte trasera — como una fila de personas.
Ejemplo resuelto: describir añadir y eliminar de una cola
- Añadir: verificar que la cola no esté llena; almacenar el elemento en la posición indicada por el puntero trasero; mover el puntero trasero (y sumar uno al contador).
- Eliminar: verificar que la cola no esté vacía; leer el elemento en el puntero frontal; mover el puntero frontal (y restar uno al contador).
- Establece la convención que uses: si el puntero trasero marca el siguiente espacio libre, almacena primero y luego mueve; si marca el último elemento, mueve primero y luego almacena. Ambas obtienen puntos si eres consistente.
Ordena los pasos para añadir un elemento a una cola (el puntero rear marca el próximo espacio libre).
Dificultad 3/5 · 200 monedas + un pequeño bono en el primer intento de hoy
La comprobación viene primero; luego almacenar, luego mover, bajo esta convención. Indica qué convención usas.
La lista enlazada
- Una lista enlazada es una lista en la que cada nodo contiene un elemento de datos y un puntero al siguiente nodo, con un puntero de inicio al primer nodo. El puntero del último nodo es un valor de sentinela como
NULL. - Operaciones: insertar, eliminar, buscar y recorrer, siguiendo los punteros desde la cabeza para visitar cada nodo en orden.
- Ventaja sobre un array: insertar o eliminar es barato, solo reconfigurar punteros, y la lista crece según sea necesario. Desventaja: no hay acceso aleatorio; llegar al décimo nodo significa seguir nueve punteros.

Un valor y una flecha, repetidos
Una lista enlazada: nodos unidos por punteros
Cada nodo almacena un valor y un puntero al siguiente nodo. Insertar o eliminar solo re-conecta los punteros — ningún elemento se desplaza, a diferencia de un array.
Cada nodo de una lista enlazada contiene:
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Un nodo almacena su valor más un puntero (referencia) al siguiente nodo; el head marca el inicio, NULL el final.
Una lista enlazada hace que insertar/eliminar sea barato (solo reconfigurar punteros) pero el acceso aleatorio sea lento (hay que seguir los punteros desde el head).
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
Esa es la compensación entre array y lista: los arrays dan acceso O(1) por índice; las listas dan inserción/eliminación barata.
Ejemplo resuelto: añadir un nodo en orden
- Describe cómo se inserta un nuevo valor en una lista enlazada mantenida en orden ascendente. [4]
- Recorre la lista desde la cabeza, siguiendo los punteros, hasta encontrar el nodo anterior a la posición deseada: el último nodo cuyo valor sea menor que el nuevo.
- Toma un nodo libre y almacena el nuevo valor en él. Establece el puntero del nuevo nodo a la dirección a la que actualmente apunta el nodo anterior.
- Luego establece el puntero del nodo anterior al nuevo nodo. Si el nuevo valor debe ir al principio, cambia el puntero de cabeza en su lugar.
Ordena los pasos para insertar un valor en una lista enlazada ordenada.
Dificultad 3/5 · 200 monedas + un pequeño bono en el primer intento de hoy
Encontrar, rellenar, apuntar el nuevo nodo hacia adelante, luego reconfigurar el nodo anterior. Invertir los últimos dos pierde el resto de la lista.
Justificar la elección
- Los elementos deben manejarse en el orden en que llegaron, trabajos de impresión, pulsaciones de tecla, clientes: una cola, porque es primero en entrar, primero en salir.
- El elemento más reciente debe manejarse primero, deshacer, retroceder, llamadas anidadas: una pila, porque es último en entrar, primero en salir.
- Los elementos se insertan o eliminan frecuentemente en el medio de una colección ordenada, y el tamaño es desconocido: una lista enlazada, porque solo cambian los punteros y nada se desplaza.
- Nombra la estructura, nombra su regla, vincula la regla a la situación.
Empareja cada ADT con su regla y un uso típico.
Dificultad 2/5 · 140 monedas + un pequeño bono en el primer intento de hoy
Pila = último-en-entrar-primer-salir; cola = primero-en-entrar-primer-salir; una lista enlazada encadena nodos con punteros.
Los trabajos de impresión deben imprimirse en el orden en que fueron enviados. ¿Qué ADT y por qué?
Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy
El orden de llegada sigue la regla FIFO. Una pila imprimiría el trabajo más reciente primero.
TDA versus implementación
- El TDA es el comportamiento: push y pop, enqueue y dequeue, insertar y recorrer.
- La implementación es el almacenamiento: en este curso, un array más unas pocas variables de puntero (siguiente lección).
- Una pregunta sobre el TDA busca operaciones y reglas; una pregunta sobre la implementación busca arrays, punteros y las comprobaciones.
Marcas que se pierden
- Push y enqueue comprueban primero si está llena; pop y dequeue comprueban primero si está vacía. Escribe la comprobación en la descripción.
- Insertar en una lista enlazada: establece el puntero del nodo nuevo antes de cambiar el del nodo anterior, o se pierde el resto de la lista.
- Una pila cambia en un extremo, una cola en ambos. "Eliminar del tope de la cola" es una respuesta de pila.
- Desarrolla las abreviaturas una vez: LIFO, último en entrar primero en salir; FIFO, primero en entrar primero en salir.
Lo has logrado
- un TDA es una colección de datos junto con un conjunto de operaciones sobre ellos; comportamiento, no almacenamiento
- pila: añadir y eliminar en el tope, LIFO, push y pop · cola: añadir en la parte trasera, eliminar en el frente, FIFO, enqueue y dequeue
- lista enlazada: nodos de valor + puntero desde un puntero de cabeza; inserción y eliminación baratas, acceso aleatorio lento; recorrer siguiendo punteros
- justifica por regla: orden de llegada → cola; más reciente primero → pila; inserción frecuente en el medio → lista enlazada