Trabajo De Colas Combinadas

[pic] [pic]


INSTITUTO POLITÉCNICO NACIONAL


ESCUELA SUPERIOR DE INGENIERÍA MECÁNICA Y ELÉCTRICA



UNIDAD CULHUACÁN



“TRABAJO DE COLAS”


ESTRUCTURA DE BASE DE DATOS



PROFESOR: JESUS RODRIGUEZ BUENDIA





SILVA MIRANDA MARTIN





3EM6




















Estructura de las colasUna cola es un tipo especial de lista abierta en la que sólo se puede insertar nodos en uno de los extremos de la lista y sólo se pueden eliminar nodos en el otro. Además, como sucede con las pilas, las escrituras de datos siempre son inserciones de nodos, y las lecturas siempre eliminan el nodo leído.
Este tipo de lista es conocido como lista FIFO (First In First Out), el primero en entrar esel primero en salir.
De manera similar a las pilas, las colas definen una estructura no estándar, de manera que se debe crear un nuevo tipo de dato, el tipo cola, que debe tener los siguientes elementos:
• Un arreglo de [pic]elementos de algún tipo específico, puede incluso ser un tipo estándar o no.
• Un número que indica el elemento que está en la posición del frente de la cola.
•Un número que indica el elemento que está en la posición trasera de la cola.


[pic]

Es evidente, a la vista del gráfico, que una cola es una lista abierta. Así que sigue siendo muy importante que nuestro programa nunca pierda el valor del puntero al primer elemento, igual que pasa con las listas abiertas. Además, debido al funcionamiento de las colas, también deberemos mantener un punteropara el último elemento de la cola, que será el punto donde insertemos nuevos nodos.
Teniendo en cuenta que las lecturas y escrituras en una cola se hacen siempre en extremos distintos, lo más fácil será insertar nodos por el final, a continuación del nodo que no tiene nodo siguiente, y leerlos desde el principio, hay que recordar que leer un nodo implica eliminarlo de la cola.
Suponiendo quelos elementos son números enteros, una idea para representar una cola en C/C++ es usar un arreglo para contener los elementos y emplear otras dos variables para representar la parte frontal y trasera de la cola.
#define maxQueue 100

struct cola{
int items[maxQueue];
int front;
int rear;
};
Esta representación con arreglos es completamente válida, pero debemos tener cuidado con loslímites del arreglo. Suponiendo que no existiera la posibilidad de caer en un desbordamiento del arreglo, es decir, que se insertaran más elementos de lo que el arreglo puede almacenar, la operación insert podría quedar como:
void insert(struct cola *C, int e){
C->items[++C->rear]=e;
}
y al operación x=remove(Q)
int remove(struct cola *C){
return C->items[C->front++];
}
y finalmente laoperación empty(Q):
bool empty(struct cola *C){
if(C->front>C->rear)
return true;
else
return false;

La diferencia con las pilas reside en el modo de entrada y salida de los datos, en las colas las inserciones se realizan al final de la lista, no al principio.

COLAS CON PRIORIDAD
Una cola con prioridad es una estructura de datos en la que se ordenan los datos almacenados de acuerdo a uncriterio de prioridad. Hay dos tipos de colas de prioridad:
• Las colas de prioridad con ordenamiento descendente.
• Las colas de prioridad con ordenamiento ascendente.
En las colas de prioridad ascendente se pueden insertar elementos en forma arbitraria y solamente se puede remover el elemento con menor prioridad. Si CPA es una cola de prioridad ascendente, la operación insert (CPA, x)inserta el elemento x en la cola CPA; y la operación x=minRemove (CPA) asigna a x el valor del elemento menor (de su prioridad) y lo remueve de la cola.
En las colas de prioridad descendente es similar, pero sólo permite la supresión del elemento más grande. Las operaciones aplicables a la cola de prioridad descendente son insert (CPD,x) y x=maxRemove(CPD), cuando CPD es una cola de prioridad...