Inicio > .NET Framework, C#, Tutorial > Todo lo que siempre quisiste saber sobre colecciones y tenías miedo de preguntar… Pilas y colas

Todo lo que siempre quisiste saber sobre colecciones y tenías miedo de preguntar… Pilas y colas


Cualquier programador que haya estudiado estructuras de datos conocerá las pilas y las colas. Junto con las listas enlazadas, los arrays y los diccionarios, forman el conjunto básico de estructuras de datos. El .NET Framework implementa clases para estas estructuras, y que son colecciones porque derivan de ICollection. Sin embargo, difieren en concepto e implementación de las listas y los diccionarios que hasta el momento hemos visto.

Definición

Una pila (stack, en inglés) es una estructura de datos a la que se le van agregando objetos y no cuenta con acceso aleatorio (es decir, a través de un indexador) sino secuencial. La secuencia en la que se obtienen los objetos almacenados es de la forma últimas entradas primeras salidas.

Considera un montón de monedas que queremos apilar. Conforme vamos colocando las monedas queda patente que la última que colocamos es la que está hasta arriba, es decir, la primera que vemos. Si añadimos una de un peso, una de dos, una de cinco y una de diez, y en este momento comenzamos a remover, las iríamos escogiendo en orden inverso a como fueron colocadas: primero la de diez pesos, luego la de cinco, la siguiente es la de dos y por último, la de un pesito. Este es precisamente el concepto de pila y más general, el concepto de últimas entradas y primeras salidas.

Nota también que al ir añadiendo monedas, una vez que coloco la moneda de dos pesos la de uno queda totalmente inaccesible, a menos que primero quite la de dos y ahora sí la de un peso. Esto ilustra una propiedad de las pilas: no cuentan con acceso aleatorio. Aunque de hecho en el ejemplo en cuestión sí podría obtener la moneda de uno, pero tendría que partir la pila en dos y remover de golpe las monedas que hay arriba, con el riesgo de que la pila puede caerse. Es decir, el proceso de hacerlo es costoso y la ventaja de tener la pila se pierde totalmente.

Una cola es muy similar a una pila. Tampoco cuentan con acceso aleatorio, sino secuencial. Esta secuencia sigue la forma de primeras entradas primeras salidas.

Un ejemplo que encaja a la perfección es la fila de personas frente a una taquilla de boletos en un estadio de Sudáfrica para el encuentro entre México y Francia (el cual, debo añadir orgullosamente, ganamos esta tarde por marcador de dos a cero). Conforme la gente va llegando a la fila, en ese orden se le vende el boleto de entrada: el vendedor atiende al primero que llegó, luego al que está atrás, etcétera. Un intento por saltar este orden terminaría en un grupo numeroso de aficionados enojados.

Estos conceptos son sencillos y sin embargo muy útiles, y por ello el .NET Framework les dedica especial atención al proveer dos clases en el espacio de nombres System.Collections: Stack para las pilas y Queue para las colas.

La clase Stack

Comencemos por la clase Stack. En primera instancia, esta clase implementa las interfaces IEnumerable, que nos permite enumerar los elementos de la pila, e ICollection, que de buenas a primeras nos permite contar el número de elementos, copiar el contenido a un array y tener un acceso sincronizado a los elementos.

Stack cuenta con tres constructores: uno por defecto, uno que toma como parámetro un ICollection y que agrega los elementos de dicha colección a la pila, y uno que toma un número entero indicando la capacidad inicial (recuerda que las colecciones crecen al paso del tiempo, y cada vez que crecen tienen que aumentar su tamaño en memoria; por ende si sabemos anticipadamente cuántos elementos tendrá la colección podemos especificar la capacidad para no tener que estar haciendo redimensionamiento, obteniendo un mejor rendimiento del procesador).

Posteriormente contamos con algunos métodos que nos son familiares. Clear elimina todo el contenido de la pila, Contains nos indica si la colección contiene un objeto determinado, CopyTo copia el contenido de la pila aun array y ToArray regresa un array con los elementos que contiene la pila.

Pero quizás los métodos más importantes sean Push y Pop. Push es muy similar al Add de las listas: nos permite añadir un elemento a la pila, mientras que Pop regresa el último elemento añadido (recuerda: últimas entradas primeras salidas) y lo elimina de la colección. El siguiente ejemplo crea un objeto Stack, le añade algunos elementos usando Push y luego los obtiene usando Pop.

Stack stack = new Stack(10);
stack.Push("Carlos Salcido");
stack.Push("Rafael Márquez");
stack.Push("Javier Hernández");
stack.Push("Giovani Dos Santos");
stack.Push("Carlos Vela");

while (stack.Count > 0)
{
    string mexicanPlayer = stack.Pop() as string;
    Console.WriteLine(mexicanPlayer);
}

