Estructura De Datos Lineal Y No Lineal

Pilas

Una pila es un concepto aplicable sobre estructuras de datos lineales, en la que la insercion y eliminacion de datos se realiza solo por un extremo denominado cima o tope.

Se define el tope o cima de la pila al unico dato visible de la estructura que seria el ultimo que se coloco (el que esta encima).

Operaciones básicas o permitidas

Entre las operaciones permitidas estan:

• Verificar si es vacia (empty)

• Insertar un dato sobre la pila (push)

• Eliminar un dato de la pila (pop)

• Inspeccionar la cima (top)

a) Pusheando (apilando) elementos sobre la pila

b) Popeando (desapilando) elementos de la pila

Aplicaciones de las Pilas

Las pilas son utilizadas ampliamente para solucionar una amplia variedad de

problemas. Se utilizan en compiladores, sistemas operativos y en programas de

aplicacion. Veamos algunas de las aplicaciones mas interesantes.

✔ Llamadas a métodos.- Cuando se realizan llamadas a metodos, el programa

principal debe recordar el lugar donde se hizo la llamada, de modo que pueda

retornar alli cuando el metodo se haya terminado de ejecutar.

✔ Almacenamiento temporal de páginas Web.- Los navegadores de Internet

almacenan las direcciones de las paginas recientemente visitadas en una pila.

Cada vez que un usuario visita un nuevo sitio, las direcciones son introducidas

en la pila de direcciones. El navegador despues permite al usuario volver a las

paginas visitadas previamente usando un boton.

✔ El mecanismo de “deshacer-rehacer” en los editores de texto.- Los

editores de texto utilizan usualmente un mecanismo de “deshacer” (undo) que

cancela las operaciones editadas actualmente para volver a las operaciones

previas. Para ello se utiliza una pila.

En general, las aplicaciones de esta estructura de datos seran aquellas en las

que los datos se manejen de modo dinamico siguiendo una politica LIFO.

Colas

Las colas son otro tipo de concepto tambien aplicables sobre estructuras de datos lineales. En una cola las eliminaciones se realizan por el principio (inicio) y las inserciones se realizan en el otro extremo (fin).

Se usan para almacenar datos que necesitan ser procesados segun el orden de llegada.

Existen varias formas de implementar a una cola , de forma estatica

utilizando arreglos o bien, de manera dinamica utilizando el concepto de listas. De cualquier manera las operaciones sobre colas tambien deberian tardar una cantidad de tiempo constante en ejecutarse, independientemente del numero de elementos que existan sobre ella.

Operaciones

Entre las operaciones basicas permitidas estan:

• Verificar si es vacia

• Insertar un dato sobre la cola (encolar)

• Eliminar un dato de la cola (decolar)

• Inspeccionar el primero (primero)

Aplicaciones de las Colas

En informatica existen numerosas aplicaciones de las colas. Por ejemplo, en un sistema de tiempo compartido suele haber un procesado central y una serie de perifericos compartidos: discos, impresoras, lectores de CD, etc. Los recursos se comparten por diferentes usuarios y se utiliza una cola para almacenar los programas o las peticiones de los diferentes usuarios que esperan su turno de ejecucion. El procesador central atiende, normalmente, por riguroso orden de llamada del usuario; por tanto, todas las llamadas se almacenan en una cola.

Listas

Una lista en su sentido amplio, es un conjunto de elementos del mismo tipo donde cada elemento tiene un unico predecesor (excepto el primero) y un único sucesor (excepto el ultimo) y cuyo numero de elementos es variable.

S = {a, b, c, d,. . . z}

Ejemplo: Una lista de letras

Operaciones

Entre las operaciones permitidas estan:

• Verificar si es vacia.

• Insertar, eliminar o localizar un elemento.

• Determinar el tamano de la lista.

• Etc.

En fin, una lista podria tener todo tipo de operaciones que le permitan ser manipulada como un arreglo por ejemplo.

Otra forma de ver a una lista es como un conjunto de celdas o nodos que se encuentran enlazados entre si.

Y dependiendo de los enlaces y como se los tenga, podemos tener una lista de simple enlace, lista de doble enlace, lista de simple enlace circular o lista de doble enlace circular.

Lista de Simple Enlace

Cada nodo de la lista tiene 2 campos: un campo que tiene el dato y otro que tiene la referencia del siguiente nodo.

Los nodos de la lista son enlazados por medio de los campos enlaces. El ultimo nodo de una lista de simple enlace, por definicion no tiene siguiente

...