Pilas y colas
Mapa conceptual
- Estructuras de Datos
- Lineales
- Arrays
- Listas enlazadas
- Pilas y Colas
- No lineales
- Arboles BST
- Heaps
- Grafos
- Hash
- Funcion hash
- Colisiones
- Rehashing
- Algoritmos
- Ordenamiento
- Busqueda binaria
- BFS DFS
- Optimizacion
- Big-O
- Dinamica
- Voracidad
- Lineales
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.
| 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 |
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
Toca una tarjeta para ver la respuesta.
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.
Tu texto se guarda sólo en este dispositivo.
Reflexiona: ¿como se relaciona este tema con los demas temas del curso? ¿Que ejemplo practico podrias dar?
Tu texto se guarda sólo en este dispositivo.
VisuAlgoVisualizaciones animadas de estructuras de datos y algoritmos.
Comentarios
Inicia sesión para comentar.
Todavía no hay comentarios. Sé la primera persona en opinar.