Programación en C++/Librería Estándar de Plantillas/Colas

C++ queue estándar

Una cola (queue) es una estructura en donde los elementos son insertados
en el inicio (front) de la misma, y retirados al final de la misma, debido a ello el comportamiento de una cola se
conoce como FIFO ( primero en entrar, primero en salir ). Ver Estructuras II

La Libreria estándar de plantillas soporta el uso de estructuras de cola a travez de la plantilla de clase queue, la cual posee el mecanismo de operación necesario para manejar operaciones de insertar (push), borrar(pop), entre otras. La clase queue posee únicamente seis métodos y dos constructores.

En seguida se presenta un ejemplo sumamente básico, el cual consiste en crear una cola para contener elementos de tipo char. Los caracteres se introducen en orden desde la 'A' hasta la 'Z' y, tal como tiene que ser, al recuperarlos se obtienen en el orden ingresados, o sea, desde la 'A' hasta la 'Z'.

En el programa se debe observar que, se usa el método push para agregar componentes a la lista; el método front regresa una referencia al elemento que se encuentra en el inicio de la cola y este es usado para leer y desplegar el carácter; y se emplea el método pop para eliminar el elemento que está en el frente de la cola.

// programa: cola01.cpp
// un simple ejemplo del uso de la plantilla queue

#include <cstdlib>
#include <iostream>
#include <queue>

using namespace std;

int main(int argc, char *argv[])
{
  queue<char> s;
  for (int i='A'; i <= 'Z'; i++)
    s.push(i);

  while (! s.empty() )
  {
    cout << s.front() << " " ;
    s.pop();
  }

  cout << endl;
  system("PAUSE");
  return EXIT_SUCCESS;
}

Colas con prioridad

Las colas prioritarias ( priority_queue ) de la STL de C++ son parecidas a las colas, con la diferencia de que en estas los elementos se ordenan mediante algun predicado.

Aunque se ha dicho que las colas prioritarias son parecidas a las colas, su comportamiento es diferente, ya que en una priority_queue no se cumple el algoritmo FIFO. Por ejemplo, en el siguiente programa se puede observar como se insertan de manera no ordenada elementos a la lista por medio de push, los cuales al ser recuperados se presentan en orden.

#include <cstdlib>
#include <iostream>
#include <queue>

using namespace std;

void cola01()
{
  priority_queue<int> p;

  // insertar elementos
  p.push(100);
  p.push(35);
  p.push(12);
  p.push(200);

  // mostrar elementos
  while (! p.empty() )
  {
    cout << p.top() << endl;
    p.pop();
  }
  cout << endl;
}

int main(int argc, char *argv[])
{
  cola01();
  system("PAUSE");
  return EXIT_SUCCESS;
}

La salida del programa anterior es:

y se debe al hecho de que por defecto la función o predicado que compara los elementos de la priority_queue es menor (less). Ahora bien, el predicado puede ser cambiado para que la comparación se mayor (greater) y para lograrlo se debe de usar una plantilla basada en la clase vector o en la clase deque. El programa que se mostrará en seguida es un ejemplo de como usar la clase deque para declarar una priority_queue.

#include <cstdlib>
#include <iostream>
#include <queue>

using namespace std;

void cola02()
{
  cout << "test 02" << endl;
  priority_queue<int, deque<int>, greater<int> > p;

  p.push(100);
  p.push(35);
  p.push(12);
  p.push(200);

  while (! p.empty() )
  {
    cout << p.top() << endl;
    p.pop();
  }
  cout << endl;
}

int main(int argc, char *argv[])
{
  cola02();
  system("PAUSE");
  return EXIT_SUCCESS;
}

La salida del programa anterior es:

Copia de contenedor

La magia de una priority_queue nos permite usar un constructor para obtener una copia ordenada de un contenedor ( vector, deque ). Así, en el siguiente ejemplo se muestra como crear una copia de un vector. El resultado es una priority_queue conteniendo en orden a todos los elementos del vector original. Veamos.

#include <cstdlib>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

// declaración de tipo
typedef priority_queue<string, vector<string>, greater<string> > STRPQUE;

int main(int argc, char *argv[])
{
  vector<string> v;

  v.push_back("pera");
  v.push_back("uva");
  v.push_back("manzana");
  v.push_back("banana");
  v.push_back("coco");

  vector<string>::iterator it = v.begin();
  cout << "Contenido del vector" << endl;
  while (it != v.end() )
     cout << "\t" << *it++ << endl;

  STRPQUE p( v.begin(), v.end() );

  cout << "\nContenido de la priority_queue" << endl;
  while (! p.empty() )
  {
    cout << "\t" << p.top() << endl;
    p.pop();
  }

  cout << endl;

  system("PAUSE");
  return EXIT_SUCCESS;
}

Si se compila y ejecuta el programa anterior, la salida en pantalla resultante será:

Contenido de la priority_queue
banana
coco
manzana
pera
uva

esto, a pesar de que el predicado ( greater<string> ), usado en la declaración de tipo, indica que los elementos se deben ordenar atendiendo al resultado de una comparación ( mayor que ). El hecho de tales resultados se debe a la naturaleza misma de la priority_queue, es decir, los elementos en esta están realmente ordenados de mayor a menor pero del inicio al fin, luego, como la orden top() regresa una referencia al último elemento de la cola, se obtiene asi un listado de los elementos ordenados de menor a mayor.

Métodos

Tabla de métodos: clase queue
Nombre	Descripción	queue	priority_queue
empty	cierto (true) si la cola está vacia	Si	Si
pop	borra el elemento del frente de la cola	Si	Si
push	agrega un elemento al frente de la cola	Si	Si
size	regresa el número de elementos en la cola	Si	Si
front	regresa una referencia al primer elemento en la cola	Si	No
back	regresa una referencia al último elemento en la cola	Si	No
top	regresa una referencia al primer elemento en la cola	No	Si

← Librería Estándar de Plantillas