Please enable JavaScript.
Coggle requires JavaScript to display documents.
Estructuras de Datos Lineales - Coggle Diagram
Estructuras de Datos Lineales
Origen
1955
:
Klaus Samelson
y
Friedrich L. Bauer
presentan la estructura de datos de pila . Posteriormente lo patentaron en 1957. Existe la necesidad de evaluar algunos símbolos más tarde, incluso cuando aparecen antes en la secuencia. Es en este contexto que se inventa la estructura de datos de pila.
1945:
John von Neumann
usa arreglos cuando implementa el algoritmo de clasificación por fusión. Las primeras computadoras digitales durante este período utilizan arreglos para tablas de datos y operaciones vectoriales o matriciales.
1960
: En un intento por mejorar el rendimiento de tiempo y espacio para el procesamiento de datos en cintas magnéticas,
Windley
propone la estructura de datos en árbol
Los primeros lenguajes de las décadas de
1950
y
1960
, como Fortran, Algol, COBOL y BASIC, utilizan matrices indexadas con soporte para matrices multidimensionales.
1956
:
Allen Newell
,
Herbert A. Simon
y
JC Shaw
inventan e implementan listas enlazadas y procesamiento de listas para el desarrollo de programas de inteligencia artificial.
1975
:
Tarjan
analiza el rendimiento de las operaciones de búsqueda y unión en conjuntos disjuntos.
Más tarde,
Tarjan
inventa el árbol de distribución de estructuras de datos (
1980
) y el montón de Fibonacci (
1985
).
Tipos de estructuras lineales
Pilas
Son estructuras de datos lineales, donde el ultimo en entrar es el primero en salir (LIFO).
Colas
Son estructuras de datos FIFO, donde el primero en entrar es el primero en salir.
Listas enlazadas
Estructura lineal que almacena una coleccion de elementos y los encadena mediante una estructura auxiliar, generalmente llamados nodos.
Aplicaciones
Aplicación de colas:
Colas de procesos, dentro de los sistemas operativos y asignación de recursos en CPU.
Servicion al cliente.
Deliver o entrega de paquetes.
Transporte y tránsito (Semaforación)
Transferencias de datos en redes.
Aplicacion de listas enlazadas:
No tiene un campo especifico de aplicacion. Son la base de todo tipo de estructura lineal e inclusive de las no-lineales, como tablas Hash, Map, Grafos, Arboles. Es decir su campo de aplicación es el todo en cuanto TAD se refiere.
Aplicacion de pilas
Teorías y algoritmos de compiladores (Análisis léxico/ sintáctico)
Solución de expresiones algebraica dentro del ámbito de la computación. Notación infija y notación polaca.
Gestión de proceso de los sistemas operativos.
Gestión de memoria y proceso en máquinas virtuales como JRE/JVM, .net CLR.
Manejo de procesos recursivos.
Soporte al desarrollo de cualquier tipo de software.