Console.ReadKey(true);

Al ejecutar este programa obtenemos la siguiente salida en la consola.

Carlos Vela
Giovani Dos Santos
Javier Hernández
Rafael Márquez
Carlos Salcido

Como era de esperarse, la salida de los nombres de algunos jugadores de la Selección Mexicana de Fútbol se da en el orden inverso al que fueron añadidos: últimas entradas primeras salidas.

Ahora bien, al hacer uso de Pop obtenemos el elemento pero también lo removemos de la colección. Esto puede convertirse en un lío cuando solo queramos leer el siguiente elemento, sin removerlo de la colección. Para solventar este problema, contamos con el método Peek. Este método devuelve el mismo elemento que devolvería Pop, pero sin eliminarlo de la colección.

Stack stack = new Stack(10);
stack.Push("Carlos Salcido");
stack.Push("Rafael Márquez");
stack.Push("Javier Hernández");
stack.Push("Giovani Dos Santos");
stack.Push("Carlos Vela");

string mexicanPlayer = stack.Peek() as string;
Console.WriteLine("Jugador: {0}", mexicanPlayer);
Console.WriteLine();

foreach (string player in stack)
    Console.WriteLine(player);

En este ejemplo, usamos Peek para obtener el siguiente jugador de la pila (es decir, el último) que en este caso será Carlos Vela. Luego hacemos un foreach, que imprime a los cinco jugadores, demostrando cómo Peek no elimina el elemento de la colección.

La clase Queue

