1. No category

Programación IV. Guía No. 13
1
Facultad:
Ingeniería
Escuela:
Computación
Asignatura: Programación IV
Tema: Colas de Prioridad.
Objetivos Específicos
•
Definir brevemente el concepto de cola.
•
Implementar la estructura de datos cola en C #.
•
Implementar la estructura de datos cola de prioridad en C #.
Materiales y Equipo
• Guía Número 13.
• Computadora con programa Microsoft Visual C#.
Introducción Teórica
Cola.
Una cola es una estructura de datos, caracterizada por ser una secuencia de elementos en la
que la operación de inserción se realiza por un extremo y la operación de extracción por el otro.
También se le llama estructura FIFO (del inglés First In First Out), debido a que el primer
elemento en entrar será también el primero en salir.
Las operaciones básicas de una cola son las siguientes.
1. Crear cola vacía.
2. Encolar: Insertar elemento al final de la cola.
3. Frente: Ver el primer elemento de la cola.
4. Desencolar: Sacar y devolver el primer elemento de la cola.
2
Programación IV. Guía No. 13
Además se pueden agregar otras operaciones las cuales serían un conjunto de las operaciones
anteriores:
 Verificar si la cola está vacía.
 Mostrar cola.
Colas de prioridad.
Las colas de prioridad es una extensión de la estructura de datos Cola. Se basan en el orden de
salida de sus elementos: en el orden de llegada y orden de prioridad; así un elemento que
ingresa a la cola se posicionará al final del segmento de elementos de su misma prioridad.
Las colas de prioridad permiten alterar el orden de salida de los elementos de una cola:
 no es necesario seguir un orden FIFO.
 el orden se puede basar en una función de comparación.
Las operaciones de las colas de prioridad son las mismas que las de las colas con un
comportamiento diferente.
Una cola de prioridad es una cola a cuyos elementos se les ha asignado una prioridad, de
forma que el orden en que los elementos son procesados sigue las siguientes reglas:

El elemento con mayor prioridad es procesado primero.
 Dos elementos con la misma prioridad son procesados según el orden en que fueron
