ESTRUCTURA DE DATOS

Abril 27 del 2020

 TADs LINEALES: COLAS
Una cola es una estructura de datos que almacena
elementos en una lista y permite acceder a los
datos por uno de los dos extremos de la lista.
Un elemento se inserta en la cola (parte final) de
la lista y se suprime o elimina por el frente (parte
inicial, frente) de la lista. Las aplicaciones utilizan
una cola para almacenar elementos en su orden
de aparición o concurrencia.
 TADs LINEALES: COLAS
Los elementos se eliminan (se quitan) de la cola en el mismo orden en que se
almacenan y, por consiguiente, una cola es una estructura de tipo FIFO (first-in,
firs-out, primero en entrar-primero en salir o bien primero en llegar-primero en
ser servido).
El servicio de atención a clientes en un almacén es un ejemplo típico de cola.
La acción de gestión de memoria intermedia (buffering) de trabajos o tareas de
impresora en un distribuidor de impresoras (spooler) es otro ejemplo típico de
cola.
Dado que la impresión es una tarea (un trabajo) que requiere más tiempo que el
proceso de la transmisión real de los datos desde la computadora a la impresora,
se organiza una cola de trabajos de modo que los trabajos se imprimen en el
mismo orden en el que se recibieron por la impresora.
Este sistema tiene el gran inconveniente de que si su trabajo personal consta de
una única página para imprimir y delante de su petición de impresión existe otra
petición para imprimir un informe de 300 páginas, deberá esperar a la impresión
de esas 300 páginas antes de que se imprima su página.
 TADs LINEALES: COLAS

Las operaciones usuales en las colas son Insertar y Quitar. La

operación Insertar añade un elemento por el extremo final de la
cola, y la operación Quitar elimina o extrae un elemento por el
extremo opuesto, el frente o primero de la cola. La organización de
elementos en forma de cola asegura que el primero en entrar
es el primero en salir.
 TADs LINEALES: COLAS
Especificaciones del tipo abstracto de datos Cola
Las operaciones que sirven para definir una cola y poder manipular
su contenido son las siguientes:
Tipo de dato Elemento que se almacena en la cola.
Operaciones
CrearCola Inicia la cola como vacía.
Insertar Añade un elemento por el final de la cola.
Quitar Retira (extrae) el elemento frente de la cola.
Cola vacía Comprueba si la cola no tiene elementos.
Cola llena Comprueba si la cola está llena de elementos.
Frente Obtiene el elemento frente o primero de la cola.
Tamaño de la cola Número de elementos máximo que puede
contener la cola
 TADs LINEALES: COLAS
En una cola, al igual que en una pila, los datos se almacenan de
un modo lineal y el acceso a los datos sólo está permitido en los
extremos de la cola.
La forma que los lenguajes tienen para representar el TAD Cola
depende de donde se almacenen los elementos: en un array, en
una estructura dinámica en una lista enlazada.
La utilización de arrays tiene el problema de que la cola no
puede crecer indefinidamente, está limitada por el tamaño del
array; como contrapartida, el acceso a los extremos es muy
eficiente. Utilizar una lista enlazada permite que el número de
nodos se ajuste al de elementos de la cola; por el contrario, cada
nodo necesita memoria extra para el enlace, y también hay que
tener en cuenta el límite de memoria del computador.
TADs LINEALES: COLAS
 TADs LINEALES: COLAS
IMPLEMENTACIÓN CON ARRAYS
Al igual que las pilas, las colas se implementan
utilizando una estructura estática (arrays) o
una estructura dinámica (listas enlazadas).
La declaración de una Cola ha de contener un array
para almacenar los elementos de la cola y dos
marcadores o apuntadores para mantener las
posiciones frente y fin de la cola, es decir, un
marcador apuntando a la posición de la cabeza de la
cola y el otro al primer espacio vacío que sigue al
final de la cola.
 TADs LINEALES: COLAS
IMPLEMENTACIÓN CON ARRAYS
Cuando un elemento se añade a la cola, se verifica
si el marcador fin apunta a una posición válida, y
entonces se añade el elemento a la cola y se
incrementa el marcador fin en 1.
Cuando un elemento se elimina de la cola, se hace
una prueba para ver si la cola está vacía y, si no es
así, se recupera el elemento de la posición apuntada
por el marcador de cabeza, y éste se incrementa en
1.
 TADs LINEALES: COLAS
IMPLEMENTACIÓN CON ARRAYS

La operación de poner un elemento en la cola

comienza en la posición fin 0, y cada vez que
se añade un nuevo elemento se incrementa fin en 1.
La extracción de un elemento se hace por el
extremo contrario, frente, y cada vez que se extrae
un elemento avanza frente una posición.
En la siguiente Figura se puede observar cómo
avanza el puntero frente al extraer un elemento.
 TADs LINEALES: COLAS
IMPLEMENTACIÓN CON ARRAYS

Una alternativa consiste

en mantener fijo el
frente de la cola al
comienzo del array y
mover todos los
elementos de la cola
una posición cada vez
El avance lineal de frente y fin tiene un grave que se retira un
elemento. Estos
problema, deja huecos por la izquierda del array . problemas quedan
Llega a ocurrir que fin alcanza el índice mas alto del resueltos considerando
array, sin que puedan añadirse nuevos elementos, y, el array como
sin embargo, hay posiciones libres a la izquierda de circular.
frente.
 TADs LINEALES: COLAS
