Colas 121111215201 Phpapp02

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 filosofa FIFO ( First In - First out), el
primer elemento en entrar es el primer elemento en
salir.
Ejemplos:
Cola
de automviles 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.
0
P
(PRIMERO)
U
(LTIMO)
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: Representacin lgica de una cola simple

en un arreglo.
Cola Doble (Bicola): Estructura lineal en la que los

elementos se pueden aadir o quitar por cualquier
extremo de la cola (cola bidireccional).
Cola de Prioridades: Estructura lineal en la cual los

elementos se insertan en cualquier posicin de la cola y
se remueven solamente por el frente.
Operaciones:
1.- Insertar A
Estado de la cola:
Inicio: Cola
Vaca
A
2.- Insertar B
3.- Insertar C
4.Elemento
Remover
5.- Insertar D
6.- Remover
Elemento
Las colas pueden ser representadas en

arreglos
de
una
dimensin
(vector)
manteniendo dos variables que indiquen el
FRENTE y FINAL de los elementos de la cola.
0
Frente
2
S
3
D
4
Z
Final
Cuando la cola esta vaca 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.
Frent
e
Final
Al remover un
elemento:
Frent
e
B
Frent
e
Insertar elemento
D:
Final
C
Final
C
Insertar elemento E:
Frent
e
B
Final
C
E
Final
Insertar elemento F:
Frent
e
B
F
Insertar elemento G:
Error: Cola llena!!!!
Representacin de colas:
Usando memoria esttica: arreglos con tamao
fijo.
Final
Frent
e
B
F
D
2
E
3
Usando memoria dinmica: Listas ligadas.
Final
Frente
Definicin de un tipo abstracto: Cola

Insertar.- Almacena en la cola el elemento que se recibe
como paramtro.
Eliminar.- Saca de la cola el elemento que se encuentra al
frente.
Vaca.- 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 posicin
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.java
Insertar_Cola(1);
Insertar_Cola(2);
Insertar_Cola(3);
Insertar_Cola(4);
Insertar_Cola(5);
retirar_Cola();
retirar_Cola();
Insertar_Cola(7);
Frent
e
Final
1
5
Frent
e
3
Error no se puede
final esta en max-1
Final
4
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();
Frent
e
Final
3
Final
Frent
e
Final
Frent
e
EJERCICIO: Cola Sencilla con la

segunda solucin
Realizar el cambio para la solucin 2

ejemplo Cola_Sencilla
Colas Circulares
Es una variacin de las colas sencillas para
hacer un uso ms 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
COLA CIRCULAR
Funciona igual que la cola simple, pero optimiza

el uso de memoria (al reutilizar localidades
disponibles).
1) Inicialmente vaca
1
COLA
2
3
4
P=0
U=0
COLAS
2) Se inserta A,B,C,D,E
P=1
U=5
COLA
2
3
4
3) Eliminar A
P=2
U=5
4) Insertar F
P=2
P=2
U=5
U=1
U
COLAS
2
1
P
B
INSERTAR F
C
E
5
4
U
SI U+1 = P
COLA CIRCULAR
LLENA
2
1
B
3
F
C
E
5
D
4
COLAS
OTRO EJEMPLO: N= 5
1) Se inserta A,B,C,D,E
P=1
U=5
COLA
2
3
4
2) Se inserta F
NO SE PUEDE INSERTAR F PORQUE LA
COLA CIRCULAR LLENA, U=N y P=1.
SRR
COLAS
Cola Circular
Es una representacin
lgica 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
posicin del arreglo.
Frent
e
Cola
inicial
Final
Frent Final
e
Remover
C
Frent
e
Insertar E
Final
C
E
Final
Insertar F
F
E
Frent
e
C
Ejemplo de cola circular

