Colas
Tipo especial de lista en la que las eliminaciones se
realizan al principio y las insercciones al final.
El concepto es muy similiar al de una cola delante de una
ventanilla: quien llega se pone el último y el siguiente a ser atendido es el
primero. Cada uno es atendido cuando le llega su turno.
La cola es una estructura FIFO (First In, First Out): el
primero en llegar es el primero en salir.
Funcionamiento de una cola (dibujo)
Operaciones sobre una cola
Cuatro operaciones posibles:
- Inicializar
- Comprobar si está vacía
- Meter
- Sacar
- implementación: Como una lista pero restringiendo las
operaciones posibles. No obstante, es mejor emplear dos punteros (uno al
primcipio y otro al final):
struct cola{
struct nodo
*principio;
struct nodo
*final;
}
Aplicaciones de las colas
Simulaciones: Modelar un sistema real mediante un prograna
de ordenador, simplificando las cosas, con el fin de obtener datos acererca de
su comportamiento. Por ejemplo, simular una oficina con dos ventanillas para
obtener el tiempo de espera en cada ventanilla.
Servicio de impresión: Cuando tenemos una impresora y varios
usuarios, lo mejor es poner una cola de impresión para que se vayan recibiendo
los trabajos que cada usuario quiere imprimir. Se servirán en orden de llegada.
Procesis en espera para ser ejecutados: Los sistemas
operativos también hacen uso de colas para colocar en ellas a los procesos que
esperan algo, por ejemplo, su turno para ser ejecutados.
Clientes a los que servir un trozo de fichero de servicios
P2P: El emule (y similares) también encola a cada cliente que quiere un fichero
de cada una de las máquinas en las que se sirve. Tanto en este caso como en el
anterior, en ocasiones se usan prioridades en las colas, que permiten que
ciertos elementos avancen más rápido que otros.
Copiar listas (en general)
Está claro que no podemos hacer esto:
struct nodo
*lista;
struct nodo
*otra;
...
otra=lista;
Ya que cualquier cambio que hiciésemos en lista se haría en otra y viceversa.
Si hacemos esto estaríamos sin más copiando un puntero en
otro.
Copiar listas: forma correcta
void copiatLista (struct nodo **dst, struct nodo *fnt){
struct nodo *e, *tmp, *anterior;
tmp=fnt;
*dst=(struct nodo *) malloc (sizeof(struct nodo));
e=*dst;
anterior=NULL;
while (tmp!=NULL){
e->elemento=tmp->elemento;
e->siguiente=(struct nodo *) malloc (sizeof(struct nodo));
anterior=e;
e=e->siguiente;
tmp=tmp->siguiente;
}
free(e);
if (anterior!=NULL){
anterior->siguiente=NULL;
}
else{
*dst=NULL;
}
}
0 comentarios:
Publicar un comentario