Lunes 11 de Octubre

Estructuras de Datos

Objetivos: Definir el concepto de estructura de datos y mostrar cómo se puede implementar una pila por medio de una lista enlazada..

Temas:

Implementación de tipos de datos abstractos

Los tipos de datos son los enteros, reales, valores booleanos y todos los objetos. Un tipo de datos es abstracto cuando los programadores pueden trabajar con él conociendo sólo sus operaciones. Uno puede abstraerse de su implementación y utilizarlos exitosamente. Por ejemplo, en este curso hemos usado las pilas, colas y arreglos asociativos sin conocer su implementación, y por lo tanto son tipos de datos abstractos.

La abstracción es importante para poder disminuir la complejidad de los problemas que se enfrentan. Sin embargo, también es útil conocer aspectos de la implementación de los tipos de datos con los que se trabaja y por ello estudiamos como se representaban los números reales. Esto nos permite entender mejor sus limitaciones, como el número finito de decimales que puede almacenar.

En este capítulo estudiaremos las técnicas que se usan para implementar los tipos de datos abstractos como las pilas, colas, arreglos asociativos y otros. Es decir definiremos (implementaremos) estas clases.

Estructuras de datos

Cuando se implementa una clase es necesario preocuparse de:

Veremos que existen patrones de organización para las variables de instancia. Estos patrones se denominan estructuras de datos.

La estructura de datos de uso más frecuente es el arreglo. Las pilas, colas y arreglos asociativos se implementan fácilmente por medio de arreglos nativos. Sin embargo, el resultado presenta serias deficiencias que resolveremos por medio de dos nuevas estructuras de datos: las listas enlazadas y los árboles.

Ejemplo: Implementación de una pila de enteros

El problema reside en donde almacenar los elementos de la pila. Lo más fácil es almacenarlos en un arreglo:

    class Queue extends Program {
      int a[];
      int tope;
      int tamanno;
      Queue() {
        max= 100;
        a= new int[max];
        tope= 0;
      }
      void push(int x) {
        if (tope>max) {
          println("desborde de pila");
          exit(); // termina el programa
        }
        a[tope]= x;
        tope= tope+1;
      }
      int popInt(int x) {
        if (tope==0) {
          println("pila vacia");
          exit();
        }
        tope= tope-1;
        return a[tope];
      }
      boolean isEmpty() {
        return tope==0;
      }
    }
En donde a es el arreglo y tope es el lugar en donde se almacenará el próximo entero que se coloque en la pila.

El problema de esta implementación es que si se llena el arreglo, hay que terminar el programa con un mensaje de error. Es decir la pila queda limitada a 100 elementos o el tamaño que se elija.

Una mejor implementación de una pila debería hacer crecer automáticamente el arreglo cuando se excede su tamaño. Por ejemplo se podría hacer crecer el tamaño en un factor 2. Ahora el problema es que si en algún momento se agrega un millón de elementos en la pila, la pila ocupará para siempre un millón enteros de la memoria del computador, incluso si sólo contiene unos cuantos enteros.

Listas enlazadas

Una lista enlazada es una estructura de datos que se visualiza como una cadena de eslabones que termina con una referencia nula. Cada eslabón se representa por medio de las siguientes variables de instancia:

    class Eslabon {
      ...
      Eslabon prox;
    }
Lo que caracteriza al eslabón como una estructura de datos recursiva es que entre las variables de instancia se encuentra una referencia a un objeto del mismo tipo.

Junto con poseer una referencia del próximo eslabón en la cadena, se colocan variables de instancia para almacenar datos concerniente al problema que se pretende resolver. Por ejemplo, para implementar la pila se puede colocar un entero en cada eslabón de la cadena: 

    class Eslabon {
      int x;
      Eslabon prox;
      Eslabon(int x, Eslabon prox) {
        this.x= x;
        this.prox= prox;
      }
    }
Típicamente los eslabones no tienen métodos asociados. Por conveniencia tienen un constructor.

Implementación de una pila usando listas enlazadas

La idea es formar una lista enlazada de eslabones que contienen los elementos de la pila. En la clase pila se almacena la referencia al eslabón que contiene el tope de la pila:

    class Pila extends Program {
      Eslabon primero= null;
      void push(int x) {
        primero= new Eslabon(x, primero);
      }
      void popInt() {
        int tope= primero.x;
        primero= primero.prox;
        return tope;
      }
    }