Estructura De Datos Lineal Y No Lineal
Enviado por ronoel54 • 2 de Octubre de 2011 • 2.051 Palabras (9 Páginas) • 1.232 Visitas
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 o no existe o en terminos de programacion es NULL.
Para tener una lista enlazada con estos nodos, basta con tener la referencia solamente del primero, al igual que para sostener un conjunto de pelotitas enlazadas solo tenemos que agarrarnos de la primera pelotita.
Lista de Doble Enlace
En las listas lineales estudiadas anteriormente el recorrido de ellas solo podía hacerse en un unico sentido: de izquierda a derecha. Sin embargo en muchas ocasiones es necesario recorrer la lista en ambas direcciones. Este tipo de listas se denomina Listas de Doble Enlace o Listas Doblementa Enlazadas. En este tipo de listas cada nodo ha de tener 3 campos: un campo que tiene el dato, otro que tiene la referencia del siguiente nodo y otro que tiene la referencia del nodo anterior
.
Los nodos de la lista son enlazados por medio de los campos enlaces. El ultimo nodo de una lista de doble enlace, no tiene siguiente y el primer nodo de la lista no tiene anterior.
Listas enlazadas circulares
En una lista enlazada circular, el primer y el último nodo están unidos juntos. Esto se puede hacer tanto para listas enlazadas simples como para las doblemente enlazadas. Para recorrer una lista enlazada circular podemos empezar por cualquier nodo y seguir la lista en cualquier dirección hasta que se regrese hasta el nodo original. Desde otro punto de vista,
...