CREADOR:

MARIANA SANCHEZ PARRA

UNIVERSIDAD FERMÍN TORO VICE-RECTORADO ACADÉMICO

FACULTAD DE INGENIERÍA

ESTRUCTURA DE DATO COLA

MATERIA: Análisis de algoritmo

SECCION:

NI-318

PROF: Elvia Sánchez

Resumen

Nombre: Mariana Sánchez Parra

Cedula: 20.669.170

En esta revista daré a conocer un poco sobre la teoría de colas lineales y circulares, se implementaran algunas imágenes en las cuales se demostrara de manera grafica la evolución y el desarrollo de una estructura llamada cola. Junto a esto se darán a conocer algunos algoritmos los cuales podrán ser utilizados al momento de programar y compilar estos programas.

índice • DEFINICION DE COLA LINEAL

• DEFINICION DE COLA CIRCULAR

• EJEMPLO DE LA VIDA REAL

• ANADIR ELEMENTO EN UNA COLA VACIA

• OPERACIONES BASICAS

• ALGORITMO DE COLA

• ANEXOS

• CHISTES

• HOROSCOPO

2

DEFINICION DE COLA LINEAL

• Estructura

Una cola lineal es como una línea recta en la que todos los elementos o instrucciones están de pie uno detrás del otro. Hay un comienzo y un final definidos en la cola. Las tareas alineadas en este formato cola se ejecutan en el orden de su colocación, de manera FIFO (First In First Out) (primero que entra, primero que sale).

3

INSERCION Y ELIMINACION En una cola lineal, una nueva tarea es insertada al final de la lista, mientras una eliminación se hace en la parte del primer elemento de la lista. Los extremos primero y último son responsables del seguimiento del estado de la cola. Una cola puede tener un número finito de elementos predefinidos. Cada nueva inserción debe pasar una prueba de "cola llena", y del mismo modo, antes de la eliminación, una prueba de "cola vacía" debe aprobarse. Una "Cola llena" revisa si que hay espacio para la inserción, y una "cola vacía" se asegura de que hay elementos en espera de ser eliminados y la cola no está ya vacía.

• Costo de mantenimiento y tiempo

En una cola lineal, para una nueva inserción al final, tiene que haber un espacio vacío en el primer elemento, y todos los elementos intermedios deben subir un espacio para crear un espacio para la nueva inserción. Cada vez que hay una nueva inserción, los pasos se tienen que repetir. La inserción y eliminación son dos pasos diferentes. Este enfoque consume tiempo y es computacionalmente caro.

4

COLAS CIRCULARES

• Estructura

Las colas lineales tienen un grave problema, como las extracciones sólo pueden realizarse por un extremo, puede llegar un momento en que el apuntador A sea igual al máximo número de elementos en la cola, siendo que al frente de la misma existan lugares vacíos, y al insertar un nuevo elemento nos mandará un error de overflow (cola llena).

Para solucionar el problema de desperdicio de memoria se implementaron las colas circulares, en las cuales existe un apuntador desde el último elemento al primero de la cola.

5

INSERCION Y ELIMINACION

En una cola circular, inserciones y supresiones pueden ocurrir en cualquier posición de la cola y no necesariamente en un orden secuencial.

• Costo de mantenimiento y tiempo

Este enfoque consume tiempo y es computacionalmente caro. Por otro lado, en una cola circular, una inserción y una eliminación pueden ocurrir simultáneamente.

6

EJEMPLO DE LA VIDA REAL Las diferencias entre las dos estructuras de colas pueden ser entendidas con ejemplos de la vida real. Una línea para boletos de cine y clientes esperando en una estación de gasolina de su turno, son ejemplos de una estructura lineal. Las personas son atendidas en el orden en que llegan a la taquilla o a la estación de gasolina. Un menú de teléfono celular o los planetas en un sistema solar, siguen el patrón de cola circular.

7

ANADIR ELEMENTO EN UNA COLA VACIA Cola vacía

• Partiremos de que ya tenemos el nodo a insertar y, por supuesto un puntero que apunte a él, además los punteros que definen la cola, primero y ultimo que valdrán NULL:

Elemento encolado

• El proceso es muy simple, bastará con que:

• Hacer que nodo->siguiente apunte a NULL.

• Que el puntero primero apunte a nodo.

• Y que el puntero último también apunte a nodo.

8

ANADIR ELEMENTO EN UNA COLA NO VACIA

