Chapter 19
Colas
Este capítulo presenta dos TADs: la Cola y la Cola Priorizada. En la
vida real, una cola es una fila de clientes esperando un servicio
de algún tipo. En la mayoría de los casos, el primer cliente de la fila
es el primero al que se va a servir. Sin embargo, hay excepciones. En los
aeropuertos, a veces se saca de la cola a los clientes cuyos vuelos van a
salir pronto. En los supermercados, un cliente educado puede dejar que
alguien que lleva pocos productos pase antes.
La regla que determina quién va primero se llama táctica de
encolamiento. La táctica de encolamiento más simple se llama FIFO,
de "first-in-first-out", "el primero que entra es el primero que sale". La
táctica de encolamiento más general es el encolamiento priorizado,
en la que a cada cliente se le asigna una prioridad y el cliente con la
prioridad más alta pasa primero, sin importar el orden de llegada. Decimos
que es la táctica más general porque la prioridad se puede basar en
cualquier cosa: a qué hora sale el vuelo; cuántos productos lleva el
cliente; cuán importante es el cliente. Por supuesto, no todas las
tácticas de prioridad son "justas", pero la justicia siempre es subjetiva.
El TAD Cola y el TAD Cola Priorizada tienen el mismo conjunto de
operaciones. La diferencia está en la semántica de las operaciones: una cola
usa la táctica FIFO, y una cola priorizada (como su propio nombre indica)
usa una táctica de encolamiento priorizado.
19.1 El TAD Cola
El TAD Cola se define a través de las siguientes operaciones:
\begin{description
\item[{\tt \_\_init\_\_}:] Inicializa una cola nueva vacía.
\item[{\tt insert}:] Añade un elemento a la cola.
\item[{\tt remove}:] Elimina y devuelve un elemento de la cola. El elemento devuelto es el
primero que se añadió.
\item[{\tt isEmpty}:] Comprueba si la cola está vacía.
\end{description}
\section{Cola Enlazada}
\index{cola enlazada}
\index{cola!implementación enlazada}
La primera implementación del TAD Cola al que vamos a echar un vistazo
se llama {\bf cola enlazada} porque está hecha de ojetos {\tt Nodo}
enlazados. He aquí la definición de la clase:
\beforeverb
\begin{verbatim}
class Cola:
def __init__(self):
self.longitud = 0
self.cabeza = None
def estaVacia(self):
return (self.longitud == 0)
def inserta(self, cargo):
nodo = Nodo(cargo)
nodo.siguiente = None
if self.cabeza == None:
# si la lista está vacía el nuevo nodo va el primero
self.cabeza = nodo
else:
# encuentra el último nodo de la lista
ultimo = self.cabeza
while ultimo.siguiente: ultimo = ultimo.siguiente
# añadir el nuevo nodo
ultimo.siguiente = nodo
self.longitud = self.longitud + 1
def quita(self):
cargo = self.cabeza.cargo
self.cabeza = self.cabeza.siguiente
self.longitud = self.longitud - 1
return cargo
\end{verbatim}
\afterverb
%
Los métodos {\tt estaVacia} y {\tt quita} son idénticos a los métodos
{\tt estaVacia} y {\tt quitaPrimero} de {\tt ListaEnlazada}.
El método {\tt inserta} es nuevo y un poco más complicado.
Queremos insertar nuevos elementos al final de la lista. Si la cola está
vacía, simplemente hacemos que {\tt cabeza} se refiera al nuevo nodo.
En caso contrario, recorremos la lista hasta el último nodo y lo fijamos
al final. Podemos reconocer el último nodo porque su atributo
{\tt siguiente} es {\tt None}.
En un objeto {\tt Cola} correctamente construido hay dos invariantes.
El valor de {\tt longitud} debería ser el número de nodos en la cola,
y el último nodo debería tener {\tt siguiente} igual a {\tt None}.
Créase que este método cumple con ambas invariantes.
\section{Rendimiento típico}
\index{redimiento}
Normalmente cuando invocamos un método, no nos importan los detalles
de su implementación. Pero hay un "detalle" que podría interesarnos:
el rendimiento típico del método. ¿Cuánto tarda, y cómo varía el
tiempo de ejecución al aumentar el número de elementos de la colección?
Primero mire {\tt quita}. Ahí no hay bucles ni llamadas a funciones,
dando a entender que el tiempo de ejecución de este método es siempre el
mismo. Un método así se llama operación de {\bf tiempo constante}. En
realidad, el método podría ser ligeramente más rápido cuando la lista
está vacía porque se salta el cuerpo de la condición, pero esa
diferencia no es significativa.
\index{tiempo constante}
El rendimiento de {\tt inserta} es muy diferente. En el caso general,
tenemos que recorrer la lista para encontrar el último elemento.
Este recorrido cuesta un tiempo proporcional a la longitud de la
lista. Como el tiempo de ejecución es función lineal de la longitud,
este método se llama de {\bf tiempo lineal}. Comparado con el tiempo
constante, es muy pobre.
\index{tiempo lineal}
\section{Cola Enlazada Mejorada}
\index{cola!implementación mejorada}
\index{cola mejorada}
Nos gustaría una implementación del TAD Cola capaz de
realizar todas las operaciones en tiempo constante. Una forma
de hacerlo es modificar la clase Cola de modo que mantenga
una referencia tanto al primero como al último nodo, como se
muestra en la figura:
\beforefig
\centerline{\psfig{figure=illustrations/queue1.eps}}
\afterfig
La implementación de {\tt ColaMejorada} es así:
\beforeverb
\begin{verbatim}
class ColaMejorada:
def __init__(self):
self.longitud = 0
self.cabeza = None
self.ultimo = None
def estaVacia(self):
return (self.longitud == 0)
\end{verbatim}
\afterverb
%
Hasta ahora, el único cambio es el atributo {\tt ultimo}. Se usa en
los métodos {\tt inserta} y {\tt quita}:
\beforeverb
\begin{verbatim}
class ColaMejorada:
...
def inserta(self, cargo):
nodo = Nodo(cargo)
nodo.siguiente = None
if self.longitud == 0:
# si la lista está vacía, el nuevo nodo es la cabeza y el último
self.cabeza = self.ultimo = nodo
else:
# encontrar el último nodo
ultimo = self.ultimo
# añadir el nuevo nodo
ultimo.siguiente = nodo
self.ultimo = nodo
self.longitud = self.longitud + 1
\end{verbatim}
\afterverb
%
Como {\tt ultimo} sigue el rastro del último nodo, no necesitamos buscarlo.
A causa de esto, este método funciona en tiempo constante.
Debemos pagar un precio por esa velocidad. Tenemos que añadir un caso
especial a {\tt quita} para apuntar {\tt ultimo} a {\tt None} cuando
quitamos el último nodo:
\beforeverb
\begin{verbatim}
class ColaMejorada:
...
def quita(self):
cargo = self.cabeza.cargo
self.cabeza = self.cabeza.siguiente
self.longitud = self.longitud - 1
if self.longitud == 0:
self.ultimo = None
return cargo
\end{verbatim}
\afterverb
%
Esta implementación es más complicada que la de la Lista Enlazada, y
es más difícil demostrar que es correcta. La ventaja es que hemos
alcanzado la meta: tanto {\tt inserta} como {\tt quita} son operaciones
de tiempo constante.
\begin{quote}
{\em Como ejercicio, escriba una implementación del TAD Cola usando
una lista de Python. Compare el rendimiento de esta implementación
con la de la {\tt ColaMejorada} para varias longitudes de cola.}
\end{quote}
\section{Cola priorizada}
\index{cola priorizada!TAD}
\index{TAD!Cola Priorizada}
El TAD Cola Priorizada tiene el mismo interfaz que
el TAD Cola, pero diferente semántica. De nuevo, el
interfaz es:
\begin{description}
\item[{\tt \_\_init\_\_}:] Inicializa una cola vacía nueva.
\item[{\tt inserta}:] Añade un nuevo elemento a la cola.
\item[{\tt quita}:] Elimina y devuelve un elemento de la cola.
El elemento devuelto es el de prioridad más alta.
\item[{\tt estaVacia}:] Comprueba si la cola está vacía.
\end{description}
La diferencia semántica es que el elemento eliminado de la cola no es
necesariamente el primero que se añadió. En su lugar, es el elemento con
la prioridad más alta. Lo que son las prioridades y cómo se comparan con
las otras no se especifica en la implementación de la Cola Priorizada.
Depende de los elementos de la cola.
Por ejemplo, si los elementos de la cola tienen nombres, podemos elegirlos
en orden alfabético. Si son puntuaciones de bolos, podemos ir de mayor a
menor, pero si son puntuaciones de golf, iremos de menor a mayor. Siempre
que podamos comparar los elementos de la cola, podermos encontrar y quitar
el elemento con mayor prioridad.
Esta implementación de Cola Priorizada tiene como atributo una lista de Python
que contiene los elementos de la cola.
\beforeverb
\begin{verbatim}
class ColaPriorizada:
def __init__(self):
self.elementos = []
def estaVacia(self):
return self.elementos == []
def inserta(self, elemento):
self.elementos.append(elemento)
\end{verbatim}
\afterverb
%
El método de inicialización, {\tt estaVacia}, e {\tt inserta} son todos
chapados de las operaciones sobre listas. El único método interesante es
{\tt quita}:
\beforeverb
\begin{verbatim}
class ColaPriorizada:
...
def quita(self):
maxi = 0
for i in range(1,len(self.elementos)):
if self.elementos[i] > self.elementos[maxi]:
maxi = i
elemento = self.elementos[maxi]
self.elementos[maxi:maxi+1] = []
return elemento
\end{verbatim}
\afterverb
%
Al principio de cada iteración, {\tt maxi} contiene el índice del elemento
más grande (prioridad más alta) que hemos visto {\em hasta el momento}.
Cada vez que se completa el bucle, el programa compara el {\tt i}ésimo
elemento con el campeón. Si el nuevo elemento es mayor, el valor de
{\tt maxi} se fija a {\tt i}.
\index{barrido}
Cuando la sentencia {\tt for} completa su ejecución, {\tt maxi} es el
índice del elemento mayor. Este elemento se elimina de la lista y se
devuelve.
Vamos a provar la implementación:
\beforeverb
\begin{verbatim}
>>> c = ColaPriorizada()
>>> c.inserta(11)
>>> c.inserta(12)
>>> c.inserta(14)
>>> c.inserta(13)
>>> while not c.estaVacia(): print c.quita() # muestra cuál se quita :)
14
13
12
11
\end{verbatim}
\afterverb
%
Si la cola contiene números o cadenas simples, se eliminan en
orden numérico o alfabético, de mayor a menor. Python puede
encontrar el entero o la cadena mayor porque puede compararlos
usando los operadores de comparación internos.
Si la cola contiene un tipo de objeto, debe proporcionar un método
{\tt \_\_cmp\_\_}. Cuando {\tt quita} usa el operador {\tt >} para
comparar elementos, invoca al {\tt \_\_cmp\_\_} de uno de los elementos
y le pasa el otro como parámetro. Siempre que el método {\tt \_\_cmp\_\_}
trabaje adecuadamete, la Cola Priorizada funcionará.
\section{La clase {\tt Golfista}}
\index{Golfista}
\index{clase!Golfista}
\index{prioridad}
\index{sobrecarga de operadores}
\index{sobrecarga!operador}
Como ejemplo de un objeto con una definición inusual de prioridad, vamos
a implementar una clase llamada {\tt Golfista} que mantiene los nombres y
puntuaciones de golfistas. Como es habitual, empezamos por definir {\tt
\_\_init\_\_} y {\tt \_\_str\_\_}:
\beforeverb
\begin{verbatim}
class Golfista:
def __init__(self, nombre, puntuacion):
self.nombre = nombre
self.puntuacion = puntuacion
def __str__(self):
return "%-16s: %d" % (self.nombre, self.puntuacion)
\end{verbatim}
\afterverb
%
{\tt \_\_str\_\_} usa el operador de formato para poner los nombres y las
puntuaciones en bonitas columnas.
\index{operador de formato}
\index{operador!formato}
A continuación definimos una versión de {\tt \_\_cmp\_\_} en la que la
puntuación más baja tiene la prioridad más alta. Como siempre,
{\tt \_\_cmp\_\_} devuelve 1 si {\tt self} es "mayor que" {\tt otro}, -1 si {\tt self}
es "menor que" otro, y 0 si son iguales.
\beforeverb
\begin{verbatim}
class Golfista:
...
def __cmp__(self, otro):
if self.puntuacion < otro.puntuacion: return 1 # menos es más
if self.puntuacion > otro.puntuacion: return -1
return 0
\end{verbatim}
\afterverb
%
Ya estamos listos para probar la cola priorizada con la clase {\tt Golfista}:
\beforeverb
\begin{verbatim}
>>> tiger = Golfer("Tiger Woods", 61)
>>> cabr = Golfer("Ángel Cabrera", 72)
>>> ola = Golfer("J.M. Olazábal", 69)
>>>
>>> cp = ColaPriorizada()
>>> cp.inserta(tiger)
>>> cp.inserta(cabr)
>>> cp.inserta(ola)
>>> while not cp.estaVacia(): print cp.quita()
Tiger Woods : 61
J.M. Olazábal : 69
Ángel Cabrera : 72
\end{verbatim}
\afterverb
\begin{quote}
{\em Como ejercicio, escriba una implementación del TAD Cola Priorizada
usando una lista enlazada. Debería usted mantener la lista ordenada de
modo que la eliminación sea una operación de tiempo constante. Compare
el rendimiento de esta implementación con la implementación con la lista
de Python.}
\end{quote}
\section{Glossario}
\index{cola}
\index{táctica de encolamiento}
\index{FIFO}
\index{cola priorizada}
\index{chapado}
\index{tiempo constante}
\index{tiempo lineal}
\index{obstáculo al rendiminto}
\index{cola enlazada}
\index{buffer circular}
\index{clase abstracta}
\index{interfaz}
\begin{description}
\item[cola:] Un conjunto ordenado de objetos esperando un servicio
de algún tipo.
\item[Cola:] Un TAD que ejecuta las operaciones que uno podría realizar
sobre una cola.
\item[táctica de encolamiento:] Las reglas que determinan qué miembro de
la cola será el próximo en eliminarse.
\item[FIFO:] "First In, First Out", una táctica de encolamiento en la que
el primer miembro en llegar es el primero en salir.
\item[cola priorizada:] Una táctica de encolamiento en la que cada miembro
tiene una prioridad determinada por factores externos. El miembro con mayor
prioridad es el primero en eliminarse.
\item[Cola Priorizada:] Una TAD que define las operaciones que se pueden
realizar sobre una cola priorizada.
\item[cola enlazada:] Una implementacion de una cola utilizando una lista
enlazada.
\item[tiempo constante:] Una operación cuyo tiempo de ejecución no depende
del tamaño de la estructura de datos.
\item[tiempo lineal:] Una operación cuyo tiempo de ejecución es función lineal
del tamaño de la estructrua de datos.
\end{description}