introducidos en la cola.
Así, si tenemos que la prioridad más alta es 0, y la más baja es 3, la estructura se vería así:
La cola de prioridad cuenta con las mismas rutinas que la estructura de cola genérica, con la
diferencia que al encolar elementos y desencolar elementos se debe de tomar en cuenta su
prioridad para su posicionamiento.
Algunas aplicaciones de las colas de prioridad.
Programación IV. Guía No. 13
3
Gestión de procesos en un sistema operativo. Los procesos no se ejecutan uno tras otro en
base a su orden de llegada. Algunos procesos deben tener prioridad (por su mayor importancia,
por su menor duración, etc.) sobre otros.
Implementación de algoritmos voraces, los cuales proporcionan soluciones globales a
problemas basándose en decisiones tomadas sólo con información local. La determinación de
la mejor opción local suele basarse en una cola de prioridad.
Algunos algoritmos sobre grafos, como la obtención de caminos o árboles de expansión de
coste mínimo, son ejemplos representativos de algoritmos voraces basados en colas de
prioridad.
Procedimiento
Ejemplo 1. Iimplementaremos una cola genérica en C#:
1. Crear un proyecto de consola y nombrarlo “colas”.
2. Agregar las clases “nodo” y “cola” al namespace “colas”
Clase Nodo:
class Nodo
{
public int info;
public nodo sgte;
}
Clase Cola:
class Cola
{
public Nodo primero;
public Nodo ultimo;
public Cola ( )
{
primero = null;
ultimo = null;
}
public void encolar (int valor)
{
Nodo aux = new Nodo ( );
aux.info = valor;
if (primero == null)
{
primero = aux;
ultimo = aux;
aux.sgte = null;
}
//si la cola está vacía
4
Programación IV. Guía No. 13
else
{
//si la cola no está vacía
ultimo.sgte = aux;
aux.sgte = null;
ultimo = aux;
}
}
public void desencolar ( )
{
if (primero == null)
Console.WriteLine ("Cola vacia");
else
{
primero = primero.sgte;
}
}
public int desencolarValor ( )
{
int valor = 0;
If (primero == null)
Console.WriteLine ("Cola vacia");
else
{
valor = primero.info;
primero = primero.sgte;
}
return valor;
}
}
//si la cola esta vacía
//si la cola no está vacía
public void Mostrar ( )
{
if (primero == null)
Console.WriteLine ("Cola vacia");
else
{
Nodo puntero;
puntero = primero;
do
{
Console.WriteLine ("{0}\t", puntero.info);
puntero = puntero.sgte;
}
while (puntero != null);
}
}
// Fin de la clase Cola
3. Sustituir la función “Main” del proyecto con el siguiente código de prueba:
public static void Main ( )
{
Cola micola = new Cola ( );
Console.WriteLine ("Colocando 5 elementos en la cola...");
micola.encolar (3);
Programación IV. Guía No. 13
5
micola.encolar (27);
micola.encolar (5);
micola.encolar (22);
micola.encolar (23);
micola.Mostrar ( );
Console.WriteLine ("Retirando 2 elementos de la cola...");
micola.desencolar ( );
micola.desencolar ( );
micola.Mostrar ( );
Console.WriteLine ("Se retiro el elemento:{0}", micola.desencolarValor ( ));
micola.Mostrar ( );
Console.ReadLine ( );
}
4. Ejecutar el proyecto y ver sus resultados.
Análisis de resultados
Ejercicio 1.
Desarrollar en una interfaz gráfica de formulario (Windows Forms) la implementación de las
clases nodo y cola para implementar una cola de prioridad. Se sugiere tomar el código del
ejemplo y hacer las modificaciones necesarias para manipular una cola de prioridad.
Ejercicio 2.
En una unidad de emergencia, se atienden personas lesionadas tomando en cuenta el orden de
llegada y la gravedad de la lesión.
Implemente una solución en una aplicación de C# (usando colas de prioridad y una interfaz
gráfica de formulario (Windows Forms)) que lleve un orden de atención para los pacientes,
teniendo en cuenta las siguientes condiciones:
a. Entrada de pacientes: selección de la gravedad de la lesión e ingreso del paciente a la
cola tomando como datos: nombre del paciente, la gravedad de la lesión y descripción
de la lesión.
6
Programación IV. Guía No. 13
b. Visualización de cola de pacientes: visualizar el orden de atención de los pacientes
detallando la gravedad de las lesiones.
c. Atención de paciente: se descarga al paciente de la cola mostrando los datos
recogidos en la “Entrada de pacientes” para su atención inmediata.
Investigación Complementaria
Para la siguiente semana:
Realizar la implementación en una interfaz gráfica de formulario (Windows Forms) de la
estructura de datos para simulación de eventos: Cola Binomial (se recomienda hacer un
simulador).
El simulador debe tener un menú que permita realizar las siguientes operaciones:
A. Insertar elemento a la cola.
B. Encontrar mínimo elemento.
C. Extraer mínimo elemento.
D. Disminuir clave.
A continuación se muestran imágenes de ejemplo de cómo podría lucir su simulador:
Programación IV. Guía No. 13
7
8
Programación IV. Guía No. 13
Programación IV. Guía No. 13
Guía 13: Colas de Prioridad.
Hoja de cotejo:
Alumno:
Máquina No:
Docente:
GL:
9
13
Fecha:
EVALUACIÓN
%
CONOCIMIENTO
Del 20
al 30%
APLICACIÓN
DEL
CONOCIMIENTO
Del 40%
al 60%
ACTITUD
Del 15%
al 30%
TOTAL
100%
1-4
5-7
8-10
Conocimiento
deficiente
de los
fundamentos
teóricos
Conocimiento
y explicación
incompleta de
los
fundamentos
teóricos
Conocimiento
completo y
explicación
clara de los
fundamentos
teóricos
No tiene
actitud
proactiva.
Actitud
propositiva y
con
propuestas no
aplicables al
contenido de
la guía.
Tiene actitud
proactiva y
sus propuestas
son concretas.
Nota