• De nuevo partiremos de un nodo a insertar, con un puntero que apunte a él, y de una cola, en este caso, al no estar vacía, los punteros primero y ultimo no serán nulos:

Cola no vacía

Elemento encolado

• El proceso sigue siendo muy sencillo:

• Hacemos que nodo->siguiente apunte a NULL.

• Después que ultimo->siguiente apunte a nodo.

• Y actualizamos ultimo, haciendo que apunte a nodo.

9

OPERACIONES BASICAS Para añadir una función

• Creamos un nodo para el valor que colocaremos en la cola.

• Hacemos que nodo->siguiente apunte a NULL.

• Si "ultimo" no es NULL, hacemos que ultimo->>siguiente apunte a nodo.

• Actualizamos "ultimo" haciendo que apunte a nodo.

• Si "primero" es NULL, hacemos que apunte a nodo.

Para leer una función

• Hacemos que nodo apunte al primer elemento de la cola, es decir a primero.

• Asignamos a primero la dirección del segundo nodo de la cola: primero->siguiente.

• Guardamos el contenido del nodo para devolverlo como retorno, recuerda que la operación de lectura equivale a leer y borrar.

• Liberamos la memoria asignada al primer nodo, el que queremos eliminar.

• Si primero es NULL, haremos que último también apunte a NULL, ya que la cola habrá quedado vacía.

10

ALGORITMO DE LA FUNCION ANADIR

void Anadir(pNodo *primero, pNodo *ultimo, int v) { pNodo nuevo; /* Crear un nodo nuevo */ nuevo = (pNodo)malloc(sizeof(tipoNodo)); nuevo->valor = v; /* Este será el último nodo, no debe tener siguiente */ nuevo->siguiente = NULL; /* Si la cola no estaba vacía, añadimos el nuevo a continuación de ultimo */ if(*ultimo) (*ultimo)->siguiente = nuevo; /* Ahora, el último elemento de la cola es el nuevo nodo */ *ultimo = nuevo; /* Si primero es NULL, la cola estaba vacía, ahora primero apuntará también al nuevo nodo */ if(!*primero) *primero = nuevo; }

11

ALGORITMO DE LA FUNCION LEER int Leer(pNodo *primero, pNodo *ultimo) { pNodo nodo;

int v;

/* variable auxiliar para manipular nodo */

/* variable auxiliar para retorno */

/* Nodo apunta al primer elemento de la pila */

nodo = *primero; if(!nodo) return 0;

/* Si no hay nodos en la pila retornamos 0 */

/* Asignamos a primero la dirección del segundo nodo */

*primero = nodo->siguiente;

/* Guardamos el valor de retorno */

v = nodo->valor;

/* Borrar el nodo */

free(nodo);

/* Si la cola quedó vacía, ultimo debe ser NULL también*/

if(!*primero) *ultimo = NULL; return v; }

ANEXOS

12

13

CHISTES

CHISTES CORTOS

• - ¿Bailamos? - Claro. ¿Pero quién saca a mi amiga? - Ahhh, por eso no te preocupes. ¡SEGURIDAAAAD!

• - Mamá, ¿qué haces en frente de la computadora con los ojos cerrados? - Nada, hijo, es que Windows me dijo que cerrara las pestañas...

14

HOROSCOPO • ARIES: EL DÍA DE HOY TRAERÁ NUEVA

ENERGÍA EN TU CAMINO. UN COLEGA O AMIGO TE SUGERIRÁ UN NUEVO PROCEDIMIENTO O ESTRATEGIA DISTINTA. ¡SI ESCUCHAS LO QUE TIENE QUE DECIR, DESCUBRIRÁS QUE POSIBLEMENTE TE ESTÁ PRESENTANDO UNA SOLUCIÓN MÁGICA!

• TAURO: HOY LA ALINEACIÓN CELESTIAL TE BENDICE CON BUENA FORTUNA Y SENTIMIENTOS DE ARMONÍA. ALGUNOS CORRESPONDERÁN A QUE RECIBIRÁS NOTICIAS FELICES. O PUEDE QUE PASES UN BUEN MOMENTO CON TU AMOR SECRETO QUE TE LLENARÁ EL CORAZÓN CON TERNURA.