La clase Queue representa una cola, y es muy similar a la clase Stack. También implementa IEnumerable e ICollection y tiene prácticamente los mismos métodos que Stack. Sin embargo, en lugar de Push y Pop, esta clase cuenta con los métodos Enqueue y Dequeue para añadir un elemento a la fila y para obtener y remover el primer elemento de la cola (recuerda: primeras entradas, primeras salidas. Por lo demás, las clases son prácticamente idénticas.

Queue queue = new Queue(5);
queue.Enqueue("Carlos Salcido");
queue.Enqueue("Rafael Márquez");
queue.Enqueue("Javier Hernández");
queue.Enqueue("Giovani Dos Santos");
queue.Enqueue("Carlos Vela");

while (queue.Count > 0)
{
    string mexicanPlayer = queue.Dequeue() as string;
    Console.WriteLine(mexicanPlayer);
}

Como cabría esperar, este código imprime los nombres de los jugadores en el orden en el que fueron añadidos a la colección.

Carlos Salcido
Rafael Márquez
Javier Hernández
Giovani Dos Santos
Carlos Vela

Un método extra que tiene Queue pero no tiene Stack es el método TrimToSize. Este método redimensiona el bloque de memoria interna para que su tamaño sea equivalente al número de elementos de la colección. Esto es útil en caso de que tengamos una cola con muchos elementos, digamos mil, y removemos una gran cantidad, digamos quinientos. Aunque removamos los elementos, la cola seguirá almacenando suficiente memoria para mil elementos, convirtiéndose en un desperdicio de memoria. Si sabemos que por el momento la cola no aumentará de tamaño, sería bueno invocar a TrimToSize para liberar la memoria reservada.

Y bueno, eso es todo con respecto a estas clases. Realmente son muy sencillas y su manejo no debería darnos problemas.

Escenarios de uso

Quizás no te quede claro bajo qué circunstancias podríamos emplear alguna de estas clases. Pues bien, la parte final de esta entrada te mostrará algunos escenarios de uso para las pilas y colas.

Mensajes

Quizás una de las aplicaciones de las colas más comunes son los mensajes. Considera este escenario: tienes un método que realiza ciertas operaciones y cada operación puede lanzar un mensaje que deberá ser procesado por otra entidad en el orden en el que fueron creados.

El sistema gráfico de Windows es un ejemplo de ello. Cada vez que se genera algún evento en la interfaz gráfica (un clic del ratón o una tecla pulsada) se genera un Windows Message (WM). Cada WM se almacena en una cola, y hasta que el sistema operativo le pasa el control a la aplicación, ésta deberá responder uno a uno a los mensajes enviados, conforme fueron generados. Esta forma de trabajo se hace en forma paralela, así que múltiples hilos entran en juego.

El siguiente código emula un sistema de mensajes donde un hilo se encarga de generar dichos mensajes mientras que el hilo principal está a la espera de éstos. Cuando encuentra un mensaje, lo imprime en la consola, y si no encuentra nada entonces se duerme algunas décimas de segundo antes de volver a revisar la cola por si hay más mensajes disponibles.

using System;
using System.Collections;
using System.Threading;

namespace Fermasmas.Wordpress.Com
{
    class Program
    {
        // este es nuestra cola de mensajes. 
        static volatile Queue _messages;

        static void Main(string[] args)
        {
            _messages = new Queue();

            // inicializamos el generador de mensajes en un hilo aparte.
            Thread thread = new Thread(new ThreadStart(MessagePump));
            thread.Start();

            // revisamos la cola de mensajes mientras el hilo trabajador esté 
            // activo o existan mensajes por procesar. 
            while (thread.IsAlive || _messages.Count > 0)
            {
                if (_messages.Count > 0)
                {
                    // hay que bloquear la cola de mensajes por si el otro 
                    // hilo intenta añadir más. de no hacer esto podríamos 
                    // tener problemas de sincronización. 
                    lock (_messages.SyncRoot)
                    {
                        // removemos el mensaje y lo imprimimos en la consola.
                        string message = _messages.Dequeue() as string;
                        Console.WriteLine(message);
                    }
                }
                else
                {
                    // no hay mensajes todavía, dormimos el hilo principal
                    // antes de continuar. 
                    Console.WriteLine("Durmiendo...");
                    Thread.Sleep(500);
                }
            }

            // el hilo trabajador terminó de hacer su proceso y ya no hay más
            // mensajes por mostrar, así que es hora de terminar la 
            // aplicacón. 
            Console.WriteLine("Terminado...");
            Console.ReadKey(true);
        }

        static void MessagePump()
        {
            for (int i = 0; i < 10; i++)
            {
                Thread.Sleep(300);

                string message = string.Format("Mensaje {0}", i + 1);
                lock (_messages.SyncRoot)
                {
                    _messages.Enqueue(message);
                }
                
            }
        }
    }
}

La salida de este programa es similar a la siguiente.

Durmiendo...
Mensaje 1
Durmiendo...
Mensaje 2
Mensaje 3
Durmiendo...
Mensaje 4
Durmiendo...
Mensaje 5
Mensaje 6
Durmiendo...
Mensaje 7
Mensaje 8
Durmiendo...
Mensaje 9
Durmiendo...
Mensaje 10
Terminado...

Rastreo de actividades

Quizás haz notado que las excepciones en .NET cuentan con la propiedad StackTrace. Esta propiedad devuelve una cadena de texto que contiene los nombres de las funciones que se fueron ejecutando. Esto es de invaluable ayuda al depurar el programa ya que podemos darnos una idea sobre cómo se ejecutó el programa.

Pues bien, este rastreo se puede implementar utilizando una pila. Al iniciar un método, haces un Push con el nombre del método, y al terminarlo haces un Pop. De tal suerte, si surge una excepción, la pila sabrá exactamente en qué método te encuentras. No en vano se le llama StackTrace (o rastreo de pila).

El siguiente programa muestra una serie de funciones que se llaman entre sí. Al inicio, el programa le pide al usuario que escriba el nombre de la función que lanzará una excepción. Así, si escribo “Foo7” la función Foo7 lanzará una excepción cuando sea invocada. Dado que las funciones Foo1 a Foo7 se llaman entre sí, podremos ver cómo se hace el rastreo al guardar información sobre el método que se llama. Cuando se lanza la excepción, se muestra el rastreo que hacemos a mano y se compara contra el rastreo que hace la clase Exception.

using System;
using System.Collections;

namespace Fermasmas.Wordpress.Com
{
  class Program
  {
    static Stack _log;
    static string _failure;

    static void Main(string[] args)
    {
      _log = new Stack();

      Console.WriteLine("¿En qué función fallará?");
      _failure = Console.ReadLine();
      Console.Clear();

      try
      {
        Console.WriteLine("Iniciando proceso...");
        Foo1();
        Console.WriteLine("Terminando proceso...");
      }
      catch (Exception ex)
      {
        Console.WriteLine("Hubo un error... rastreo habilitado: ");
        while (_log.Count > 0)
        {
          Console.WriteLine("en {0}", _log.Pop());
        }
        Console.WriteLine();

        Console.WriteLine("Rastreo de Exception.StackTrace: ");
        Console.WriteLine(ex.StackTrace);
      }

      Console.ReadKey(true);
    }

    static void DoWork()
    {
      string current = _log.Peek() as string;
      if (current.IndexOf(_failure) >= 0)
      {
        _log.Push("DoWork... ");
        throw new Exception();
      }
    }

    static void Foo1()
    {
      _log.Push("Estamos en Foo1");

      DoWork();
      Foo2();
      Foo3();
      Foo4();

      _log.Pop();
    }

    static void Foo2()
    {
      _log.Push("Estamos en Foo2");
      DoWork();
      _log.Pop();
    }

    static void Foo3()
    {
      _log.Push("Estamos en Foo3");
      DoWork();
      Foo5();
      Foo6();
      _log.Pop();
    }

    static void Foo4()
    {
      _log.Push("Estamos en Foo4");
      DoWork();
      Foo5();
      _log.Pop();
    }

    static void Foo5()
    {
      _log.Push("Estamos en Foo5");
      DoWork();
      _log.Pop();
    }

    static void Foo6()
    {
      _log.Push("Estamos en Foo6");
      DoWork();
      Foo7();
      _log.Pop();
    }

    static void Foo7()
    {
      _log.Push("Estamos en Foo7");
      DoWork();
      _log.Pop();
    }
  }
}

Al ejecutar este programa, y decirle que quiero una excepción en Foo5, esta es la salida. Al comparar el rastreo manual que hacemos junto con el que hace Exception.StackTrace, veremos que son prácticamente idénticos.

Iniciando proceso...
Hubo un error... rastreo habilitado:
en DoWork...
en Estamos en Foo6
en Estamos en Foo3
en Estamos en Foo1

Rastreo de Exception.StackTrace:
   at Fermasmas.Wordpress.Com.Program.DoWork() in C:\[...]\Program.cs:line 47
   at Fermasmas.Wordpress.Com.Program.Foo6() in C:\[...]\Program.cs:line 97
   at Fermasmas.Wordpress.Com.Program.Foo3() in C:\[...]\Program.cs:line 75
   at Fermasmas.Wordpress.Com.Program.Foo1() in C:\[...]\Program.cs:line 57
   at Fermasmas.Wordpress.Com.Program.Main(String[] args) in C:\[...]\Program.cs:line 22

 

Deshacer acciones

Otro de los ejemplos clásicos sobre aplicaciones de pilas es el hacer y deshacer acciones. Editores de texto como Word o el Visual Studio cuentan con esta funcionalidad para deshacer el texto previamente escrito. Esta funcionalidad se puede fácilmente alcanzar con una pila. Conforme ingresamos texto, lo agregamos a la pila, y al hacer el "undo” tomamos el último elemento escrito (es decir, hacemos un Pop) y lo eliminamos del editor de texto. Hacer un “redo” es muy similar: lo que sacamos del “undo” lo metemos en otra pila y listo.

El siguiente programa es un pequeño editor de texto estilo vim y emacs, muy básico, que soporta la funcionalidad de hacer y deshacer. Utiliza :q para salir, :n para añadir un salto de línea, :c para borrar todo el contenido, :u para deshacer y :r para rehacer. Todo lo demás será agregado al texto y se mostrará en la consola.

using System;
using System.Text;
using System.Collections;

namespace Fermasmas.Wordpress.Com
{
  class Program
  {
    static Stack _undo;
    static Stack _redo;
    static string _text;
    
    static void Main(string[] args)
    {
      _undo = new Stack();
      _redo = new Stack();
      _text = string.Empty;

      string query = string.Empty;

      do
      {
        Console.Clear();
        Console.Write(_text);

        Console.WriteLine("\n\n\n\n");
        Console.WriteLine("Ingrese texto o :q para terminar.");
        Console.Write("> ");

        query = Console.ReadLine();
        if (query == ":n")
        {
          _undo.Push("\n");
          _redo.Clear();
          _text += "\n";
        }
        else if (query == ":c")
        {
          _undo.Clear();
          _redo.Clear();
          _text = string.Empty;
        }
        else if (query == ":u")
        {
          if (_undo.Count > 0)
          {
            string undo = _undo.Pop() as string;
            _redo.Push(undo);
            int index = _text.LastIndexOf(undo);
            _text = _text.Remove(index, undo.Length);
          }
        }
        else if (query == ":r")
        {
          if (_redo.Count > 0)
          {
            string redo = _redo.Pop() as string;
            _undo.Push(redo);
            _text += redo;
          }
        }
        else if (query == ":?")
        {
          Console.Clear();
          Console.WriteLine("Comandos");
          Console.WriteLine(":n - salto de línea");
          Console.WriteLine(":c - borrar");
          Console.WriteLine(":u - deshacer última acción");
          Console.WriteLine(":r - rehacer última acción deshecha");
          Console.WriteLine(":q - quitar");
          Console.WriteLine("Presione una tecla para continuar...");
          Console.ReadKey(true);
        }
        else if (query != ":q")
        {
          _undo.Push(query);
          _redo.Clear();
          _text += query;
        }
      }
      while (query != ":q");
    }
  }
}

Conclusiones

Bueno, pues eso es todo por ahora. Hay muchos más ejemplos, pero creo (espero) que estos son ilustrativos. Por supuesto, puedes reemplazar una pila y una cola con arrays o listas, pero bueno, tendrías que hacer las validaciones a manita.

Utiliza sabiamente las pilas y las colas, ya que el abusar de ellas también puede acarrear problemas de escalamiento o rendimiento de recursos.

Y ahora sí, a festejar que México le ganó a Francia…

Anuncios
Categorías:.NET Framework, C#, Tutorial Etiquetas: ,

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s