Estructura de Datos I
TDA COLA
Ing. Mario Milton López Winnipeg
Capitulo 4 TDA Cola
4 Colas
4.1 Descripción del TDA Cola.
4.2 Especificación del TDA Cola.
4.3 Ejemplos de uso.
4.4 Implementaciones del TDA Cola.
4.4.1 Implementación basada en el TDA Lista.
4.4.2 Implementación con vectores.
4.4.3 Implementación con apuntadores.
4.4.4 Comparación de las implementaciones.
4.5 Modalidades de colas.
4.5.1 Dicolas.
4.5.2 Colas de Prioridad
4.1 Descripción del TDA Cola
Una cola es un caso particular de lista en el cual los
elementos se insertan en un extremo (el posterior o final)
y se suprimen en el otro (el anterior o frente).
Las colas se conocen también como listas FIFO ( first-
in first-out) o listas ``primero en entrar, primero en
salir''.
Algunas de las operaciones vistas para listas pierden
sentido en el TDA Cola y se definen nuevas operaciones
4.1 Descripción del TDA Cola
Podemos definir las siguientes operaciones:
CREA. Crea una cola vacía.
VACIA. Devuelve un valor cierto si la cola está vacía,
y falso en caso contrario.
PRIMERO. Devuelve el primer elemento de una cola.
PONER. Añade un elemento por el extremo final de
una cola.
SACAR. Suprime el primer elemento de una cola y
retorna dicho valor.
4.2 Especificación del TDA Cola
Especificación Informal
Cola = TDA con operaciones crea, vacia, primero,
poner, sacar.
DESCRIPCIÓN:
Los valores del TDA Cola son colas de elementos del
tipo Elemento. Las colas son mutables: poner y sacar
añaden y eliminan elementos en la cola
respectivamente.
OPERACIONES:
crea() devuelve (C:Cola)
efecto: Devuelve la cola vacía C.
4.2 Especificación del TDA Cola
vacia(C:Cola) devuelve (booleano)
efecto: Devuelve cierto si C es la cola vacía, y falso en
caso contrario.
primero(C:Cola) devuelve (E:Elemento)
requerimientos: La cola C es no vacía.
efecto: Devuelve en E el primer elemento de la cola C.
poner(C:Cola; E:Elemento)
modifica: C.
efecto: Añade el elemento E por el extremo final de la cola C
sacar(C:Cola, ES E: Elemento)
requerimientos: La cola C es no vacía.
modifica: C.
efecto: Suprime el primer elemento de la cola C y lo retorna.
4.2 Especificación del TDA Cola
Especificación Formal
Tipo: Cola (Elemento)
Sintaxis:
crea Cola
vacia(Cola) booleano
primero(Cola) Elemento
poner(Cola,Elemento) Cola
sacar(Cola, Elemento) Cola
4.2 Especificación del TDA Cola
La interface del TDA Cola de acuerdo a esta
especificación puede definirse de la siguiente
forma:
publico interface Cola
{
publico boolean vacia();
publico Elemento Primero()
publico poner(Objecto elemento);
publico sacar(Objeto elemento);
} // fin interface Cola
4.3 Ejemplo de uso
publico concatenar(Cola cola1, Cola cola2 ES Cola Cola3)
inicio
mientras No ([Link]()= Verdadero)
inicio
[Link](E ) [Link](E)
fin
mientras no([Link]())
inicio
[Link](E); [Link](E); [Link](E)
fin
mientras No ([Link]()= Verdadero)
inicio
[Link](E ) [Link](E)
fin
mientras no([Link]())
inicio
[Link](E); [Link](E); [Link](E)
fin
fin
4.4 Implementaciones del TDA Cola
En esta sección mostraremos tres implementaciones
para el TDA Cola:
Implementación basada en el TDA Lista
Implementación con vectores circulares
Implementación con apuntadores
4.4.1 Implementación basada en el TDA Lista
Definición básica de la clase Cola con representación contigua
Clase Cola
Atributos
L : Lista
Metodos
Crear()
Vacia()
Poner(E : Elemento)
Sacar( ES E: Elemento)
primero()
Fin
Constructor [Link]
inicio
// Crear Objeto L
fin
[Link]( E: Elemento) [Link]( ES E: Elemento)
inicio Inicio
[Link]([Link](),E); [Link]([Link](),E)
[Link]([Link])
Fin Fin
4.4.2 Implementacion basada en vectores
(Vector de recorrido 1..MAX V.1)
Definición básica de la clase Cola con implementacion usando vectores
Clase Cola
Atributos
V : Arreglo(MAX)
ini,fin: Entero 1 2 3 4 5 6 7 max
Metodos
Crear() e1 e2 e3
Vacia()
Poner(E : Elemento)
Sacar( ES E: Elemento)
primero() ini fin
Fin
Constructor [Link]
inicio
fin=0
ini=1
fin
[Link]( E: Elemento) [Link]( ES E: Elemento)
inicio Inicio
si fin<MAX entoces Si no Vacia() entoces
fin = fin +1 E= V[ini]
v[fin]=E ini=ini +1
Fin Fin
4.4.2 Implementacion basada en vectores
(Vector de recorrido 1..MAX V.2)
Definición básica de la clase Cola con implementacion usando vectores
Clase Cola
Atributos
V : Arreglo(MAX)
ini,fin: Entero
1 2 3 4 5 6 7 max
Metodos
Crear()
e1 e2 e3
Vacia()
Poner(E : Elemento) Desplazar para sacar
Sacar( ES E: Elemento)
primero() ini fin
Fin
Constructor [Link]
inicio
fin=0
ini=1
fin
[Link]( E: Elemento) [Link]( ES E: Elemento)
inicio Inicio
si fin<MAX entoces Si no Vacia() entoces
fin = fin +1 E= V[1]
v[fin]=E Desplazar(1)
fin=fin - 1
Fin Fin
4.4.2 Implementacion basada en vectores
(Vector de recorrido 1..MAX,1..Max,1..Max.. V.3)
Definición básica de la clase Cola con implementacion usando vectores
Clase Cola
Atributos
V : Arreglo(MAX) ...
ini,fin: Entero
Metodos
Crear()
Vacia()
a1 an
Poner(E : Elemento)
Sacar( ES E: Elemento) ini
primero()
a2 an fin
Fin ... -1
Constructor [Link]
inicio
fin=0
ini=1
fin
[Link]( E: Elemento) [Link]( ES E: Elemento)
inicio Inicio
si Siguiente(Siguiente(Fin))=ini entoces Si no Vacia() entoces
fin = siguiente(fin) E= V[ini]
v[fin]=E ini=siguiente(ini)
Fin Fin
4.4.2 Implementacion basada en vectores
(Vector de recorrido 1..MAX,1..Max,1..Max.. V.3)
La funcion Siguiente( Dir )
Esta funcion tiene por objetivo recibir una direccion y
retornar la siguiente o la direccion que se encuentra a
continuacion.
Implementacion
Siguiente ( dir )
Inicio
si dir = MAX entonces retornar 1
caso contrario retornar dir+1
Fin
Si no se desea implementar la funcion siguiente se podria
reemplazar esta por
dir = (dir modulo MAX) +1
4.4.3 Implementación con apuntadores
Definición básica de la clase Cola con representación
enlazada con simple enlace:
Tipo de dato
Nodo
elemento TipoElemento
sig Puntero a Nodo
// fin definicion
Direccion Puntero a espacio de memoria de tipo Nodo
Clase Cola
Atributos
ini Puntero de tipo Direccion
fin Puntero de tipo Direccion
Metodos
……………..
4.4.3 Implementación con apuntadores
publico [Link]()
inicio publico [Link]()
ini = nulo ; fin = nulo inicio
fin retornar (ini = nulo)
fin
publico [Link]( E : Elemento)
inicio
aux = // Pedir Espacio de memoria para Nodo
si aux <> nulo entoces
ponerdato(aux,1E);
Ponerdato(aux,2,nulo)
si vacia() entoces ini=aux
fin=aux
caso contrario
ponerdato(fin,2,aux)
fin = Aux
caso contrario // Error
fin
4.4.4 Comparación de las Implementaciones
La elección de una implementación u otra dependerá de
los requerimientos de la aplicación en la que se use.
Es posible obtener representaciones para colas que
permiten operaciones eficientes con tiempos de ejecución
constantes.
Queda demostrado con la reprecentacion con vectores
que las formas de implementacion deben ser totalmente
agenas al usuario.
4.5 Modalidades de colas
En esta sección mostraremos dos
modalidades usuales de colas:
Dicolas
Colas de Prioridad
4.5.1 Dicolas
Las Dicolas son casos particulares de listas y
generalizaciones de colas en donde las eliminaciones e
inserciones pueden realizarse en ambos extremos de la
lista.
El conjunto de operaciones de una dicola consiste en las
operaciones de una cola junto con las siguientes:
publico Elemento ultimo();
public void poner_frente(Objecto elemento);
public void sacar_final(Objeto Elemento)
4.5.1 Especificación del TDA DiCola
Especificación Formal
Tipo: DiCola (Elemento)
Sintaxis:
crea Cola
vacia(Cola) booleano
primero(Cola) Elemento
poner(Cola,Elemento) DiCola //Poner_inicio
sacar(Cola, Elemento) DiCola // Sacar Inicio
Poner_Frente(Cola,Elemento) DiCola
Sacar_Final(Cola, Elemento) DiCola
Ultimo(Cola) Elemento
4.5.2 Cola de Prioridad
Una cola de prioridad es una cola a cuyos
elementos se les ha asignado una prioridad, de
forma que el orden en que los elementos son
procesados sigue las siguientes reglas:
El elemento con mayor prioridad es procesado
primero.
Dos elementos con la misma
prioridad son procesados según el orden en que
fueron introducidos en la cola
4.5.2. Cola de Prioridad
La interface del TDA Cola de Prioridad puede ser la siguiente:
publico interface ColaPrioridad
inicio
publico boolean vacia();
publico Object primero();
publico void poner( elemento E, entero prioridad)
publico void frecuencia_Prioridad ( entero frec,
entero prioridad)
public void sacar(Elemento E );
Fin // fin interface ColaPrioridad
4.5.2 Implementacion con vectores
Definición básica de la clase Cola de Prioridad representada con
Vectores
Clase ColaPri
Atributos
VC arreglo(MAX) Ccola
VF arreglo[MAX] numero
colaAct numero
cant numero
Metodos
Crear() vc vp
vacia();
primero(); cola1 Fre 1
poner( elemento E, entero prioridad)
1
frecuencia_Prioridad ( entero frec, entero prioridad) cola2 Fre 2
sacar(Elemento E ); 2
Fin cola3 Fre 3
Constructor [Link] 3
inicio cola4 Fre 4
// Crear Objetos vc[1], vc[2], vc[3] ..
max
fin
[Link]( E: Elemento , pri :numero)
inicio
vc[pri].poner(E);
Fin 100,200,50 3
4.5.2 Implementación con vectores
[Link]( E: Elemento)
inicio
si no vc[ColaAct].vacia()
entoces
si cant < vf[colaAct]
cant = cant +1
v[ColaAct].sacar(e)
si cant=vf[colaAct]
entoces
colaAct = colaAct +1
cont = 0
retornar e
Fin
4.5.2 Implementación con vectores
ColaPri.Frecuencia_prioridad( frec,prio)
inicio
vf[prio]= frec
Fin