• GEMISIS: HOY DESCUBRIRÁS UN SECRETO OCULTO. NO EXISTE NADA QUE TE GUSTE MÁS QUE EL MISTERIO, Y HOY TENDRÁS LA OPORTUNIDAD DE DESCUBRIR UNO. PUEDE SER ALGO PEQUEÑO, COMO DESCUBRIR CUÁL ES LA MELODÍA FAVORITA DE TU PAREJA.

• CANCER: HOY SENTIRÁS GANAS DE CONECTARTE CON TUS AMISTADES. A VECES TRABAJAS TANTO Y TE ESTANCAS TANTO EN LOS PROBLEMAS QUE TE NIEGAS UN POCO LA VIDA SOCIAL. ÁBRETE A LA ENERGÍA POSITIVA QUE LOS DEMÁS DESEAN BRINDARTE.

• LEO: ES MUY COMÚN QUE TE HAYAS ACOSTUMBRADO A OTRAS DIMENSIONES.

CON LA ENERGÍA CELESTIAL ACTUAL, RECIBIRÁS ALGUNAS PREMONICIONES O VISIONES QUE PARECEN PROVENIR DE ARRIBA. EL TRUCO ES REALMENTE HACERLE HONOR A LAS REVELACIONES QUE RECIBES, AUNQUE RESULTEN EFÍMERAS.

• VIRGO: HOY LA CONFIGURACIÓN CELESTIAL TE PONDRÁ EN HUMOR DE FIESTA, POR LO TANTO SI NO HAS HECHO PLANES PARA LA NOCHE, COMIENZA A PENSAR EN ALGO ATREVIDO Y DIVERTIDO. SENTIRÁS COMO SI SALIERAS DEL CAPARAZÓN Y GRITARÁS A TODO PULMÓN.

15

HOROSCOPO • LIBRA: HOY TENDRÁS UN HUMOR MUY

ROMÁNTICO. ES IMPORTANTE QUE ENCUENTRES UNA AMISTAD VERDADERA EN TU PAREJA. DESEAS QUE RESPETE LAS METAS DE TU VIDA Y EL RUMBO QUE HAS ELEGIDO PARA TU CARRERA.

• ESCORPIO: LA ENERGÍA ASTRAL DEL DÍA TE HARÁ SENTIR NERVIOSISMO E INQUIETUD. DEMÁS, TENDRÁS SENSIBILIDAD HACIA LA ENERGÍA DE OTRAS PERSONAS PORQUE ESTARÁS CON UN HUMOR HIPERSENSIBLE.

• SAGITARIO: EL DÍA DE HOY TE AUGURARÁ CAMBIOS INESPERADOS PERO POSITIVOS EN TU VIDA PERSONAL. LOS MIEMBROS FAMILIARES DESCUBRIRÁN NUEVOS CAMINOS QUE DESEAN SEGUIR. UNA OPORTUNIDAD REPENTINA PARA AVANZAR NECESITARÁ UN MOVIMIENTO, PERO NO PERMITAS QUE LA RESISTENCIA AL CAMBIO SE INTERPONGA EN TU CAMINO.

• CAPRICORNIO: UNA SENSACIÓN INCREMENTADA DE UNIDAD ENTRE TUS AMISTADES MÁS ÍNTIMAS Y ENTRE CUALQUIER GRUPO AL QUE TENGAS AFILIACIÓN AUMENTARÁ TU SENSACIÓN DE EMOCIÓN Y ENTUSIASMO PARA EL FUTURO. LAS RELACIONES CON EL SEXO OPUESTO TE

SERÁN ESPECIALMENTE BENEFICIOSAS.

• ACUARIO: PROPONTE EL COMENZAR UNA RUTINA DE MEDITACIÓN O ALGÚN TIPO DE YOGA. PUEDES CONSIDERAR COMPRAR ALGÚN OBJETO ADIVINADOR O UN MAZO DE CARTAS DE TAROT. TIENES UNA CONEXIÓN MUY FUERTE CON LO OCULTO.

• PISCIS: HOY, LAS COSAS NO SALDRÁN COMO TE ESPERABAS, PERO SI TE RELAJAS TODO SE RESOLVERÁ. LA ENERGÍA SOCIAL TRAERÁ ALGUNAS SORPRESAS QUE NO SERÁN DESAGRADABLES. LO QUE SÍ, TENDRÁS UNA DISCUSIÓN DESAGRADABLE CON UN FAMILIAR O AMIGO QUE TE HARÁ ABRIR LOS OJOS A ALGÚN SECRETO QUE SE TE HA ESCONDIDO.