Colas
COLAS
Definicion. Es una lista lineal de elementos en la que las operaciones de insertar y eliminar se realizan en diferentes extremos de la cola.
Trabajan con filosofía FIFO ( First In - First out), el primer elemento en entrar es el primer elemento en salir.
Ejemplos:
•Cola de automóviles esperando servicio en una gasolinera•Cola de clientes en una ventanilla del banco para pagar un servicio•Cola de programas en espera de ser ejecutados por una computadora.
Es una lista en la que las supresiones se realizan solamente al principio de la lista y las inserciones al final de la misma.
P U
0 1 2 3 4 5 6 7 . . . N
(ÚLTIMO) (PRIMERO)
PEPS = Primero Entrar - Primero Salir
Las colas abundan en la vida cotidiana:
TIPOS DE COLAS:
• Cola simple: Estructura lineal donde los elementos salen en el mismo orden en que llegan.
• Cola circular: Representación lógica de una cola simple en un arreglo.
• Cola Doble (Bicola): Estructura lineal en la que los elementos se pueden añadir o quitar por cualquier extremo de la cola (cola bidireccional).
• Cola de Prioridades: Estructura lineal en la cual los elementos se insertan en cualquier posición de la cola y se remueven solamente por el frente.
Operaciones:
A
BA
A B C
B C
B C D
C D
1.- Insertar A1.- Insertar A
2.- Insertar B2.- Insertar B
Estado de la cola:
3.- Insertar C3.- Insertar C
4.- Remover 4.- Remover ElementoElemento
5.- Insertar D5.- Insertar D
6.- Remover Elemento
Inicio: Cola Vacía
Las colas pueden ser representadas en arreglos de una dimensión (vector) manteniendo dos variables que indiquen el FRENTE y FINAL de los elementos de la cola.
A F S D Z
Frente Final
0 1 2 3 4 5
• Cuando la cola esta vacía las variables frente y final son nulos y no es posible remover elementos.
• Cuando la cola esta llena ( frente = 0 y final = n-1) no es posible insertar elementos nuevos a la cola.
• Cuando se remueven elementos el frente puede incrementarse para apuntar al siguiente elemento de la cola.
• Cuando no hay espacios libres al final del arreglo los elementos pueden ser desplazados para desocupar posiciones del arreglo o se puede manejar una estructura circular.
Ejemplo: Suponer que usamos un arreglo de 5 posiciones.
A B CFrente
Final
Al remover un elemento:
B C
Frente
Final
Insertar elemento D:
B C D
Frente
Final
Insertar elemento E:
B C D E
Frente
Final
Insertar elemento F:
B C D E F
Frente
Final
Insertar elemento G:
Error: Cola llena!!!!
Representación de colas:• Usando memoria estática: arreglos con tamaño fijo.
• Usando memoria dinámica: Listas ligadas.
B C D E F
Frente
Final
0 1 2 3 4
B C D
Frente
Final
E F
Definición de un tipo abstracto: Cola
Insertar.- Almacena en la cola el elemento que se recibe como paramétro.
Eliminar.- Saca de la cola el elemento que se encuentra al frente.
Vacía.- Regresa un valor booleano indicando si la cola tiene o no elementos (true – si la cola esta vacia, false – si la cola tiene al menos un elemento).
Llena.- Regresa un valor booleano indicando si la cola tiene espacio disponible para insertar nuevos elementos ( true – si esta llena y false si existen espacios disponibles).
Interface de un TDA llamado Cola:
interface ICola{
public boolean llena();
public boolean vacia();
public void insertar (Object elem);
public Object eliminar();
}
Cola simple
Es una lista lineal de elementos en la que las operaciones de insertar y eliminar se realizan en diferentes extremos de la cola. Para lo cual hace uso de dos indices frente y final.
Este tipo de cola presenta desaprovechamiento de memoria al momento que se retiran elementos de la cola ya que esa localidad queda libre; para evitar este desaprovechamiento de memoria tenemos dos soluciones:
1.- Mover todos los elementos de la cola una posición cada vez que se quiere retirar un elemento de la cola
2.- Cuando final =max-1 y frente >0 mover todos los elementos.
Implementacion de la clase Cola Sencilla Ver ejemplo Cola.javaInsertar_Cola(1);
Insertar_Cola(2);
Insertar_Cola(3);
Insertar_Cola(4);
Insertar_Cola(5);
retirar_Cola();
retirar_Cola();
Insertar_Cola(7);
1 2 3 4 5
Frente
Final
3 4 5
Frente
Final
Error no se puede final esta en max-1
Cola Sencilla con la primera solucion Ver ejemplo
Cola_Sencilla1
Insertar_Cola(1);Insertar_Cola(2);Insertar_Cola(3);Insertar_Cola(4);retirar_Cola();retirar_Cola();
1 2 3 4Frente
Final
2 3 4Frente
Final
3 4Frente
Final
EJERCICIO: Cola Sencilla con la segunda solución
Realizar el cambio para la solución 2
ejemplo Cola_Sencilla
Colas Circulares
Es una variación de las colas sencillas para hacer un uso más eficiente de la memoria disponible, se trata a la estructura de cola de forma circular. Es decir el elemento anterior al primero es el último
COLAS
Funciona igual que la cola simple, pero optimiza el uso de memoria (al reutilizar localidades disponibles).
COLA CIRCULAR
1) Inicialmente vacía
P=0
U=0
1 2 3 4 5COLA
COLAS
2) Se inserta A,B,C,D,EP=1
U=5
1 2 3 4 5COLA
B CA D
P U
E
3) Eliminar AP=2
U=5
1 2 3 4 5
B CA D
P U
E
P=2
U=5
4) Insertar F 1 2 3 4 5
B C D
P U
EFP=2
U=1
B
C
DE
P
U
COLAS
INSERTAR F
B
C
DE
P
FU
1
2
3
45
SI U+1 = P
COLA CIRCULAR LLENA
1
2
3
45
1) Se inserta A,B,C,D,EP=1
U=5
1 2 3 4 5COLA
B CA D
P U
E
SRR COLAS
OTRO EJEMPLO: N= 5
2) Se inserta F
NO SE PUEDE INSERTAR “F” PORQUE LA
COLA CIRCULAR LLENA, U=N y P=1.
Cola Circular
Es una representación lógica de la cola en un arreglo.
El frente y final son movibles.
Cuando el frente o final llegan al extremo se regresan a la primera posición del arreglo.
C D E
Frente
Final
F C D E
Frente
Final
C D
Frente
Final
B C D
Frente
Final
Remover
Insertar E
Insertar F
Cola inicial
Ejemplo de cola circularclass ColaCirc max=3InsColaCirc(A);InsColaCirc(B);InsColaCirc(C);RetColaCirc();RetColaCirc();InsColaCirc(D);InsColaCirc(F);InsColaCirc(E); DESBORDAMIENTO
Ejercicio para clase Modificar el programa anterior ColaCirc modificando y
agregando los métodos:
ColaCirc_llena()ColaCirc_vacia()InsColaCirc(Object dato)RetColaCirc()
Hacer un programa, que contenga un menú para llamar los métodos de inserción y retiro de los elementos de la cola circular.
BICOLA
Es una variación del tipo de datos cola.
Una bicola: es un conjunto de elementos en el cual se
pueden añadir o quitar elementos de cualquier extremo de la misma.
Los dos extremos de una bicola los llamaremos izquierdo y derecho
Operaciones Básicas de una bicola
CrearB.- inicializa una bicola sin elementos
EsVacía.- Regresa un valor booleano indicando si la bicola tiene o no elementos .
InsertarIZQ.- Añade un elemento por el extremo izquierdo.
InsertarDER.- Añade un elemento por el extremo derecho.
EliminarIZQ.- Devuelve el elemento Izquierdo y lo retira de la bicola.
EliminarDER.- Devuelve el elemento Derecho y lo retira de la bicola.
Representacion estática
Se mantienen los elementos de la bicola en un arreglo circular.
Se utilizan dos variables indice Izquierdo y Derecho.
Restricciones en las bicolas
Restricciones de entrada: Es aquella que solo permite inserciones por uno de los extremos, pero permite la eliminación por los dos extremos.
Restricciones de salida: Es aquella que permite inserciones por los dos extremos, pero solo permite retirar elementos por un extremo.
Estructura tipo bicola
Frente: 2
Final: 4
0 1 2 3 4 5 6 7 8 9
luz agua rió
Al añadir el elemento sql por el frente:
0 1 2 3 4 5 6 7 8 9
luz agua riósql
Puede eleiminar por el final:
0 1 2 3 4 5 6 7 8 9
luz aguasql
Frente: 1
Final: 4
Frente: 1
Final: 3
Implementar la clase bicolaProblema: El estacionamiento de las avionetas de un aeropuerto es en línea,
con una capacidad de 12 avionetas. Las avionetas llegan por el extremo izquierdo y salen por el extremo
derecho. Cuando llega un piloto a recoger su avioneta, si esta no esta
justamente en el extremo de salida (derecho), todas las avionetas a su derecha han de ser retiradas, sacar la suya y las avionetas retiradas son colocadas de nuevo en el mismo orden en que estaban.
La salida de una avioneta supone que las demás se mueven hacia delante, de tal forma que los espacios libres del estacionamiento están en la parte izquierda.
El programa para emular este estacionamiento tiene como entrada un carácter que indica una acción sobre la avioneta, y la matricula de la avioneta.
La acción puede ser llegada (E) o salida (S) de avioneta. En la llegada puede ocurrir que el estacionamiento este lleno, si es
así la avioneta espera hasta que se quede una placa libre, o hasta que se dé orden de retirada (salida).
Análisis del programa El estacionamiento va a estar representado por una bicola de salida
restringida ¿Por qué? La salida siempre se hace por el mismo extremo, sin embargo la entrada se puede hacer por los dos extremos, y así contemplar la llegada de una avioneta nueva ,y que tenga que entrar una avioneta que ha sido movida para que salga una intermedia.
La línea de espera para entrada de una avioneta (estacionamiento lleno) se representa por una bicola a la que se añaden avionetas por un extremo, salen para entrar en el estacionamiento por el otro extremo.
Las avionetas que se mueven para poder retirar del estacionamiento una intermedia se almacenan en una lista lifo (pila); asi la última en entrar será la primera en añadirse en el extremo salida del estacionamiento y seguirá en el mismo orden.
La restricción de salida se refleja en que no es valida la operación retirar por el extremo de salida
Colas en Java
Java contiene la definición de interfaces y clases para el manejo de colas.
Las colas son una colección de elementos diseñadas para almacenar elementos que esperan ser procesados.
Java contiene una interface parametrizada Queue<E> y varias clases que que la implementan, entre ellas PriorityQueue<E>
Colas en Java
public interface Queue<E> extends Collection<E> {
E element(); boolean offer(E o); E peek(); E poll(); E remove(); }
Method Summary
E element() Retrieves, but does not remove, the head of this queue, it throws an exception if this queue is empty..
boolean
offer(E o) Inserts the specified element into this queue, if possible.
Epeek() Retrieves, but does not remove, the head of this queue, returning null if this queue is empty.
Epoll() Retrieves and removes the head of this queue, or null if this queue is empty.
E remove() Retrieves and removes the head of this queue.
Cola de Prioridad en Java
java.util Class PriorityQueue<E>
java.lang.Object java.util.AbstractCollection<E> java.util.AbstractQueue<E> java.util.PriorityQueue<E>
Type Parameters: E - the type of elements held in this collection
All Implemented Interfaces: Serializable, Iterable<E>, Collection<E>, Queue<E>
Constructor SummaryPriorityQueue() Creates a PriorityQueue with the default initial capacity (11) that orders its elements according to their natural ordering (using Comparable).
PriorityQueue(Collection<? extends E> c) Creates a PriorityQueue containing the elements in the specified collection.
PriorityQueue(int initialCapacity) Creates a PriorityQueue with the specified initial capacity that orders its elements according to their natural ordering (using Comparable).
PriorityQueue(int initialCapacity, Comparator<? super E> comparator) Creates a PriorityQueue with the specified initial capacity that orders its elements according to the specified comparator.
PriorityQueue(PriorityQueue<? extends E> c) Creates a PriorityQueue containing the elements in the specified collection.
PriorityQueue(SortedSet<? extends E> c) Creates a PriorityQueue containing the elements in the specified collection.
Method Summary boolean add(E o)
Adds the specified element to this queue.
void clear() Removes all elements from the priority queue.
Comparator<?
super E>
comparator() Returns the comparator used to order this collection, or null if this collection is sorted according to its elements natural ordering (using Comparable).
Iterator<E>
iterator() Returns an iterator over the elements in this queue.
boolean offer(E o) Inserts the specified element into this priority queue.
E peek() Retrieves, but does not remove, the head of this queue, returning null if this queue is empty.
E poll() Retrieves and removes the head of this queue, or null if this queue is empty.
boolean remove(Object o) Removes a single instance of the specified element from this queue, if it is present.
int size() Returns the number of elements in this collection.
Top Related