CLOAS 3CV4 ESTRUCTURA Y BASE DE DATOS

COLAS

Es una estructura lineal de datos. Una cola es un grupo ordenado de elementos homogéneos en el que los nuevos elementos se añaden por un extremo (el final) y se quitan por el otro extremo (el frente). En las colas el elemento que entró primero sale también primero, por ello se las llama como listas FIFO (first – in, first – out) "primero en entrar, primero en salir". La diferencia con las pilas es en el modo de entrada / salida de datos; en las colas se realizan las inserciones al final de la lista, no al principio.Por eso, se usan para almacenar datos que necesitan ser procesados según el orden de llegada.C= C (1), C(2), ......., C(N)Las eliminaciones se realizan al principio de la lista frente (front), y las inserciones se realizan en el otro extremo final (rear).

Aplicaciones de las Colas.

Las Colas también se utilizan en muchas maneras en los sistemas operativos para planificar el uso de los distintos recursos de la computadora. Uno de estos recursos es la propia CPU (Unidad Central de Procesamiento).

Si esta trabajando en una sistema multiusuario, cuando le dice a la computadora que ejecute un programa concreto, el sistema operativo añade su petición a su "cola de trabajo".

Cuando su petición llega al frente de la cola, el programa solicitado pasa a ejecutarse. Igualmente, las colas se utilizan para asignar tiempo a los distintos usuarios de los dispositivos de entrada/salida (E/S), impresoras, discos, cintas y demás. El sistema operativo mantiene colas para peticiones de imprimir, leer o escribir en cada uno de estos dispositivos.

Representación de las Colas.

Se las puede representar por listas enlazadas o por arrays

C= Q(1), Q(2)......., Q(n).

En cualquier caso se necesitan dos punteros

frente (f) final (r)

y la lista o array de n elementos (LONGMAX)

parte no utilizada de la lista Cola parte no utilizada de la lista

1

CLOAS 3CV4 ESTRUCTURA Y BASE DE DATOS

Representación de una Cola, mediante un array.

100 264 119 48

frente final

Representación de una Cola mediante una lista enlazada

1 2 3 4

100 264 119 48

frente final

Las operaciones que se pueden realizar con una cola son:

1. Acceder al primer elemento de la Cola2. Añadir un elemento al final de la Cola3. Eliminar el primer elemento de la Cola4. Vaciar una Cola5. Verificar el estado de la Cola: vacía, Llena

Operaciones:

LimpiarPila (Cola)

Función: Inicializa Cola al estado vacío

Entrada: Cola a inicializar

Precondiciones: Ninguna

Salida: Cola (inicializada)

Postcondiciones: Cola está vacía

ColaVacía (Cola)

Función: Indica si la Cola esta vacía

Entrada: Cola a ser comprobada

Precondiciones: Ninguna

Salida: Cola Vacía (indicador Booleano)

Postcondiciones: ColaVacía= (cola está vacía)

ColaLlena (Cola)

Función: Indica si esta llena

Entrada: Cola a ser comprobada

Precondiciones: Ninguna

Salida: Cola llena (indicador Booleano)

Postcondiciones: ColaLlena = (cola está llena)

InsCola (Cola, Nuevo Elemento)

Función: Añade Nuevo Elemento al final de la Cola

Entrada: Cola, Nuevo Elemento a ser añadido

Precondiciones: Hay espacio en la Cola

Salida: Cola (cambiada)

Postcondiciones: Cola = Cola original con Nuevo

2

CLOAS 3CV4 ESTRUCTURA Y BASE DE DATOS

Elemento añadido al final

SupCola (Cola, ElemSuprimido)

Función: Quita el elemento del frente de la Cola y devuelve su valor como ElemSuprimido.

Entrada: Cola

Precondiciones: Cola no esta vacía

Salida: Cola (cambiada)

ElemSuprimido

Postcondiciones: Cola = Cola original con el frente quitado

ElemSuprimido = elemento frente de la cola original

Insertar Elementos.

Definimos el array.

