TEMA 2: Tipos Abstractos de Datos

Listas

• Matemáticamente una lista es una secuencia de cero o más elementos.

• Si tiene $0$ elementos se llama lista vacía.
• $a_1$ es el primer elemento (cabeza ) y $a_n$ el último (cola ).
• Decimos que $a_i$ precede a $a_{i+1}$ y $a_i$ sucede a $a_{i-1}$ y que $a_i$ ocupa la posición i-ésima.

Listas. Operaciones básicas

• Delete (L, i) : Elimina el elemento de la posición iésima. Si se ha podido hacer devuelve el valor booleano true y si no false. Implica reorganizar los elementos de la lista.

• Length (L) : Devuelve $|L|$, la longitud de L.
• Reset (L) : Hace que la posición actual sea igual la cabeza de la lista y devuelve el valor 1, si la lista está vacía devuelve 0.

Listas. Operaciones básicas

• Current (L) : Devuelve la posición actual en la lista L.
• Next (L) : Incrementa y devuelve la posición actual en la lista L.

Listas. Implementación

• Cada TAD será una clase, p.e.:

  typedef char Element;           // Hasta que veamos genericidad
                                  // usaremos estos typedef.
  typedef int  Position;
  
  class List {
    public:
      void insert (Element x, Position i); // Dónde está el primer
                                           // parámetro 'L'?
      ...
  };
  
  List l;
  l.insert ('a', 1);
  

Listas. Implementación

• Diversas opciones para la representación interna.
• Puede ser un vector (array ).

• Puede ser una serie de elementos en la cual cada uno sabe sólo cuál es su siguiente (simplemente enlazada ):

  

  Figura 1: Lista simplemente enlazada.

Listas. Implementación

• O también su anterior (doblemente enlazada ):

  

  Figura 2: Lista doblemente enlazada.

Pilas. Operaciones básicas

• Pop (S) : Elimina el último dato insertado en S (cabeza). En la práctica lo devuelve antes de eliminarlo. Aplicada sobre una pila vacía lanzará una excepción de tipo EmptyStackException.
• Empty (S) : Devuelve true si la pila no tiene elementos.

Ejemplo, apilamos A, B, C y desapilamos.

Pilas. Implementación

List* myList = new Stack();
myList->insert(0, value);  // ¿Permitido? No debería en una pila.

Pilas. Implementación

• ¿Y esta?:

  #include "list.h"
  
  class Stack : private List {
  public:
    void push (Element x);
  ...
  };
  

Pilas. Implementación

• ¿O esta otra?:

  #include "list.h"
  
  class Stack {
  public:
    void push (Element x);
  ...
  private:
    List _l;
  };
  

Colas. Operaciones básicas

• Dequeue (Q) : Elimina el dato que más tiempo lleva en Q (cabeza). Aplicada sobre una cola vacía lanzará una excepción de tipo EmptyQueueException.

• Empty (Q) : Devuelve true si la cola no tiene elementos.

  Por completitud, al dato que menos tiempo lleva en la cola se le llama cola (del inglés tail ).

Colas. Operaciones básicas

Ejemplo, encolamos A, B, C y desencolamos.

Colas. Implementación

• ¿Y esta?:

  #include "list.h"
  
  class Queue : private List {    // Herencia privada
  public:
    void enqueue (Element x);
  ...
  };
  

Colas. Implementación

• ¿O esta otra?:

  #include "list.h"
  
  class Queue {
  public:
    void enqueue (Element x);
  ...
  private:
    List _l;                      // Composición
  };