Listas y Pilas

Objetivos

  • Practicar el manejo de listas
  • Entender las diferencias entre listas encadenadas y arreglos dinámicos
  • Utilizar las estructuras de pila para solucionar un problema práctico

Problema: Listas encadenadas vs arreglos dinámicos

Las listas encadenadas y los arreglos dinámicos son dos estructuras de datos ampliamente utilizadas en la industria. Cada una tiene ventajas y desventajas, y es responsabilidad del programador analizar el problema al que se enfrenta para elegir correctamente cuál es la mejor opción.

Reflexione, en los siguientes casos ¿qué estructura tiene un mejor desempeño, una lista simplemente encadenada, o un arreglo dinámico?

  • Agregar/eliminar
  • Acceder a elementos dada su posición
  • Uso del espacio

Ahora, haga un experimento

  1. Ingresar a la carpeta taller_3 que se encuentra en el repositorio talleres-templates. En caso de no contar con una copia del repositorio, puede realizar una copia directamente a su máquina local, usando el comando git clone https://[email protected]/talleres/talleres-templates.git.

  2. A continuación, iniciar DrJava y seleccionar en el menú principal Project->Open, luego escoger el archivo project.xml que se encuentra en la carpeta taller_3. Esto abrirá el proyecto en DrJava.

  3. Cree una lista enlazada simple y un arreglo dinámico de números enteros, puede utilizar las clases previstas de java LinkedList y ArrayList.

  4. Haga un ciclo donde se agreguen elementos aleatorios a la lista y otro ciclo en el que se agreguen elementos aleatorios al arreglo dinámico.

  5. Documente el tiempo que se demora cada una agregando cada vez mas elementos.

    long tInicio= System.currentTimeMillis();

//código de ejecución

long tTranscurrido = System.currentTimeMillis()-tInicio();

    Asegúrese de ejecutar cada ciclo por separado y varias veces cada uno para sacar un promedio del tiempo que toma agregar los elelentos a cada uno. Haga pruebas agregando 1000, 2000, 4000, 8000,16000 , 32000 y 64000 elementos.

  6. ¿Qué sucede con los desempeños de cada colección? ¿Cuál obtiene un mejor rendimiento con mayor número de elementos?.

¿Por qué sucede esto?, si en teoría la lista encadenada tiene una complejidad para agregar de O(1) y el arreglo dinámico de O(1) si se realiza un análisis amortizado y de O(n) en el peor de los casos.

Taller 3: Pilas

Una pila es útil para muchas aplicaciones de uso común. Por ejemplo, un editor de texto guarda la información de las acciones del usuario en una pila, de manera que al deshacerlas se haga en el orden apropiado.

Para aplicar sus conocimientos sobre las pilas, se desarrollará una aplicación que compruebe que un String en formato JSON está escrito de manera correcta.