COLA = COLA (1), COLA (2), ...., COLA(n).

n = longitud máxima

f y r = punteros frente y final

x = elementos a insertar

procedimiento inserción

inicio

si r > = n

entonces escribir “desbordamiento de la pila”

sino r r + 1

si r > n

entonces r 1

finsi

COLA(r®

finsi

{ poner el puntero f al valor 1, a fin de poder hacer eliminaciones posteriores }

si f = 0

entonces f 1

finsi

fin

Eliminación de elementos.

El primer elemento introducido Q(n) que es el eliminado, se almacena en una variable auxiliar x, para eliminar se tendrá que verificar que la cadena este vacía.

Procedimiento eliminar

Inicio

{verificar cola vacía}

si f = 0

entonces escribir ‘cola vacía’

sino x cola (f)

f f + 1

si f > n

entonces f 1

finsi

3

CLOAS 3CV4 ESTRUCTURA Y BASE DE DATOS

finsi

{ verificar si la cola se ha quedado vacía y en ese caso dejar los puntero frontal y final en condiciones iniciales, cero}

si f = 0 {condición de pila vacía}

entonces f 0

r 0

finsi

fin

Verificar si la Cola esta vacía.

Una operación muy útil es ver si la cola está vacía. Cola Vacía (Cola) devuelve True si la Cola está vacía y False en los demás casos. Ponemos SupCola cuando la cola no está vacía. Teóricamente ponemos siempre InsCola, porque en principio, una cola no tiene un tamaño limitado. Sin embargo, sabemos de nuestra experiencia con las pilas que ciertas implementaciones requiere que veamos si la estructura está llena antes de añadir otro elemento.

Aprovechamiento de la memoria.

Las colas pueden necesitar cantidad de memoria sobre todo si se diseña con un gran número de elementos. Para evitar este desperdicio de memoria, existe un procedimiento para diseñar las colas mediante una lista circular

Tipos de colas

Colas circulares (anillos): en las que el último elemento y el primero están unidos.

Colas de prioridad: En ellas, los elementos se atienden en el orden indicado por una prioridad asociada a cada uno. Si varios elementos tienen la misma prioridad, se atenderán de modo convencional según la posición que ocupen. Hay 2 formas de implementación:

1. Añadir un campo a cada nodo con su prioridad. Resulta conveniente mantener la cola ordenada por orden de prioridad.

2. Crear tantas colas como prioridades haya, y almacenar cada elemento en su cola.

4

CLOAS 3CV4 ESTRUCTURA Y BASE DE DATOS

Bicolas: son colas en donde los nodos se pueden añadir y quitar por ambos extremos; se les llama DEQUE (Double Ended QUEue). Para representar las bicolas lo podemos hacer con un array circular con Inicio y Fin que apunten a cada uno de los extremos. Hay variantes:

Bicolas de entrada restringida: Son aquellas donde la inserción sólo se hace por el final, aunque podemos eliminar al inicio ó al final.

Bicolas de salida restringida: Son aquellas donde sólo se elimina por el final, aunque se puede insertar al inicio y al final

Información adicional.

Teóricamente, la característica de las colas es que tienen una capacidad específica. Por muchos elementos que contengan siempre se puede añadir un elemento más y en caso de estar vacía borrar un elemento sería imposible hasta que no se añade un nuevo elemento. A la hora de añadir un elemento podríamos darle una mayor importancia a unos elementos que a otros (un cargo VIP) y para ello se crea un tipo de cola especial que es la cola de prioridad.

MANUAL PARA PRINCIPIANTE.

Para correr el programa, debes tener un compilador (borland ó turbo c++).

Entras al compilador escribes el codigo. Ya una vez transcrito el codigo presiona ctrl-F9. Se despliega una ventana con fondo negro

(significa que el codigo esta correcto), en esta aparecen palabras (que imprime el codigo).

Observaras un menu general. Sucursal bancaria. o La primera opicion ( 1 ) banco.

Despliega la informacion del cliente. Nombre. Clave. Recuerde esto porque

sera util alolargo del programa.

Numero de cuenta. Recuerde esto porque sera util alolargo del programa.

Sueldo. Numere de referencia.

Recuerde esto porque sera util alolargo del programa.

5

CLOAS 3CV4 ESTRUCTURA Y BASE DE DATOS

Ya llenando la informacion presiona enter y te regresa a menu general.

o La segunda opcion ( 2 ) cajero. Despliega un submenu. Servicios

La primera opcion ( 1 ) seguir.

o Introduzca su numero de boleta.

Ejecutar procesos.

Retirar. Al momento de realizar esta operación debes de estar conciente del monto inicial.

Consulta de saldo. Los informacion del cliente sera util en esta operación.

Cancelar.

o Al ejecutar esta opcion te regresa

6

CLOAS 3CV4 ESTRUCTURA Y BASE DE DATOS

al manu general.

La segunda opicion ( 2 ) cancelar.

o Al ejecutar esta opcion te regresa al manu general.

o La tercera salir ( 3 ). Al ejecutar esta opción finalizas

totalmente el programa.

MANUAL PARA EXPERTOS.

El programa consiste en una base de datos de un banco donde utilizamos:

- punteros: los punteros nos sirven para apuntar a la dirección de memoria de una variable. - colas: es una estructura de almacenamiento donde la podemos considerar como una en las que estos van hacer insertados por un extremo, exportados por otros.

- for: el for nos permite recorrer un arreglo por medio de variables previamente declaradas.

- while.: la función while nos permite hacer condicionamientos sobre las funciones que se pueden realizar. Así como también se utilizan funciones básicas como:

-- limpiar pantalla (clrscr): esta función se utiliza

para quitar lo que se imprimió en la función

7

CLOAS 3CV4 ESTRUCTURA Y BASE DE DATOS

pasada y evitar que la información que aparece no se encime o traslape.

-- Gotoxy(x,y): esta función parte de la librería getch

se utiliza en la pantalla para dar un formato a lo que se muestra en ella.

-- Scanf : esta función permite al usuario insertar

valores al programa que se guardara temporalmente (mientras el programa siga en ejecución)

En el siguiente código se explican las funciones de las líneas.

#include<stdio.h> // en esta librería maneja scanf, printf#include<conio.h>//esta librería maneja lo que son getch,clrscr#include<stdlib.h>#include<string.h>//esta librería esta declarada para ingresar cadenas#include<ctype.h>

struct colas{ //declara una estructura llamda colaschar clave[100],nc[100],nom[100];//se declaran tres cadenas de longitud 100double sueldo;//una variable doble llamada sueldoint tiquete;//declara una variable entera de nombre tiquetestruct colas *sig;//una apuntador de siguiente};

8

CLOAS 3CV4 ESTRUCTURA Y BASE DE DATOS

struct colas *read=NULL,*front=NULL;//a continuecion se declaran las funciones miembro de la esctructuravoid menu();void dentrar();void boletas();void pasar();void calculo();

main()//funcion principal del programa{menu();//llamaa 1da a la funcion menu

return 0;//no retorna ningun valor}//fin de la funcion main

void menu()//esta es la funcion menu{int n,esta,opcc;//delcara las variables tipo enteras

for(int i=0;;i++)//recorre la cola con el for{clrscr();//limpiar pantallaesta=0;//iguala la variable esta a cero.gotoxy(20,2);//ajusta el texto en las coordenadas 20 en x y 2 en yprintf("BANCO ESIME"); //plantilla que se imprime en pantallagotoxy(10,7);printf("1. PASAR AL CLIENTE AL BANCO");gotoxy(10,9);printf("2. PASAR AL CAJERO ");gotoxy(10,11);printf("3. QUIT");

gotoxy(10,13);printf("DIGITA EL NUMERO DE LA OPCION: ");scanf("%d",&n);//recopila los datos a travez del teclado tipo entero y lo guarda en la variable nswitch(n)//funcion parte de la libreria stdio.h util para el menu{case 1:dentrar();break; //se llama la funcion entrar si n=1case 2:pasar();break;//se llama la funcion pasar si n=2case 3:if(!front)//en este case se condiciona si no es la variable front.esta=1;//iguala la variableelse{

gotoxy(20,17);printf("AUN QUEDAN CLIENTES");gotoxy(20,17);printf("1. DESEA CONTINUAR ATENDIENDO AUN QUEDAN CLIENTES");gotoxy(20,18);

9

CLOAS 3CV4 ESTRUCTURA Y BASE DE DATOS

printf("2. CERRAR SOFTWARE");gotoxy(20,20);printf("OPCION: ");scanf("%d",&opcc);if(opcc==2) // esta funcion if condiciona la variable opcc por si es igual a 2 ejecutar la siguiente accionesta=1;}break; rompe el case}if(esta)break;}

}void dentrar()// llamada a la funcion entrar{char s;//declara una variable unidimensional tipo charint mirar; //declara una variable tipo entera llamada mirarstruct colas *a,*b; // declara dos punteros uno llamado “a” y el otro “b”a=(struct colas*)malloc(sizeof(struct colas)); //iguala la variable “a” a un tamaño de memoria de la estructura colasclrscr();gotoxy(10,2);printf("INFORMACION DEL CLIENTE");gotoxy(10,5);printf("NOMBRE: ");gets(a->nom); gets(a->nom);gotoxy(10,7);printf("CLAVE: ");gets(a->clave);

b=read;s='S';

do{mirar=0;gotoxy(10,9);printf("NUMERO DE CUENTA: ");gets(a->nc);if(read){while(b) //ejecutar la accion si hay una variable b{if(!(strcmp(b->nc,a->nc))){

gotoxy(20,22);printf("YA EXISTE");getch();gotoxy(10,9);printf(" ");gotoxy(20,22);printf(" ");

10

CLOAS 3CV4 ESTRUCTURA Y BASE DE DATOS

mirar=1;break;}b=b->sig;}}if(mirar==0)s='N';}while(s=='S');

