Estructura de Datos : Pilas Enlazadas

Definiciones

La representación de pilas secuenciales es eficiente si se procesara solamente una pila. La representación de pilas enlazadas es la adecuada cuando se desean representar múltiples pilas.

Las ventajas de la representación enlazada de pilas son :

No hay necesidad de reubicar información al insertar nuevos elementos o eliminar los existentes.
El programa corre hasta que haya nodos libres en el storage pool.
En el mismo storage pool se pueden representar pilas y cualquier otra estructura de datos con el mismo nodo.
Tiempo de computación menor que pilas secuenciales.
Esta estructura de datos se conoce como Linked Stack en la literatura inglesa.

Representaciones

Representación Gráfica ( Graphic Representation )

      top
       .
       .             DATA   LINK
       .           +-------------+      <------ add
       ...........>|      |   *  |
                   +----------|--+      ------> delete
                              V
                   +-------------+
                   |      |   *  |
                   +----------|--+
                              V
                   +-------------+                      +---+
                   |      |   *  |                    P |   | Variable con el tope de la pila
                   +----------|--+                      +---+
                              V
                              .
                              .
                              .
                              .
                              |
                              V
                   +-------------+
                   |      |   0  |
                   +-------------+

Observar que las operaciones de agregar o eliminar un elemento a la pila, siempre se hacen sobre el nodo que está al tope y es referenciado por la variable que representa la pila.

Representación Conjunto ( Pool Representation )

Pool de pilas

P(i) = Tope de la pila i, para 1 =< i =< n

Condiciones iniciales

P(i) = 0, para 1 =< i =< n

Condiciones de borde

P(i) = 0, si y solo si la pila está vacia

     +---+         +---------+    +---------+    +---------+                   +---------+
  P1 |   |........>|     | *.|...>|     | *.|...>|     | *.|...> ......... ...>|     | 0 |
     +---+         +---------+    +---------+    +---------+                   +---------+
     +---+         +---------+                   +---------+
  P2 |   |........>|     | *.|...> ......... ...>|     | 0 |
     +---+         +---------+                   +---------+
     +---+
  P3 | 0 |
     +---+
     +---+         +---------+    +---------+                   +---------+
  P4 |   |........>|     | *.|...>|     | *.|...> ......... ...>|     | 0 |
     +---+         +---------+    +---------+                   +---------+
       .
       .
       .
       .
       .
     +---+         +---------+    +---------+    +---------+    +---------+                   +---------+
  Pn |   |........>|     | *.|...>|     | *.|...>|     | *.|...>|     | *.|...> ......... ...>|     | 0 |
     +---+         +---------+    +---------+    +---------+    +---------+                   +---------+

Funciones

Inserciones ( Inserts )

Agrega el elemento o contenido C en el tope del stack i, siendo i un stack del pool de stacks. Las variables i e C son de entrada.

procedure ADDS(i,C)

call GETNODE(Y)
DATA(Y) <---- C
LINK(Y) <---- P(i)
P(i) <---- Y

end ADDS

Eliminaciones ( Deletes )

Elimina el elemento al tope del stack i y los datos del elemento eliminado se dejan en Y. La variable i es de entrada. La variable Y es de salida.

procedure DELETES(i,Y)

if P(i) = 0
- then
  - call STACK_EMPTY
- else
  - X <---- P(i)
  - Y <---- DATA(X)
  - P(i) <---- LINK(X)
  - call RETNODE(X)

end DELETES