Pila
ConceptoUna pila, también llamada stack, es una colección ordenada de elementos a los cuales sólo se puede acceder por un único lugar o extremo de la pila. Los elementos se añaden o se quitan (borran) de la pila sólo por su parte superior (cima). Este es el caso de una pila de platos, una pila de libros, etc.
Las pilas se conocen también como estructuras LIFO (Last-in, first-out, último en entrar primero en salir).
Ejemplo:
- Una pila de libros, colocando un libro encima de otro
Para tener la idea más clara podemos ver la siguiente gráfica:
Por eso el último en entrar es el primero en salir.
Mapa conceptual
Tratamiento de expresiones
Ejemplo de códigos
Código de ejemplo de Pila:
Transformación de expresiones infija a postfija
Transformación de expresiones infija a prefija
Cola
Concepto
Una cola es una estructura de datos que almacena elementos en una lista y permite acceder a los datos por uno de los dos extremos de la lista. Un elemento se inserta en la cola (parte final) de la lista y se suprime o elimina por el frente (parte inicial) de la lista. Las aplicaciones utilizan una cola para almacenar elementos en su orden de aparición o concurrencia.Los elementos se eliminan (se quitan) de la cola en el mismo orden en que se almacenan y, por consiguiente, una cola es una estructura de tipo FIFO (first-in, firs-out, primero en entrar-primero en salir o bien primero en llegar-primero en ser servido).
Ejemplos:
- Atención a clientes en un almacén
- Tareas enviadas a una impresora
Para aclarar, una cola es una estructura de datos cuyos elementos mantienen un cierto orden, de tal modo que sólo se pueden añadir elementos por un extremo, final de la cola, y eliminar o extraer por el otro extremo, llamado frente.
Operaciones:
- Insertar: agrega un elemento por el final de la cola.
- Quitar: elimina un elemento por el inicio de la cola.
Por eso el primero en entrar es el primero en salir.
Mapa conceptual
Colas con prioridad
Las colas con prioridad tienen las siguientes características:
- Clase PriorityQueue que implementa la interfaz Queue
- Se comporta como una cola de prioridad
- Usa compareTo, o un comparador, para ordenar los elementos por su prioridad
- Los ordena de menor a mayor (sale primero el menor elemento)
- Para los que son iguales, el orden es arbitrario
- Constructores de las colas de prioridad
Código de ejemplo de Cola
Código de ejemplo de Cola con prioridades
Código de ejemplo para Clase Urgencia
Código de ejemplo para Clase ColaEsperaConUrgencia
Fuentes:
https://www.youtube.com/watch?v=gTt4rG2Cja4
http://www.redeszone.net/2012/04/02/curso-de-java-colas-de-prioridad/