Listas

Lista Doblemente Enlazada

En una lista doblemente enlazada, a diferencia de una lista simplemente enlazada, cada elemento tiene información de dónde se encuentra el elemento posterior y el elemento anterior. Esto permite leer la lista en ambas direcciones. Una aplicación típica es un procesador de textos, donde el acceso a cada línea individual se hace a través de una lista doblemente enlazada.

Es una colección de objetos, cada uno de los cuales contiene datos o una referencia a los datos, una referencia al elemento siguiente y una referencia al elemento anterior. Gráficamente se puede apreciar de la siguiente manera:

Para construir una lista de este tipo, primero tendremos que definir la clase de objetos que van a formar parte de la misma. Por ejemplo, cada elemento de la lista puede definirse como una estructura de datos de tres miembros:

Una referencia al elemento siguiente

Una referencia al elemento anterior

Una referencia al área de datos

Por ejemplo:

public class CElementoLse

  {
   public CElementoLse siguiente; 
   //referencia al siguiente elemento
   
   public CElementoLse anterior; 
   //referencia al elemento anterior
   
   double dato; 
   //referencia al dato
   
   public CElementoLse(){ }
  }
 

Una vez creada la clase objetos CElementoLse la asignación de memoria para un elemento se haría así:

static void Main(string[ ] args)
  {
  
   CElementoLse p= new CElementoLse; 
   /*referencia y asignación de memoria para un objeto de
   tipo CElementoLse*/
   
   //Este elemento no tiene sucesor
   p.siguiente=null;
   p.anterior=null;
   
   p=null;
   //Permite liberar la memoria ocupada por el elemento p
  }

En otras palabras el código CElementoLse p define una referencia p a un objeto de la clase CElementoLse. La sentencia p=new CElementoLse() crea o asigna memoria para un objeto de tipo CElementoLse, se genera una dirección de memoria que direcciona este nuevo objeto por medio de la variable p. Las sentencias p.siguiente=null y p.anterior=null, asigna al miembro siguiente del objeto referenciado por p el valor de null, indicando así que después de este elemento no hay otro, esto es, que el elemento es el último de la lista.

En el ejemplo anterior mostramos que tenemos una lista de un elemento:

Para añadir un elemento nuevo en la lista, se utilizan las siguientes instrucciones:

q=new CElementoLse();
//se crea un nuevo elemento

q.siguiente=p;
//se almacena la localización del elemento siguiente

p.anterior=q;
//se almacena la localización del elemento anterior

p=q;
// p hace referencia al principio de la lista

La sentencia q.siguiente=p hace que el sucesor del elemento creado sea el anteriormente creado. Ahora q.siguiente y p tienen el mismo valor, esto es, la misma dirección, por lo tanto, referencian al mismo elemento:

Por último, la sentencia p=q hace que la lista quede de nuevo referenciada por p, ahora p y q referencian al mismo elemento, esto es, al elemento que se acaba de crear.

Si se coloca la instrucción:

q=q.siguiente;

Es el atributo siguiente del objeto referenciado por q que contiene la dirección de memoria donde se localiza al siguiente elemento al referenciado por p. Si este valor se lo asignamos a q, entonces q referenciará al mismo elemento que referenciaba q.siguiente (el cual es q.siguiente=p). El resultado es que q referencia ahora al siguiente elemento:

Si volvemos a colocar la instrucción:

q=q.siguiente;

Se aprecia en la figura anterior que q.siguiente tiene el valor de null, este se le asigna a q. Entonces se puede entender que se ha llagado al final de la lista.

Pilas (Stack)

Una pila, torre o stack es una estructura de información en la cual los elementos se agregan o eliminan sólo por el tope. Se dice que una estructura de esta naturaleza tiene una disciplina de acceso, según la cual, el ultimo objeto de entrar será precisamente el primero en salir; esta disciplina es en ocasiones referida como UEPS, por sus siglas.

La clase Stack (pila) implementa la clásica colección LIFO (último en entrar primero en salir). Un elemento se mete en la pila por la parte superior (Push) y abandona la pila por la parte superior (Pop).Ejemplo:

Se tiene una pila de platos, los platos nuevos se añaden por arriba y también se quitan de arriba, con lo que el primer plato que se pone en la pila es el último que se quita.

Las pilas se pueden comparar con las pilas de charolas en una cafetería de autoservicio, o con los ramales de desvió de una línea ferroviaria (vease figura 3.1)

La forma común de implantar una pila en la memoria de una computadora es mediante un arreglo unidimensional con un apuntador que indique el top.

Este apuntador puede contener el índice del primer espacio disponible, o del último ocupado; la decisión no afecta en mayor grado la implantacion; pero es conveniente segurila rigurosamente en todas las pilas que utilice un programa para evitar errores; en lo siguiente, indicará el último lugar ocupado. Es importante también mantener una liga estrecha entre el arreglo y el apuntador.

La declaración de una Pila se hace de la siguiente forma:

using System;
using System.Collections;
Stack numbers = new Stack();

///para llenar la Pila
foreach( int number in new int[4]{9,3,7,2})
{
 numbers.Push(numer);
 Console.WriteLine(number + "se ha puesto en la pila");
}

///recorrer la Pila>
foreach(int number in numbers)
{
 Console.WriteLine (number);
}

///vaciar la Pila
while(numbers.Count != 0)
{
 int number = (int) numbers.Pop();
 Console.WriteLine (number + "se ha quitado de la Pila");
}

Colas (Queue)

La clase cola implementa la clásica colección FIFO (primero en entrar primero en salir). Un elemento se añade a la cola por detrás (Enqueue) y abandona la cola por delante (Dequeue). Al igual que en un ArrayList se tiene un control total de dónde viven los elementos dentro de una Queue.

Las colas tienen muchas aplicaciones en los sistemas computacionales. La mayoría de de las computadoras tienen sólo un procesador, por lo que sólo pueden atender una aplicación a la vez. Cada aplicación que requiere tiempo del procesador se coloca en una cola. La aplicación al frente de la cola es la siguiente que recibe atención. Cada aplicación avanza gradualmente al frente de la cola, a medida que las aplicaciones al frente reciben atención.

Las colas también se utilizan para dar soporte al uso de la cola de impresión. Por ejemplo, una sola impresora puede compartirse entre todos los usuarios de la red. Muchos usuarios pueden enviar trabajos a la impresora, incluso cuando ésta ya se encuentra ocupada. Estos trabajos de impresión se colocan en una cola hasta que la impresora esté disponible. Un programa conocido como spooler administra la cola para asegurarse que a medida que se complete cada trabajo de impresión se envíe el siguiente trabajo a la impresora.

La declaración de una cola se hace de la siguiente manera:

Using System;
Using System.Collections;
Queue numbers = new Queue();

//llenar cola
foreach (int number in new int[4]{9,3,7,2})
{
 numbers.Enqueue(number);
 Console.WriteLine (number + "ha entrado en la cola");
}

//recorrer la cola
foreach(int number in numbers)
{
 Console.WriteLine(number);
}

//vaciar la cola
while(numbers.Count !=0)
{
 int number= (int) numbers.Dequeue();
 Console.WriteLine (number + "ha dejado la cola");
}