Pilas y colas para TAI: 8 ejercicios de FIFO y LIFO
Una pila y una cola son tipos abstractos de datos lineales que se parecen solo a primera vista. Ambos conservan una secuencia de elementos, pero establecen reglas diferentes sobre qué elemento puede salir. La pila aplica LIFO (last in, first out): lo último que entra es lo primero que sale. La cola aplica FIFO (first in, first out): lo primero que entra es lo primero que sale. En un ejercicio, esa pequeña diferencia decide cada salida.
Los ocho casos siguientes son originales y didácticos, no oficiales. Sirven para entrenar trazas, operaciones y condiciones límite, no para prometer una frecuencia de examen. El anexo V, II.3 de la convocatoria estatal publicada en el BOE incluye «Tipos abstractos y Estructuras de datos… Algoritmos…», pero no nombra Python ni indica frecuencia de preguntas. Python es aquí un instrumento de comprobación, no un lenguaje exigido por el programa.
Antes de resolver: contrato, implementación y orientación
Un TAD define qué se puede hacer y las reglas que deben cumplirse; una implementación decide cómo se guardan los datos. Pila es un contrato con operaciones como apilar, consultar cima, desapilar y comprobar vacío. Puede implementarse con un vector, una lista dinámica o nodos enlazados. Cola también es un contrato: encolar al final, consultar frente y desencolar por el frente. Un buffer circular o una lista enlazada son decisiones posteriores. Si el enunciado pregunta por LIFO o FIFO, pregunta por el tipo; si pregunta por índices, punteros, memoria o desplazamientos, pregunta por la implementación.
Usaremos una sola orientación para no invertir dibujos a mitad de ejercicio. Una pila se escribe de base → cima, con la cima a la derecha: [A, B, C] tiene A abajo y C arriba. Una cola se escribe de frente → final, también de izquierda a derecha: [A, B, C] tiene a A esperando para salir y a C como recién llegado. La primera operación útil no es ejecutar código: es etiquetar ambos extremos.
Método de traza
Para cada fila escribe estado inicial, operación, salida y estado resultante. No borres un elemento al consultarlo. No supongas tampoco una política de capacidad si el problema no la da: una estructura llena puede rechazar, bloquear, ampliar o expulsar; no son equivalentes. En los bloques se usan listas o collections.deque por claridad. La documentación oficial explica listas como pilas, listas como colas y la clase deque.
Ejercicio 1. Pila: entra, sale y vacía
Partimos de []. Apilamos A, apilamos B, desapilamos una vez, apilamos C y vaciamos. La secuencia de estados es [], [A], [A, B], [A], [A, C], []. La primera salida es B, porque estaba en la cima; el vaciado produce C y después A. El error típico sería hacer salir A por leer la lista desde la base en vez de aplicar LIFO.
pila = []
pila.append("A"); pila.append("B")
sale = pila.pop(); pila.append("C")
vaciado = [pila.pop(), pila.pop()]
assert sale == "B" and vaciado == ["C", "A"]
print(f"sale={sale}; vaciado={vaciado}")sale=B; vaciado=['C', 'A']append y pop() actúan a la derecha; por eso la representación coincide exactamente con la convención base→cima. Este código no demuestra que Python sea requisito de una prueba: solo verifica la traza que ya debíamos poder hacer a mano.
Ejercicio 2. Cola: FIFO con deque
En una cola vacía entran A y B; sale uno; entra C; finalmente se vacía. Los estados son [A], [A, B], [B], [B, C], []. Las salidas, en orden, son A, B, C. Inserción al final y extracción al frente son dos extremos distintos.
from collections import deque
cola = deque()
cola.append("A"); cola.append("B")
sale = cola.popleft(); cola.append("C")
vaciado = [cola.popleft(), cola.popleft()]
assert sale == "A" and vaciado == ["B", "C"]
print(f"sale={sale}; vaciado={vaciado}")sale=A; vaciado=['B', 'C']deque expresa la intención: append incorpora por el final y popleft retira por el frente. Una lista permitiría simularlo, pero eliminar por su primer índice desplaza los demás elementos; no es una buena implementación de cola si esa operación se repite.
Ejercicio 3. Consultar la cima no elimina
La pila inicial es [A, B, C]. Consultar su cima devuelve C, pero el estado sigue siendo [A, B, C]. Esta distinción parece menor, aunque cambia todas las operaciones posteriores: peek observa, mientras que desapilar modifica. En la traza, una consulta conserva el mismo estado en ambas columnas.
pila = ["A", "B", "C"]
cima = pila[-1]
assert cima == "C" and pila == ["A", "B", "C"]
print(f"cima={cima}; intacta={pila}")cima=C; intacta=['A', 'B', 'C']En cualquier notación, la cima está a la derecha porque así se declaró. Si se hubiera elegido cima a la izquierda, habría que mantener esa decisión en todos los pasos; cambiarla sobre la marcha es el origen de muchas respuestas aparentemente contradictorias.
Ejercicio 4. Consulta del frente y salidas intercaladas
La cola [A, B, C] consulta primero el frente: es A y no desaparece. A continuación sale A, entra D, sale B y entra E. El estado final es [C, D, E]. Las salidas intercaladas obligan a respetar el orden de llegada incluso cuando se añaden elementos entre ellas.
from collections import deque
cola = deque(["A", "B", "C"])
frente = cola[0]
primera = cola.popleft(); cola.append("D")
segunda = cola.popleft(); cola.append("E")
assert frente == "A" and [primera, segunda] == ["A", "B"]
assert list(cola) == ["C", "D", "E"]
print(f"frente={frente}; salidas={[primera, segunda]}; queda={list(cola)}")frente=A; salidas=['A', 'B']; queda=['C', 'D', 'E']La palabra clave es «consultar»: cola[0] no es popleft(). Aun cuando ambas señalan A, una operación conserva el elemento y la otra lo extrae. Separarlas en la traza aclara inmediatamente el resultado.
Ejercicio 5. Extraer de vacío
Una pila vacía no tiene cima. Intentar extraer exige una política: comprobar esVacía() antes, documentar una precondición o gestionar un error. Aquí se captura IndexError, que es la respuesta de una lista Python vacía. No hay una salida válida que inventar ni un valor universal que pueda suponerse.
pila = []
try:
pila.pop()
except IndexError as error:
resultado = type(error).__name__
assert resultado == "IndexError"
print(f"vacío={resultado}")vacío=IndexErrorEn pseudocódigo, lo esencial sería indicar el caso vacío y no la sintaxis de la excepción. Eso vuelve el razonamiento transportable a cualquier lenguaje o implementación.
Ejercicio 6. Cola de capacidad tres: rechazo explícito
La cola tiene capacidad 3. Entran A, B, C; D intenta entrar y recibe rechazo explícito. Después sale A; un nuevo intento de D se acepta. El estado termina en [B, C, D]. No se bloquea una tarea real y no se usa maxlen: la política concreta del ejercicio es rechazar cuando está llena.
from collections import deque
cola, capacidad = deque(), 3
def encolar(x):
if len(cola) == capacidad: return False
cola.append(x); return True
admisiones = [encolar(x) for x in "ABCD"]
sale = cola.popleft(); reintento = encolar("D")
assert admisiones == [True, True, True, False] and sale == "A"
assert reintento and list(cola) == ["B", "C", "D"]
print(f"admisiones={admisiones}; sale={sale}; reintento={reintento}; queda={list(cola)}")admisiones=[True, True, True, False]; sale=A; reintento=True; queda=['B', 'C', 'D']La capacidad no altera FIFO: solo limita cuándo se puede insertar. Lo que ocurrió con D depende de la especificación de desbordamiento, no de la disciplina de salida.
Ejercicio 7. maxlen expulsa: política distinta
Con deque(maxlen=3) se carga A, B, C y se añade D con append. El resultado es [B, C, D]: A desaparece automáticamente. Conserva un orden de supervivientes, pero no implementa el rechazo del ejercicio anterior. Es un historial acotado que admite lo nuevo expulsando lo antiguo; una cola FIFO limitada con rechazo deja intactos los tres elementos y no acepta el cuarto. Esta regla se refiere a append: otras operaciones, como insert, pueden producir IndexError si la deque está llena.
from collections import deque
historial = deque(["A", "B", "C"], maxlen=3)
historial.append("D")
assert list(historial) == ["B", "C", "D"]
print(f"queda={list(historial)}")queda=['B', 'C', 'D']No mezcles este FIFO del TAD cola con FIFO como política de reemplazo de memoria. Allí FIFO decide qué página sustituir; aquí describe la extracción de una cola. La comparación útil está en FIFO y LRU para reemplazo de páginas.
Ejercicio 8. Paréntesis balanceados
Una pila permite seguir aperturas y cierres. Cada ( se apila y cada ) debe desapilar una apertura: si la pila está vacía al llegar un cierre, existe un prefijo con más cierres que aperturas. Son válidas (()) y la cadena vacía. (() acaba con una apertura pendiente. ())( falla en su tercer carácter. La misma idea puede expresarse con un contador para un único símbolo, pero la pila real enseña la extensión natural a varios delimitadores. La regla completa es: ningún prefijo puede bajar de cero y el nivel final debe ser cero.
def parentesis(cadena):
pila = []
for caracter in cadena:
if caracter == "(": pila.append(caracter)
elif caracter == ")":
if not pila: return False
pila.pop()
else: raise ValueError("solo se admiten paréntesis")
return not pila
casos = ["(())", "(()", "())(", ""]
assert [parentesis(x) for x in casos] == [True, False, False, True]
print([(x, parentesis(x)) for x in casos])[('(())', True), ('(()', False), ('())(', False), ('', True)]Con varios delimitadores, la pila guardaría el símbolo de apertura para verificar que ] cierra [ y no (. El contador es una simplificación posible solo porque todas las aperturas son del mismo tipo. La idea importante no es el truco, sino la invariante de prefijos.
Tabla para corregir una traza
| Situación | Pila de base a cima | Cola de frente a final |
|---|---|---|
| Estado inicial | [A, B] | [A, B] |
| Consultar el siguiente en salir | B, sin cambiar el estado | A, sin cambiar el estado |
Insertar C | [A, B, C] | [A, B, C] |
| Extraer después de insertar | Sale C; queda [A, B] | Sale A; queda [B, C] |
El dibujo final puede coincidir después de una inserción, aunque el comportamiento de extracción sea diferente. Por eso identificar una estructura mirando solo sus elementos no basta: hay que conocer las operaciones que ofrece y su disciplina. Dos estructuras que contienen exactamente A y B pueden dar respuestas distintas a «¿qué sale ahora?».
Otra comprobación útil consiste en contar inserciones aceptadas y extracciones realizadas. Si partes de dos elementos, aceptas tres inserciones y extraes cuatro, deben quedar uno, siempre que no exista ninguna otra operación que borre o expulse. Una consulta no cambia ese recuento. Una inserción rechazada tampoco lo aumenta. En cambio, el ejercicio con maxlen sí obliga a contabilizar el elemento descartado: no es una extracción explícita realizada por tu código, pero deja de estar en la colección.
Cuando una solución no coincide, busca la primera fila distinta, no solo el último estado. Si el primer error está en una consulta, probablemente se ha eliminado un elemento que debía quedarse. Si aparece al insertar con la capacidad completa, revisa la política de llenado. Si se produce en una extracción normal, vuelve a rotular cima o frente. Así localizas el motivo sin repetir toda la secuencia a ciegas.
Repaso y encaje de estudio
Antes de entregar una respuesta, revisa cuatro puntos: orientación declarada, diferencia entre consulta y extracción, tratamiento de vacío y política de capacidad. Después simula cada operación en orden, sin saltar directamente al resultado. Este hábito también se aprovecha en otros algoritmos; por ejemplo, los ejercicios de búsqueda binaria requieren conservar la invariante del intervalo ordenado, no confundirla con FIFO o LIFO.
El material real relacionado trata FIFO, LIFO y la diferencia entre TAD e implementación. La muestra actual verificada es de Seguridad IV.9, Almacenamiento II.2 y Repaso IV.9; no es una muestra de pilas ni colas. Si buscas el contexto completo del estudio, consulta el Pack Temario TAI 2027 o su muestra.
Preguntas frecuentes
¿Qué significa LIFO en una pila?
Significa último en entrar, primero en salir. Se inserta y se extrae por la cima; en [A, B, C] sale C.
¿Qué significa FIFO en una cola?
Significa primero en entrar, primero en salir. Con frente a la izquierda, en [A, B, C] sale A y las entradas nuevas van al final.
¿Una pila es un TAD o una implementación?
Es un TAD cuando se define por operaciones y LIFO. Un vector o una lista enlazada pueden implementarlo.
¿Por qué se usa deque para una cola Python?
Porque popleft() retira eficientemente por el frente, mientras quitar el primer elemento de una lista desplaza el resto.
¿Qué ocurre al extraer de una pila vacía?
Debe aplicarse una política explícita, como comprobar vacío o informar de error. En Python, pop() sobre una lista vacía produce IndexError.
¿deque(maxlen) rechaza al llegar a capacidad?
No con append: admite lo nuevo y descarta el extremo opuesto; otras operaciones, como insert, pueden producir IndexError.