Aplicaciones De Colas

Ruiz Cruz Ana Lilia Tarea 10

INVESTIGACIÓN DE APLICACIONES DE ESTRUCTURAS LINEALES (3 DE CADA UNA)
Estructura lineal de datos:
Una estructura lineal de datos o lista está conformada por ninguno, uno o varios elementos que tienen una relación de adyacencia ordenada donde existe un primer elemento, seguido de un segundo elemento y así sucesivamente hasta llegar al último. El tipo de dato delos elementos puede ser cualquiera, pero debe ser el mismo tipo para todos. El valor contenido en los elementos puede ser el mismo o diferente. En estas estructuras se realizan operaciones de agregar y/o eliminar elementos a la lista según un criterio particular. Sobre la base de la forma y el lugar de la realización de estas operaciones en la misma, las listas se clasifican en listas de accesorestringido y listas de acceso no restringido.
Las listas de acceso restringido son las pilas, colas y dipolos. En las pilas, las operaciones de acceso se realizan por un único extremo de la lista, al cual normalmente se denomina tope de la pila. En las colas, estas operaciones se realizan por ambos extremos de la lista llamados generalmente, inicio y fin de la cola. Finalmente, en los dipolosque son colas dobles, las operaciones se realizan también por ambos extremos de la lista, en este caso todas las operaciones se pueden hacer por ambos extremos, es decir se puede insertar o eliminar elementos por el tope o por el fin, a diferencia de la cola donde se inserta siempre por el fin y se elimina por el tope. Se puede entonces considerar al dipolo como una clase general de la clasecola.
Las listas de acceso no restringido, denominadas listas, son el tipo más general, al cual se considera como la superclase de las otras clases de listas, en específico de las pilas, colas y dipolos. Haciendo la jerarquía de clases adecuada para estas estructuras, se tiene que la lista es la clase raíz de la jerarquía que tiene como subclases la pila, la cola y el dipolo, este último a suvez tiene como subclases el dipolo de entrada restringida y el dipolo de salida restringida.
Esta jerarquía se observa en la figura:

Pila:
Una pila es un subtipo de las listas donde el acceso está restringido a un solo extremos de la lista, en este caso al tope de la misma.
Las operaciones básicas sobre una pila son: crearla, destruirla, agregar un nuevo elemento, suprimir un elemento,consultar el elemento del tope y verificar si está vacía.
Cola:
Una cola es otro subtipo de las listas donde el acceso está restringido a los extremos de la lista, es decir al inicio y al fin de la misma, en la cola las operaciones básicas son: creación, destrucción, inserción al final de un nuevo elemento, eliminación del inicio de un elemento, consultar que elemento está al inicio y cual al final,y verificar si la cola está vacía.
Dipolo:
Esta estructura equivale a dos colas colocadas una en un sentido y la otra en sentido contrario, por ello las operaciones de inserción y eliminación se pueden realizar por ambos extremos. Dos casos especiales se pueden tener, el dipolo de entrada restringida donde sólo se puede insertar por un extremo y eliminar por ambos, y el dipolo de salidarestringida, donde se puede insertar por ambos extremos y sólo se puede suprimir por un extremo. Se llamará a estos extremos como izquierdos (izq.) y derecho (der).
Lista:
La lista es el tipo más general de estructura lineal donde las inserciones y eliminaciones se hacen en cualquier punto de la lista, por ello se debe especificar donde se requiere que se haga la operación, sus operaciones básicasson: creación, destrucción, inserción, eliminación, consulta y verificación de lista vacía.
Entre las múltiples aplicaciones que tienen estas estructuras podemos mencionar:
* El desarrollo de compiladores de lenguajes de programación que están conformados por varios subprogramas con finalidades más específicas, como por ejemplo: el analizador de léxico que genera la tabla de símbolos.
* La...