Estructura de datos: lista, pilas y colas

1. Estructura de Datos TAD Lista, Pila y Cola Huáscar Génere 10-1006 Prof. Rina Familia

2. Concepto de Lista Es un TAD que nos permite almacenar datos de una forma organizada, al igual que los vectores pero, a diferencia de estos, esta estructura es dinámica, por lo que no tenemos que saber "a priori" los elementos que puede contener. Los elementos de una lista, suelen recibir también el nombre de nodos de la lista.

3. Concepto de Pila 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 ). En esta estructura sólo se tiene acceso a la cabeza o cima de la pila.

4. Concepto de Cola Una cola es una estructura de datos donde el primer elemento en entrar es el primero en salir, también denominadas estructuras FIFO ( First In, First Out ). Esta estructura de datos se puede definir como una lista enlazada con acceso FIFO a la que sólo se tiene acceso al final de la lista para meter elementos y al principio de esta para sacarlos.

5. Operaciones Basicas de las Pilas -PUSH (insertar).- Agrega un elementos a la pila en el extremo llamado tope. -POP (remover).- Remueve el elemento de la pila que se encuentra en el extremo llamado tope. -VACIA.- Indica si la pila contiene o no contiene elementos. -LLENA.- Indica si es posible o no agregar nuevos elementos a la pila.

6. Operaciones básicas en Colas Insertar.- Almacena al final de la cola el elemento que se recibe como parámetro. Eliminar.- Saca de la cola el elemento que se encuentra al frente. Vacía.- Regresa un valor booleano indicando si la cola tiene o no elementos (true – si la cola esta vacía, false – si la cola tiene al menos un elemento). Llena.- Regresa un valor booleano indicando si la cola tiene espacio disponible para insertar nuevos elementos ( true – si esta llena y false si existen espacios disponibles).

7. Diferencias entre Pila y Cola La diferencia radica en cuales son los elementos que salen primero -> Pilas (Primeras en entrar, Ultimas en salir): Son como una pila de libros, los primeros que entran a la pila son los últimos que salen porque quedan abajo de los últimos. -> Colas(Primeras en entrar, Primeras en salir): Son como la cola para comprar un boleto del cine, los primeros en entrar a la cola son los primeros que salen de ella. Otra diferencias es que en las pilas los ítems se añaden y se eliminan en el mismo extremo

8. Operaciones Básicas de una Lista Insertar: Agrega un elemento a la lista. Eliminar: Retira un elemento de la lista. Buscar: Busca un elemento en la lista. Recorrer: Visita todos los elementos de la lista. Vacía: Indica si la lista contiene o no elementos . Tamaño: Indica el número de elementos de la lista.

9. Ventana en una Lista Ventanas muestra información sobre todas las ventanas de las áreas de trabajo de CDE. Una vez arrancada, la lista de ventanas se actualizará de manera dinámica .

10. Diferencias entre estructuras estáticas y dinámicas La diferencia entre estructuras estáticas y dinámicas es el manejo de memoria . Estáticas: Durante la ejecución del programa el tamaño de la estructura no cambia Dinámicas: Durante la ejecución del programa el tamaño de la estructura puede cambiar

11. Ejemplos de lenguajes de implementación Aplicaciones de Pilas // Funcion factorial public static int factorial( int n) { if (n<=1) return 1; else return n*factorial(n-1); } // Funcion fibonacci public static int fib( int n) { if (n==1) return 0; else if (n==2) return 1; else return fib(n-1)+fib(n-2); }

12. Insertar un nuevo dato en una posición determinada con listas /* obtiene el numero de nodos de la lista */ length = g_slist_length (list); g_print ("\ nEscribe el nº de indice donde se insertara el dato (el indice maximo es %d): ", length); scanf ("%d", &index); /* inserta el valor en la posicion indicada */ if (index < length) { l ist = g_slist_insert (list, GINT_TO_POINTER (value), index); print_list (list); }