sistemas operativos

¿Qué es una estructura de datos lineal?
Las estructuras lineales de datos se caracterizan porque sus elementos están en secuencia, relacionados en forma lineal, uno luego del otro. Cada elemento de la estructura puede estar conformado por uno o varios sub-elementos o campos que pueden pertenecer a cualquier tipo de dato, pero que normalmente son tipos básicos.
Una estructura lineal de datos oslista está conformada por ninguno, uno o varios elementos que tienen una relación dónde existe un primer elemento, seguido de un segundo elemento y así sucesivamente hasta llegar al último.
El valor contenido en los elementos pueden 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.

¿Qué son lasestructuras lineales y cuáles son sus características?
Existen tres estructuras lineales especialmente importantes:
1.-Las pilas: Una pila, es una estructura de datos en la que el último elemento en entrar es el primero en salir, por lo que también se denominan estructuras LIFO (Last In, First Out) o también estructuras lineales con una política UEPS (Ultimo en entrar, primero en salir).
En estaestructura sólo se tiene acceso a la cabeza o cima de la pila, también solo se pueden insertar elementos en la pila cuando esta tiene espacio y solo se pueden extraer elementos de la pila cuando tenga valores.

Representación grafica de la operación de una pila




Las operaciones básicas en una pila son push y pop
        - Push me permite insertar un elemento a la pila
        - Popextrae un elemento de la pila
 
La forma de implementar una pila es a través de:
        - Por medio de un arreglo unidimensional
        - A través de la clase Stack de la java.util.*
        - Con una lista de elementos.

2.- Colas: Una cola, es una estructura de datos lineal que permite almacenar elementos por un extremo y extraerlos por el otro. Por tal motivo, es una estructura FIFO(first in, first out: primero en entrar, primero en salir).

Al igual que en las pilas, se debe tener el control de la cola, tomando en cuenta de que si se quiere extraer un elemento de la cola se debe asegurar de que no esté vacía, o si se quiere insertar un elemento se debe asegurar de que la cola no esté llena, estas dos acciones se deben desarrollar al hacer operaciones con una cola. Lasoperaciones que aplican a una cola son:
-       Crear una cola.
-       Revisar si la cola está vacía.
-       Revisar si la cola está llena.
-       Insertar un elemento en la cola.
-       Extraer un elemento de la cola.
-       Revisar cuál es el siguiente elemento en la cola.




Funcionamiento
Cola vacía
 
 
 
 
 

Se va a insertar un elemento en la cola, el número 10push(10)(Los elementos se insertan al final de la cola)
10
 
 
 
 
 
Se va a insertar otro elemento en la cola, el número 13 push(13) (Los elementos se insertan al final de la cola)
10
13
 
 
 
 
Se va a insertar otro elemento en la cola, el número 15 push(15) (Los elementos se insertan al final de la cola)
10
13
15
 
 
 
Se va a insertar otro elemento en la cola, el número 20push(20)(Los elementos se insertan al final de la cola)
10
13
15
20
 
 
Se va a insertar otro elemento en la cola, el número 5 push(5)(Los elementos se insertan al final de la cola)

10
13
15
20
5

Si se quiere insertar otro elemento en la cola entonces debe de marcar cola llena, ya que no hay espacio para almacenar ningún otro valor
 
Se extrae un valor de la cola llamando al métodopop() (todos los valores de la cola se sacan del inicio).
10
13
15
20
5
Sale el valor de 10.
 
13
15
20
5
Al sacar el valor de 10 queda con espacio vacío en  la primera posición por lo que se debe de recorrer para que quede espacio para almacenar un nuevo valor.


3.- Listas: Una lista es una estructura de datos secuencial.
Una manera de clasificarlas es por la forma de acceder al...