Pilas y colas

Diagrama de estructuras de datos: arbol binario, lista enlazada y tabla hash. — Estructuras de datos fundamentales y analisis de complejidad algoritmica.

Mapa conceptual

LIFO y FIFO Una pila (stack) es una pila de platos: el último que llega es el primero que se retira (LIFO). Una cola (queue) es una fila de gente: el primero que llega es el primero que es atendido (FIFO). Toda su potencia está en esa restricción de orden.

Pila (stack): LIFO

Operaciones push (añadir arriba) y pop (quitar arriba), ambas O(1). La pila es la estructura del RETROCESO y del ANIDAMIENTO: deshacer (Ctrl+Z), la pila de llamadas de un lenguaje, cerrar paréntesis y etiquetas, y los algoritmos de profundidad (DFS).

Cola (queue): FIFO

Operaciones enqueue (añadir al final) y dequeue (quitar del frente), O(1). La cola es la estructura del ORDEN DE LLEGADA y la ESPERA justa: buffer de impresión, colas de peticiones, planificación de tareas y los recorridos en anchura (BFS) de un grafo.

La cola de prioridad se verá a fondo en la ola de heaps; aquí basta saber que rompe el FIFO: no vale «el primero que llegó» sino «el de mayor urgencia».
Estructura	Principio	Añadir	Quitar	Usos canónicos
Pila	LIFO	arriba	arriba	deshacer, recursión, DFS, balancear símbolos
Cola	FIFO	final	frente	buffer,调度, BFS, atención por turnos
Cola de prioridad	por peso	según prioridad	el de mayor prioridad	planificación, Dijkstra, top-k

La pregunta del orden Cómo decidir en un vistazo: si lo más reciente debe resolverse antes, es PILA (retroceso, anidamiento). Si lo más antiguo debe resolverse antes, es COLA (orden de llegada). Si el orden lo decide un peso, es COLA DE PRIORIDAD.

El mecanismo que permite «deshacer» una secuencia de ediciones (la última acción se deshace primero) es…

Para comprobar si unos paréntesis están balanceados, una cola es la estructura natural.

Une cada situación con la estructura que la resuelve mejor.

Errores frecuentes

Confundir orden: en FIFO sale el ANCIANO (el más antiguo), en LIFO sale el NOVATO (el más reciente). Memorízalo con «cola de banco» vs «pila de platos».
Implementar una pila con borrado del final de un arreglo creyendo que es gratis: con un arreglo dinámico sí es O(1) amortizado, pero borrar del FRENTE de un arreglo es O(n).
Usar una pila donde hace falta orden de llegada: perderías la equidad FIFO.

Ejemplo resuelto: balanceo de símbolos

Recorre « [ ] ( ) » carácter a carácter.
Si es apertura ([(, haz push.
Si es cierre, haz pop y comprueba que la apertura que saca es la pareja correcta.
«» push, «[» push, «]» pop da «[» ✓, «(» push, «)» pop da «(» ✓, «» pop da «» ✓.
Pila al final vacía → balanceado. Si un cierre no casa o queda algo al final → no balanceado.

En tus propios pipelines, las colas aparecen en todas partes: un consumidor de mensajes, un buffer de logs, una lista de tareas que lanza un scheduler. Y las pilas están en cada for anidado que deja el intérprete, en cada backtrack y en cada DFS. Nombrar la estructura que ya estás usando te debe ayudar a razonar su costo.

Las dos restricciones de orden

pila

LIFO: último entra, primero sale

cola

FIFO: primero entra, primero sale

push/pop

operaciones de pila

enqueue/dequeue

operaciones de cola

deshacer

pila

turnos

cola

DFS

pila

BFS

cola

Pilas y colas (repaso formal)
Definiciones, operaciones y aplicaciones con ejercicios.

Una imprenta recibe trabajos por red y debe imprimirlos en el orden en que llegaron. Un editor de texto permite deshacer. Asigna a cada uno pila o cola y justifica. Luego propón una tercera situación real que corresponda a cola de prioridad.

Reflexiona: ¿como se relaciona este tema con los demas temas del curso? ¿Que ejemplo practico podrias dar?

VisuAlgo
Visualizaciones animadas de estructuras de datos y algoritmos.