PILAS Y COLAS

Pila

Concepto  

Una 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
  1. Los ordena de menor a mayor (sale primero el menor elemento)
  2. Para los que son iguales, el orden es arbitrario
  3. 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/