Proyecto colas

Aplicación de Colas
Proyecto de investigación
Aplicación de colas en la vida diaria las conocemos por ejemplo cuando recibimos un mensaje de texto al teléfono celular y la impresora.

López Castro Stefan Curiel Chapul Eduardo Zamora Quintero Joel 11/09/2009

Página |2 Índice Pagina Concepto de Cola
Aplicaciones Tipo Cola Implementado como Arreglo

3

Colas implementadas con MemoriaDinámica
Algoritmo Para Añadir elementos en la cola Algoritmo Para eliminar

7

Aplicación de Cola
Explicación de la aplicación de cola

9

Listas Enlazadas
Tipos De Listas

16
18 19

El TAD Lista
Operaciones con las listas

Listas Simplemente Enlazadas
Estructura del Nodo Función getnodo() Función Insertar después del nodo apuntado por p Función Borrar después de..., buscar.Ejemplo 1

Listas Doblemente Enlazadas
Insertar al frente de la lista Insertar al final de la lista Función Eliminar Ejemplo 1.1

27

Listas Circulares
Declaración de la estructura Función getnodo(), ingresar, eliminar Ejemplo 1.2 y explicación.

39

Listas Circulares Doblemente Enlazadas
Declaración de la estructura Función getnodo(), ingresar, buscar Ejemplo 1.3

44

Bibliografía50

| PAC

Página |3 Concepto de Cola Una cola, es una estructura en la cual se almacenan elementos en orden de llegada, es decir que, se ingresan los elementos por la parte final de la estructura y se eliminan (o se sirven) por la parte del frente.

Como puede observarse, ésta estructura cuenta con dos apuntadores, uno que apunta al último elemento y otro que apunta hacia el primerelemento (o el elemento del frente). Se debe tener en cuenta que, una cola, almacena los datos en ella, manteniendo cierto orden, ya que sus elementos se añaden por el final de la cola y se extraen o se eliminan por la parte de frente. El lector dispersará el por qué la insistencia de ello, pero cuando uno inicia este estudio, al momento de programar, se confunde fácilmente, por que las sentencias delas funciones son muy parecidas a la de una pila. Las operaciones con las colas son: -insert (q, x) Inserta el elemento x en la parte posterior de la cola q -remove (q) Suprime el elemento delantero de la cola q -empty (q) Retorna True o false, si la cola tiene elementos o no. Las colas pueden implementarse, al igual que las pilas, mediante dos formas:
 

Arrays Memoria DinámicaTipo Cola Implementado como Arreglo

La figura de arriba, muestra la forma de implementar una cola, como arreglo, en la que cada casilla, representa una estructura compuesta por el tipo de dato a guardar (o bien otra estructura).

| PAC

Página |4 Las variables q.rear y q.front, se van modificando cada vez que añadimos o eliminamos datos de nuestra cola. Para determinar la cantidad deelementos en cualquier momento es: Cant=q.rear-q.front+1 Ahora vemos un ejemplo del funcionamiento de las colas, implementadas como arreglos: Supongamos que en una cola vamos a almacenar elementos de tipo carácter. Insert (&q, ‘A’);

q.rear=0, q.front=0 insert (&q, ‘B’)

q.rear=1 q.front=0 insert (&q, ‘C’);

q.rear=2 q.front=0 remove (&q);

q.rear=2 q.front=1 remove (&q);

q.rear=2 q.front=2insert (&q, ‘D’);

| PAC

Página |5

CD 01234 q.rear=3 q.front=2 insert(&q, ‘E’);

q.rear=4 q.front=2 Como se puede ver, al manejar una cola en forma de arreglo lineal, resulta complicado y poco eficiente, porque al eliminar elementos quedan nodos vacíos y cuando se llega al último elemento de la cola, aparecerá un mensaje de error, o al menos debería aparecer, que indique que ya no hay másespacios, sin embargo, eso sería una total mentira, ya que tenemos elementos sin utilizar; una solución para ello podría ser, el considerar la cola, como un arreglo circular.

Pero el manejo de los subíndices, resulta bastante complejo, poco accesible y tampoco se resuelve el problema de la eficiencia; es decir que ésta solución tampoco resulta eficiente para el problema que se intenta...