45 - Estructuras dinámicas: Listas tipo Cola


Una lista se comporta como una cola si las inserciones las hacemos al final y las extracciones las hacemos por el frente de la lista. También se las llama listas FIFO (First In First Out - primero en entrar primero en salir)

Confeccionaremos un programa que permita administrar una lista tipo cola. Desarrollaremos los métodos de Insertar, Extraer, Vacia e Imprimir.

Programa:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ListasTipoCola1
{
    class Cola
    {
        class Nodo 
        {
            public int info;
            public Nodo sig;
        }
    
        private Nodo raiz,fondo;
    
        public Cola() 
        {
            raiz=null;
            fondo=null;
        }
    
        public bool Vacia ()
        {
            if (raiz == null)
                return true;
            else
                return false;
        }

        public void Insertar (int info)
        {
            Nodo nuevo;
            nuevo = new Nodo ();
            nuevo.info = info;
            nuevo.sig = null;
            if (Vacia ()) 
            {
                raiz = nuevo;
                fondo = nuevo;
            }
            else
            {
                fondo.sig = nuevo;
                fondo = nuevo;
            }
        }

        public int Extraer ()
        {
            if (!Vacia ())
            {
                int informacion = raiz.info;
                if (raiz == fondo)
                {
                    raiz = null;
                    fondo = null;
                }
                else
                {
                    raiz = raiz.sig;
                }
                return informacion;
            }
            else
                return int.MaxValue;
        }

        public void Imprimir() 
        {
            Nodo reco=raiz;
            Console.WriteLine("Listado de todos los elementos de la cola.");
            while (reco!=null) 
            {
                Console.Write(reco.info+"-");
                reco=reco.sig;
            }
            Console.WriteLine();
        }
        
        static void Main(string[] args)
        {
            Cola cola1=new Cola();
            cola1.Insertar(5);
            cola1.Insertar(10);
            cola1.Insertar(50);
            cola1.Imprimir();
            Console.WriteLine("Extraemos uno de la cola:"+cola1.Extraer());
            cola1.Imprimir();
            Console.ReadKey();
        }
    }
}

La declaración del nodo es igual a la clase Pila. Luego definimos dos punteros externos:

        class Nodo 
        {
            public int info;
            public Nodo sig;
        }
    
        private Nodo raiz,fondo;

raíz apunta al principio de la lista y fondo al final de la lista. Utilizar dos punteros tiene como ventaja que cada vez que tengamos que insertar un nodo al final de la lista no tengamos que recorrerla. Por supuesto que es perfectamente válido implementar una cola con un único puntero externo a la lista.

En el constructor inicializamos a los dos punteros en null (Realmente esto es opcional ya que los atributos de una clase en C# se inicializan automáticamente con null):

        public Cola() 
        {
            raiz=null;
            fondo=null;
        }

El método vacía retorna true si la lista no tiene nodos y false en caso contrario:

        public bool Vacia ()
        {
            if (raiz == null)
                return true;
            else
                return false;
        }

En la inserción luego de crear el nodo tenemos dos posibilidades: que la cola esté vacía, en cuyo caso los dos punteros externos a la lista deben apuntar al nodo creado, o que haya nodos en la lista.

            Nodo nuevo;
            nuevo = new Nodo ();
            nuevo.info = info;
            nuevo.sig = null;
            if (Vacia ()) 
            {
                raiz = nuevo;
                fondo = nuevo;
            }
            else
            {
                fondo.sig = nuevo;
                fondo = nuevo;
            }

Recordemos que definimos un puntero llamado nuevo, luego creamos el nodo con el operador new y cargamos los dos campos, el de información con lo que llega en el parámetro y el puntero con null ya que se insertará al final de la lista, es decir no hay otro después de este.

Si la lista está vacía:

Cola

En caso de no estar vacía:

Cola

Debemos enlazar el puntero sig del último nodo con el nodo recién creado:

                fondo.sig = nuevo;
Cola

Y por último el puntero externo fondo debe apuntar al nodo apuntado por nuevo:

                fondo = nuevo;
Cola

Con esto ya tenemos correctamente enlazados los nodos en la lista tipo cola. Recordar que el puntero nuevo desaparece cuando se sale del método insertar, pero el nodo creado no se pierde porque queda enlazado en la lista.

El funcionamiento del método extraer es similar al de la pila:

        public int Extraer ()
        {
            if (!Vacia ())
            {
                int informacion = raiz.info;
                if (raiz == fondo)
                {
                    raiz = null;
                    fondo = null;
                }
                else
                {
                    raiz = raiz.sig;
                }
                return informacion;
            }
            else
                return int.MaxValue;
        }

Si la lista no está vacía guardamos en una variable local la información del primer nodo:

                int informacion = raiz.info;

Para saber si hay un solo nodo verificamos si los dos punteros raiz y fondo apuntan a la misma dirección de memoria:

                if (raiz == fondo)
Cola

Luego hacemos:

                    raiz = null;
                    fondo = null;
Cola

En caso de haber 2 o más nodos debemos avanzar el puntero raiz al siguiente nodo:

Cola
                    raiz = raiz.sig;
Cola

Ya tenemos la lista correctamente enlazada (raiz apunta al primer nodo y fondo continúa apuntando al último nodo)


Retornar