gotoxy(10,11);printf("SUELDO: ");scanf("%lf",&a->sueldo);gotoxy(10,17);printf("NUMERO DE BOLETA: ");scanf("%d",&a->tiquete);

if(!read){a->sig=NULL;read=front=a;}else{a->sig=read;read=a;}return;}

void pasar(){struct colas *q;int bol,o;if(front){for(int i=0;;i++){if(!front)break;clrscr();gotoxy(20,2);printf("CAJERO DE SERVICIO");gotoxy(10,6);printf("1. SEGUIR");gotoxy(10,7);printf("2. CANCELAR");gotoxy(10,8);printf("OPCION: ");scanf("%d",&o);if(o==1){gotoxy(10,10);printf("NUMERO DE BOLETA AL SEGUIR [[ %d ]]",front->tiquete);

11

CLOAS 3CV4 ESTRUCTURA Y BASE DE DATOS

gotoxy(10,12);printf("SU NUMERO DE BOLETA: ");scanf("%d",&bol);if(bol==front->tiquete)calculo();else{q=read;while(q){if(q->tiquete==bol){gotoxy(20,20);printf("LO SIENTO POR FAVOR HAGA LA FILA");gotoxy(20,21);printf("LA BOLETA QUE SIGUE ES %d",front->tiquete);getch();break;}q=q->sig;}if(!q){gotoxy(20,20);printf("LO SIENTO NO EXITE EL CLIENTE");getch();}gotoxy(20,20);printf(" ");

}}elsebreak;}}else{gotoxy(10,22);printf("NO HAY NINGUN CLIENTE");getch();gotoxy(10,22);printf(" ");}return;}

