Análisis de algoritmo

Estructuras de Datos

Tania Escobar Gangas

Análisis de Algoritmo

Instituto IACC

12/11/2018

Caso Estudio I

 De acuerdo a lo visto en los contenidos de la semana y al hecho de que las estructuras de datos pueden ser implementadas utilizando otras estructuras de datos, ¿cómo sería una estrategia para contar los elementos existentes en una pila? (Es decir, ¿cómo sería una forma eficiente de construir la función Count?).

Antes de explicar cómo contar los elementos en una pila, se definirá lo que es una. Una pila es una estructura que se basa en que el último elemento en entrar será el primer elemento en salir (LIFO), en un ejemplo cotidiano seria como una pila de libro, al llegar al tome si deseamos sacar un que se encuentre en medio debemos sacar uno a uno de los que se encuentran de arriba hacia abajo, algunas de las funciones básicas de las pilas se encuentran las siguientes:

• Print, para imprimir los ítems.
• Push, para agregar los ítems.
• Pop, para eliminar un ítems.
• Count, para contar los ítems.
• Peek, para indicar el valor del primer ítem.
• IsEmpty, para saber si la pila esta vacía o no.

[pic 1]

[pic 2]

Caso Estudio II

 La empresa ferroviaria ABC-Ferrocarriles está en proceso de remodelación de algunos de sus terminales de trenes y necesita mover un tren completo (locomotora y 4 vagones) desde el terminal A al terminal C, como muestra la figura.

[pic 3]

 La dificultad en esta operación es que el tren debe quedar en el terminal C en el mismo orden del que salió del terminal A, frente a esta situación se le ha pedido a Ud. que ayude con una estrategia para cumplir con el objetivo. Entonces, ¿qué tipo de estructura de datos utilizaría para resolver el problema?

Genere la estrategia para mover el tren y escriba cómo lo haría (puede usar el terminal B para apoyarse).

En este caso estudio utilizaremos la estructura de datos de una cola, los elementos de una cola funcionan bajo la filosofía de FIFO (First In, First Out), el primero en entrar es el primero en salir. En la imagen anteriormente mostrada se ve una locomotora con sus respectivos vagones, que serán enumerados para poder ejemplificar más abajo. Vagón 4, vagón 3, vagón 2, vagón 1, locomotora 0. Se agregaron uno a uno los números desde el 0 al 4 (Add) entonces al momento de eliminarlos (Remove) para posicionarlo en B o en C se eliminara el primero elemento agregado por ende será 0, y luego el segundo insertado que es 1 y así sucesivamente hasta llegar a 4 y la locomotora con sus vagones quedaran en la misma posición pero en la letra C.

...