Para que un String JSON sea correcto, se necesita que cada vez que se abra algún tipo de caracter reservado como los paréntesis, llaves o comillas, se verifique que se cierren en el orden correcto. A continuación se muestra un ejemplo correcto y uno incorrecto:

  • Correcto:
    { a : [1,2,3,4], b: “A”, c: “”}

  • Incorrecto:

    { a : [1,2,3,4], b: “A”, c: “”)

    Recuerde que dentro de un string que inicia y termina con comillas dobles, los paréntesis pueden usarse libremente:

    { a : [1,2,3,4], b: “[[[A”, c: “}”}

Haga uso de las técnicas aprendidas en clase para crear una aplicación que reciba un String por consola y retorne si es o no válido. De no ser válido indique en que posición se encontró el error.

  1. Descargue el esqueleto del taller 3 de [https://bitbucket.org/talleres/talleres-templates]. En el mismo encontrará la clase pilasCLI, que maneja la comunicación por interfaz, y una pequeña interfaz IVerificador.
  2. Cree una nueva clase que implemente la interfaz IVerificador.
  3. Implemente el método cargarArchivo, que debe leer un archivo .json dado su nombre (y extensión) y retornar su contenido. Como precondición, asuma que este archivo se encuentra en la carpeta data. Puede leer un archivo .json como leería cualquier archivo de texto plano.
  4. Implemente el método hayError. Este método verifica que el String que entra por parámetro sea un String JSON válido, y retorna la posición del carácter donde se encontró el error, o -1 en caso de ser correcto.
  5. Pruebe su aplicación (por ejemplo cree o busque nuevos archivos JSON).

A continuación encontrará algunos casos de prueba que puede utilizar para validar su aplicación. Estos casos se encuentran también en la carpeta data del esqueleto:

Google Maps - Correcto

{"markers": [
    {
        "point": [40.266044,-74.718479],
        "homeTeam":"Lawrence Library",
        "awayTeam":"LUGip",
        "markerImage":"images/red.png",
        "information": "Linux users group meets second Wednesday of each month.",
        "fixture":"Wednesday 7pm",
        "capacity":"",
        "previousScore":""
    },
    {
        "point":[40.211600,-74.695702],
        "homeTeam":"Hamilton Library",
        "awayTeam":"LUGip HW SIG",
        "markerImage":"images/white.png",
        "information": "Linux users can meet the first Tuesday of the month to
        work out harward and configuration issues.",
        "fixture":"Tuesday 7pm",
        "capacity":"",
        "tv":""
    },
    {
        "point":[40.294535,-74.682012],
        "homeTeam":"Applebees",
        "awayTeam":"After LUPip Mtg Spot",
        "markerImage":"images/newcastle.png",
        "information": "Some of us go there after the main LUGip meeting,
        drink brews, and talk.",
        "fixture":"Wednesday whenever",
        "capacity":"2 to 4 pints",
        "tv":""
    }
]}

Facebook-Incorrecto

{
    "data": [
        {
            "id": "X999_Y999",
            "from": {
                "name": "Tom Brady", "id": "X12"
            },
            "message": "Looking forward to 2010!",
            "actions": [
            {
                "name": "Comment",
                "link": "http://www.facebook.com/X999/posts/Y999"
            ,
            {
                "name": "Like",
                "link": "http://www.facebook.com/X999/posts/Y999"
            }
            ],
            "type": "status",
            "created_time": "2010-08-02T21:27:44+0000",
            "updated_time": "2010-08-02T21:27:44+0000"
        },
    {
        "id": "X998_Y998",
        "from": {
            "name": "Peyton Manning", "id": "X18"
        },
        "message": "Where's my contract?",
            {
                "name": "Like",
                "link": "http://www.facebook.com/X998/posts/Y998"
            }
        ],
        "type": "status",
        "created_time": "2010-08-02T21:27:44+0000",
        "updated_time": "2010-08-02T21:27:44+0000"
        }
    ]
}
[

Reto (Opcional)

  • Implemente un aplicación que compruebe si un String en formato HTML es correcto.

Entrega para bonificación

Fecha límite de entrega: Ver

  1. Siga las instrucciones de estructura de talleres presentes en Envío talleres
  2. Realice pruebas unitarias para la aplicación de la pila, que como mínimo, validen los casos presentados en los ejemplos.
  3. Asegúrese que su aplicación funciona con cualquier otro String JSON y que se puede ingresar por consola y el resultado se muestra en esta misma.
  4. En el archivo README.md describa claramente los pasos para poder ejecutar su aplicación y pruebas.
  5. Implemente también una estructura de cola y una de bolsa y realice las pruebas unitarias para las operaciones de add, iterar y obtener un elemento.
  6. En el archivo readme escriba un promedio del tiempo que toma agregar N elementos a cada una de sus estructuras usando N = 4000, 8000, 16000 , 32000 y 64000.
  7. Cargue el taller a su repositorio en Bitbucket.