Ejercicio usando Colas en C++

[xKuZz]

Por curiosidad, ¿en qué asignatura te han pedido que hagas esto?.

Vamos al lío, obviamente tienes dos opciones, que más que depender de ti dependerán probablemente del profesor.

1) Utilizo priority_queue de la STL, eso implica que al menos debes comprender como funciona cada uno de sus métodos y saber crear y usar un functor.

2) Utilizo mi propia estructura. Eso implica plantearse las siguiente preguntas.

¿Para mi problema necesito usar memoria dinámica?
En caso afirmativo, o creo mi propia estructura de datos o utilizo una se la STL que ya conozca. En caso negativo puedo utilizar un simple array C.

¿En qué consiste una cola con prioridad?
Una cola con prioridad es aquella en la que debe salir antes el elemento que tenga asignada la mayor prioridad.

¿En qué orden almaceno los elementos?
No tienen por qué estar ordenados, es una cuestión de diseño. Puedes tenerlos organizados en memoria al insertarlos en la estructura o tenerlos desordenados y buscar el que más prioridad tiene al sacarlos.

¿Cómo obtengo la prioridad de un elemento?
Para ello crearás una función que se encargue de la relación de orden prioridad para el problema. Por ejemplo, en el caso dado, crearás una función que devolverá true si cumple los requisitos dados para que el primer argumento sea menor que el segundo, es decir que o bien el primer argumento tenga más dígitos que el segundo o en caso de que tengan los mismos devolverá true si el primero es menor que el segundo.

Por tanto, para cumplir los requisitos dados, tus estructura debería contar AL MENOS con las siguientes funciones para ser una cola con prioridad.

Elementos ordenados en memoria (al insertar)
1- Función de prioridad
Dados dos valores a y b, ambos enteros, devolverá si prioridad(a) < prioridad(b).

2- Función de inserción en cualquier posición de la estructura
Esta función implica que no debe existir ningún problema para introducir un dato en cualquier lugar de la estructura.
a) Busco la posición en la que debo introducir el dato según la PRIORIDAD. Mirar algoritmos de búsqueda binaria (preferible porque es más eficiente) y búsqueda secuencial (más fácil pero menos eficiente) en caso de no conocerlos.
b) Una vez encuentro la posición inserto el dato.

3- Función de devolución/borrado al principio o final
Dependiendo de si al insertar de como hayas ordenado implicará
a) Si ordenaste de menor a mayor prioridad eliminarás siempre el último elemento.
b) Si lo hiciste de mayor a menor eliminarás siempre el primero.
En este método puedes devolver el valor de la posición, o crear otro método aparte
para devolver el dato antes de borrarlo.

Elementos no ordenados en memoria
1- Función de prioridad (Mirar arriba)

2- Función de inserción
En este caso te basta con poder insertar en una posición como la del principio o la del final, no tiene porque ser una posición del centro.

3- Función de devolución/borrado en cualquier posición
Deberás recorrer secuencialmente toda tu estructura con el fin de encontrar el máximo para la relación de prioridad. Ese elemento será el que borraremos, igual que antes puedes devolverlo en una función o en esta misma.
Nota: En caso de que separes los métodos de devolver el dato y borrarlo, recuerda que debes de devolverlo antes de borrarlo, que aunque suene obvio, a mucha gente se le pasa por alto.

Aunque sea mucho texto, no te asustes, es algo que no es difícil pero he intentado dejarte los conceptos lo más claros que he podido. Saludos.