void calculo(){struct colas *d;int opc,apro=0,c;double re;char cla[100],con;clrscr();gotoxy(20,2);

12

CLOAS 3CV4 ESTRUCTURA Y BASE DE DATOS

printf("EJECUTAR PROCESO");gotoxy(10,6);printf("SALDO DEL CLIENTE %s ES %.0lf",front->nom,front->sueldo);gotoxy(10,10);printf("1. RETIRAR");gotoxy(10,12);printf("2. CONSIGNAR");gotoxy(10,14);printf("3. NADA");gotoxy(10,16);printf("OPCION DESEADA ");scanf("%d",&opc);gets(cla);gotoxy(10,18);printf("ANTE DE EJECUTAR LA OPERACION POR FAVOR");c=3;do{gotoxy(10,19);printf("CLAVE: ");gets(cla);if(!(strcmp(cla,front->clave)))apro=1;else{gotoxy(10,21);printf("%d OPORTUNIDADES",c);getch();gotoxy(10,21);printf(" ");c--;gotoxy(10,19);printf(" ");

}

}while((c>=0)&&(!apro));

if(apro){apro=0;c=3;do{gotoxy(10,20);printf("NUMERO DE CUENTA: ");gets(cla);if(!(strcmp(cla,front->nc)))apro=1;else{gotoxy(10,21);printf("%d OPORTUNIDADES",c);getch();gotoxy(10,21);

13

CLOAS 3CV4 ESTRUCTURA Y BASE DE DATOS

printf(" ");c--;gotoxy(10,20);printf(" ");}}while((c>=0)&&(!apro));}

if(apro){switch(opc){case 1:while(1){clrscr();gotoxy(5,3);printf("SALDO DEL CLIENTE %s ES %.0lf",front->nom,front->sueldo);gotoxy(10,7);printf("CUANTO DESEA RETIRAR: ");scanf("%lf",&re);if(re>front->sueldo){gotoxy(10,20);printf("NO SE PUEDE POR EL SUELDO QUE ES MENOR");getch();gotoxy(10,20);printf(" ");gotoxy(10,20);printf("DESEA CONTINUAR <S><N> ");con=getche();if(toupper(con)=='N')break;}else{front->sueldo=front->sueldo-re;break;}}gotoxy(1,15);printf("NUEVO SALDO DEL CLIENTE %s ES %.0lf",front->nom,front->sueldo);getch();break;case 2:while(1){clrscr();gotoxy(5,3);printf("SALDO DEL CLIENTE %s ES %.0lf",front->nom,front->sueldo);gotoxy(10,7);printf("CUANTO DESEA CONSIGNAR: ");scanf("%lf",&re);if(re<0){

14

CLOAS 3CV4 ESTRUCTURA Y BASE DE DATOS

gotoxy(10,20);printf("NO EXISTE ESA CANTIDAD");getch();gotoxy(10,20);printf(" ");gotoxy(10,20);printf("DESEA CONTINUAR <S><N> ");con=getche();if(toupper(con)=='N')break;}else{front->sueldo=front->sueldo+re;break;}}gotoxy(1,15);printf("NUEVO SALDO DEL CLIENTE %s ES %.0lf",front->nom,front->sueldo);getch();break;case 3: clrscr();gotoxy(10,10);printf("GRACIAS POR SU ATENCION");getch();break;}}else{d=read;while((d->sig!=front)&&(d!=front))d=d->sig;if(d==front){gotoxy(5,22);printf("LO SIENTO ACCESO DENEGADO POR NO CONSUIDIR CON LA INFORMACION");gotoxy(5,23);printf("COMO NO HAY MAS CLIENTES NO SE ATIENDE MAS");getch();gotoxy(5,22);printf(" ");gotoxy(5,23);printf(" ");}else{gotoxy(5,22);printf("LO SIENTO ACCESO DENEGADO POR NO CONSUIDIR CON LA INFORMACION");gotoxy(5,23);printf("POR FAVOR EL SIGUIENTE ES CON BOLETA %d",d->tiquete);

15

CLOAS 3CV4 ESTRUCTURA Y BASE DE DATOS

getch();gotoxy(5,22);printf(" ");gotoxy(5,23);printf(" ");}}d=read;while((d->sig!=front)&&(d!=front))d=d->sig;if(d==front)front=read=NULL;else{front=d;d=front->sig;front->sig=NULL;}free(d);return;}

16