Control 1 Estructura de Datos

Estructuras de datos
Matías Sandoval Chacón

Análisis de Algoritmos

Instituto IACC

16 de Agosto del 2018

Desarrollo

1. 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?).

Respuesta: Según lo comprendido en el contenido de la semana, pasamos analizar cada estructura de datos, tales como serian:

• Listas: Es un conjunto de nodos unidos entre sí, formando una cadena.
• Colas: Se puede decir que lo primero en entrar es lo primero en salir. Los elementos son procesados en el orden que fueron insertados en la cola.
• Pilas: Al contrario de las colas, podemos indicar que el primer elemento en entrar es el último en salir.

Ahora en base al caso planteado y también contenido de la semana, que indica que las estructuras de datos pueden ser implementadas utilizando otras estructuras de datos. Para contar los elementos existentes en una pila, podemos aplicarlos a una cola, donde se utilizaría el POP para ir sacando elementos por elemento de la pila, y los datos posteriormente van siendo insertados a la lista y conjunto a ello el conteo respectivo.

1. 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 1]

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).

Respuesta: Para resolver este caso utilizaríamos la estructura de datos de Pilas, donde comenzaríamos utilizando el POP para sacar un elemento de la pila (El tren, ubicado en el terminal A), y hacer un PUSH para ir agregando un elemento a otra pila formada en el terminal B, esto sería realizado con la locomotora y sus respectivos vagones, quedando de la siguiente manera (Izquierda a Derecha): Locomotora – Vagón 1 – Vagón 2 – Vagón 3 – Vagón 4. Posteriormente aplicaría la misma técnica, formando otra pila en el terminal C, con POP saco un elemento y con PUSH lo ubico en el otro terminal respectivo, lo que llevaría en este caso a mover los vagones y finalmente la locomotora, quedando de la siguiente manera (Izquierda a Derecha): Vagón 4 – Vagón 3 – Vagón 2 – Vagón 1 – Locomotora. De esta manera se cumple con el requerimiento que el tren debe quedar en el terminal C, tal cual se encuentra ubicado en el terminal A desde un principio.

...