COLAS
TDA Cola Cola: Colección lineal de objetos actualizada en sus extremos llamados
frente y rabo siguiendo una política FIFO (first-in firstout, el primero en entrar es el
primero en salir) (También se llama FCFS = First-Come First-Served).
Operaciones:
o enqueue(e): Inserta el elemento e en el rabo de la cola
o dequeue(): Elimina el elemento del frente de la cola y lo retorna. Si la cola
está vacía se produce un error.
o front(): Retorna el elemento del frente de la cola. Si la cola está vacía se
produce un error.
o isEmpty(): Retorna verdadero si la cola no tiene elementos y falso en caso
contrario.
o size(): Retorna la cantidad de elementos de la cola.
Implementación de Cola
Definición de una interfaz Cola:
o Se abstrae de la ED con la que se implementará
o Se documenta el significado de cada método en lenguaje natural
o Se usa un parámetro formal de tipo representando el tipo de los elementos
de la cola
o Se definen excepciones para las condiciones de error
Implementación de cola con un arreglo circular
o q es un arreglo de N componentes y mantiene los elementos de la cola.
o El tamaño máximo de q es N-1 (lo que permite diferenciar la cola vacía de
la cola llena).
o f es la posición en q del próximo elemento a eliminar en un dequeue.
o r es la posición en la cual se va a insertar el siguiente elemento con un
enqueue.
o Implementaremos operaciones en O(1)
Implementación de cola con un arreglo circular
Cola: Implementación con nodos enlazados
Cola con Memoria Dinámica Basada en Nodos
Esta cola funciona de la misma forma que la anterior con respecto al funcionamiento pero
su implementación es diferente, ya que está basada en memoria dinámica y nodos.
Veamos la clase Nodo y la implementación de la Cola para luego explicar ambas clases.
La clase Nodo
Nuestra Cola con Memoria Dinámica
public boolean hasNext() {
boolean next = false;
import java.util.Optional;
if (inicio != null) {
public class ColaMemoriaDinamica<V> { next = true;
}
private Nodo<V> inicio;
private Nodo<V> fin; return next;
private int numElementos; }
public ColaMemoriaDinamica() { public int size() {
this.inicio = null; return this.numElementos;
this.fin = null; }
this.numElementos = 0;
} }
public void push(V item) {
Nodo<V> nodo = new Nodo<>(item,
null);
if (inicio == null) {
inicio = nodo;
fin = nodo;
}else {
fin.setNext(nodo);
fin = nodo;
}
}
public Optional<V> pop(){
Optional<V> item =
Optional.empty();
Con respecto a la clase Nodo esta contiene 3 atributos, uno de ellos, el de
prioridad de momento lo vamos a ignorar, ya que lo utilizaremos después para
nuestra cola con prioridad. Los atributos que nos interesan aquí son:
o private V item: Aquí almacenaremos nuestro elemento. Fijaos que
utilizamos Genéricos «V».
o private Nodo next: Se tratará de un puntero hacia el siguiente nodo.
Veamos los atributos de la clase cola:
private Nodo<V> inicio;
private Nodo<V> fin;
private int numElementos;
BIBLIOGRAFÍAS
https://cs.uns.edu.ar/~mlg/ed/downloads/Teorias/uns-ed-
2019-clase-04-Pilas%20y%20Colas.pdf
https://somoshackersdelaprogramacion.es/la-estructura-de-
datos-cola-en-java