class ColaCirc max=3
InsColaCirc(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 mtodos:
ColaCirc_llena()
ColaCirc_vacia()
InsColaCirc(Object dato)
RetColaCirc()
Hacer un programa, que contenga un men para llamar

los mtodos de insercin y retiro de los elementos de la
cola circular.
BICOLA
Es una variacin del tipo de datos cola.
Una bicola:
es un conjunto de elementos en el cual se
pueden aadir o quitar elementos de cualquier
extremo de la misma.
Los dos extremos de una bicola los llamaremos
izquierdo y derecho
Operaciones Bsicas de una bicola

CrearB.- inicializa una bicola sin elementos
EsVaca.- Regresa un valor booleano indicando si la bicola tiene o no
elementos .
InsertarIZQ.- Aade un elemento por el extremo izquierdo.
InsertarDER.- Aade 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 esttica
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 eliminacin 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
luz
agua
ri
Al aadir el elemento sql por el frente:

Frente: 1
Final: 4
sql
luz
agua
ri
Puede eleiminar por el final:

Frente: 1
Final: 3
sql
luz
agua
Implementar la clase bicola
Problema:
El estacionamiento de las avionetas de un aeropuerto es en lnea,

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 dems se mueven hacia
delante, de tal forma que los espacios libres del estacionamiento
estn en la parte izquierda.
El programa para emular este estacionamiento tiene como entrada

un carcter que indica una accin sobre la avioneta, y la matricula
de la avioneta.
La accin 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).
Anlisis 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 lnea de espera para entrada de una avioneta (estacionamiento
lleno) se representa por una bicola a la que se aaden 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 aadirse en el
extremo salida del estacionamiento y seguir en el mismo orden.
La restriccin de salida se refleja en que no es valida la operacin
retirar por el extremo de salida
Colas en Java
Java contiene la definicin de interfaces y
clases para el manejo de colas.
Las colas son una coleccin de elementos
diseadas 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..
boo offer(Eo)
lean
Inserts the specified element into this queue, if possible.
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.
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 Summary
PriorityQueue()
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(intinitialCapacity)
Creates a PriorityQueue with the specified initial capacity that orders its elements according to
their natural ordering (using Comparable).
PriorityQueue(intinitialCapacity, 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)

PriorityQueue(SortedSet<? extends E>c)
Method Summary
boolean
void
Comparat
or<?
super E>
Iterator<
E>
boolean
add(Eo)
Adds the specified element to this queue.
clear()
Removes all elements from the priority queue.
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()
Returns an iterator over the elements in this queue.
offer(Eo)
Inserts the specified element into this priority queue.
peek()
Retrieves, but does not remove, the head of this queue, returning null if this queue is empty.
poll()
Retrieves and removes the head of this queue, or null if this queue is empty.
boolean
int
remove(Objecto)
Removes a single instance of the specified element from this queue, if it is present.
size()
Returns the number of elements in this collection.

Colas 121111215201 Phpapp02

Cargado por

Copyright:

Formatos disponibles

Colas 121111215201 Phpapp02

Cargado por

Información del documento

Descripción original:

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Colas 121111215201 Phpapp02

Cargado por

Copyright:

Formatos disponibles

Colas

de automviles esperando servicio en una gasolinera

Es una lista en la que las supresiones se realizan

PEPS = Primero Entrar - Primero Salir

Las colas abundan en la vida cotidiana:

Cola simple: Estructura lineal donde los elementos

Cola circular: Representacin lgica de una cola simple

Cola Doble (Bicola): Estructura lineal en la que los

Cola de Prioridades: Estructura lineal en la cual los

Las colas pueden ser representadas en

Cuando la cola esta vaca las variables frente y

Cuando la cola esta llena ( frente = 0 y final = n-1)

Cuando se remueven elementos el frente puede

Cuando no hay espacios libres al final del arreglo

Ejemplo: Suponer que usamos un arreglo de 5

Usando memoria dinmica: Listas ligadas.

Definicin de un tipo abstracto: Cola

Interface de un TDA llamado Cola:

Implementacion de la clase Cola

Ver ejemplo Cola.java

Cola Sencilla con la primera

EJERCICIO: Cola Sencilla con la

Realizar el cambio para la solucin 2

Funciona igual que la cola simple, pero optimiza

Ejemplo de cola circular

Ejercicio para clase

Modificar el programa anterior ColaCirc modificando y

Hacer un programa, que contenga un men para llamar

Es una variacin del tipo de datos cola.

Operaciones Bsicas de una bicola

Restricciones en las bicolas

Restricciones de entrada: Es aquella que solo

Restricciones de salida: Es aquella que

Estructura tipo bicola

Al aadir el elemento sql por el frente:

Puede eleiminar por el final:

Implementar la clase bicola

El estacionamiento de las avionetas de un aeropuerto es en lnea,

El programa para emular este estacionamiento tiene como entrada

Anlisis del programa

El estacionamiento va a estar representado por una bicola de salida

Cola de Prioridad en Java

All Implemented Interfaces:

Creates a PriorityQueue containing the elements in the specified collection.

Creates a PriorityQueue containing the elements in the specified collection.

Creates a PriorityQueue containing the elements in the specified collection.

También podría gustarte