Declaración de la clase Cola
Una cola debe tratar elementos de diferentes tipos de datos: enteros, cadenas, objetos...
Por esta circunstancia, los elementos han de ser de un tipo genérico. En Java todavía no está
definido el tipo genérico; sin embargo, declarando el tipo del elemento Object y utilizando
objetos y referencias se puede conseguir el mayor grado de genericidad.
La clase ColaLineal contiene un array (listaCola) cuyo máximo tamaño se determina
por la constante MAXTAMQ. El tipo de los elementos queda sin especificar
(TipoDeDato), para que pueda sustituirse por un tipo simple, o bien por Object.
Los atributos frente y fin son los punteros de cabecera (frente) y cola (fin),
respectivamente.
El constructor de la clase inicializa una cola vacía y define el array: new TipoDeDato
[MAXTAMQ].
La operación insertar toma un elemento y lo añade al final de la cola.
Quitar suprime y devuelve el elemento de la cabeza de la cola.
La operación frente devuelve el elemento que está en la primera posición (frente) de la
cola, sin eliminar el elemento.
 TADs LINEALES: COLAS
Declaración de la clase Cola
La operación de control colaVacia comprueba si la cola tiene elementos, ya que es
necesaria esta comprobación antes de eliminar un elemento.
La operación colaLlena comprueba si la cola está llena, esta comprobación se realiza antes
de insertar un nuevo miembro.
Si las precondiciones para insertar y quitar se violan, el programa debe generar una
excepción o error.
 TADs LINEALES: COLAS
Declaración de la clase Cola

En la clase se hace referencia a un tipo no

definido, TipoDeDato; es necesario sustituir
ese identificador por el tipo verdadero de los
elementos.
Otra cuestión más importante es que esta
implementación de una cola es notablemente
ineficiente, ya que se puede alcanzar la condición
de cola llena existiendo elementos del array sin
ocupar.
Esto se debe a que, al realizar la operación de
quitar un elemento, avanza el frente y, por
consiguiente, las posiciones anteriores quedan
desocupadas, no accesibles.
 TADs LINEALES: COLAS
COLA CON UN ARRAY CIRCULAR
La forma más eficiente de almacenar una cola en un array
es modelarlo de tal forma que se una el extremo final con
el extremo cabeza. Tal array se denomina array circular y
permite que la totalidad de sus posiciones se utilicen para
almacenar elementos de la cola sin necesidad de desplazar
elementos.
El array se almacena de modo natural en la
memoria como un bloque lineal de n
elementos.
Se necesitan dos marcadores (apuntadores)
frente y fin para indicar, respectivamente,
la posición del elemento cabeza y del último
elemento puesto en la cola.
 TADs LINEALES: COLAS
COLA CON UN ARRAY CIRCULAR
El frente siempre contiene la posición del primer elemento
de la cola y avanza en el sentido de las agujas del reloj; fin
contiene la posición donde se puso el último elemento y
también avanza en el sentido del reloj (circularmente a la
derecha). La implementación del movimiento circular se
realiza según la teoría de los restos, de tal forma que se
generen índices de 0 a MAXTAMQ-1:
 TADs LINEALES: COLAS
COLA CON UN ARRAY CIRCULAR
Los algoritmos que formalizan la gestión de colas en un array circular han de incluir las
operaciones básicas del TAD Cola, en concreto, las siguientes tareas :
Creación de una cola vacía, de tal forma que fin apunte a una posición inmediatamente
anterior a frente:
frente = 0; fin = MAXTAMQ-1.
Comprobar si una cola está vacía:
frente == siguiente(fin)
Comprobar si una cola está llena. Para diferenciar la condición de cola llena de cola
vacía se sacrifica una posición del array, de tal forma que la capacidad de la cola va a
ser MAXTAMQ-1. La condición de cola llena es:
frente == siguiente(siguiente(fin))
Poner un elemento a la cola: si la cola no está llena, avanzar fin a la siguiente posición,
fin = (fin + 1) % MAXTAMQ, y asignar el elemento.
Retirar un elemento de la cola: si la cola no está vacía, quitarlo de la posición frente y
avanzar frente a la siguiente posición:(frente + 1) % MAXTAMQ.
Obtener el elemento primero de la cola, si la cola no está vacía, sin suprimirlo de la cola.
 TADs LINEALES: COLAS
Clase COLA con un array circular

La clase declara los apuntadores frente, fin y el

array listaCola[].
Para obtener la siguiente posición de una dada,
aplicando la teoría de los restos, se escribe el
método siguiente().
A continuación, se codifican los métodos que
implementan las operaciones del TAD Cola.
Ahora el tipo de los elementos es Object, de tal
forma que se pueda guardar cualquier tipo de
elementos.
TADs LINEALES: COLAS
Clase COLA con un array circular
TADs LINEALES: COLAS
Clase COLA con un array circular
TADs LINEALES: COLAS
Clase COLA con un array circular
 Clase PilaLineal. Ejemplo
Encontrar un numero capicúa leído del dispositivo estándar de
entrada.
El algoritmo para encontrar un número capicúa utiliza conjuntamente una Cola y una
Pila.
El número se lee del teclado, en forma de cadena con dígitos. La cadena se procesa
carácter a carácter, es decir, dígito a dígito (un dígito es un carácter del 0 al 9). Cada
dígito se pone en una cola y, a la vez, en una pila. Una vez que se terminan de leer los
dígitos y de ponerlos en la Cola y en la Pila, comienza el paso de comprobación: se
extraen en paralelo elementos de la cola y de la pila, y se comparan por igualdad. De
producirse alguna no coincidencia entre dígitos, significa que el número no es
capicúa, y entonces se vacían las estructuras para pedir, a continuación, otra entrada.
El número es capicúa si el proceso de comprobación termina con la coincidencia de
todos los dígitos en orden inverso y tanto la pila como la cola quedan vacías.
¿Por qué utilizar una pila y una cola? Sencillamente porque aseguran que se procesan
los dígitos en orden inverso; en la pila, el último en entrar es el primero en salir; en la
cola, el primero en entrar es el primero en salir.
Cola con Lista Enlazada