En el espacio de nombres : 'System.Collections.Generic' se encuentran las clases Queue<T> y Stack<T>.
- Queue<T> : Implementa el concepto de una cola (FIFO - Fist In First Out - Primero en entrar primero en salir)
- Stack<T> : Implementa el concepto de una pila (LIFO - Last In First Out - Ultimo en entrar primero en salir)
Veamos un programa que defina objetos de estas clases y llame a sus diferentes métodos.
Programa:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace PilaCola1
{
class Program
{
static void Main(string[] args)
{
Stack<int> pila1 = new Stack<int>();
Console.WriteLine("Insertamos tres elementos en la pila:10, 25 y 70");
pila1.Push(10);
pila1.Push(25);
pila1.Push(70);
Console.WriteLine("Cantidad de elementos en la pila:"+pila1.Count);
Console.WriteLine("Extraemos un elemento de la pila:" + pila1.Pop());
Console.WriteLine("Cantidad de elementos en la pila:" + pila1.Count);
Queue<string> cola1 = new Queue<string>();
Console.WriteLine("Insertamos tres elementos en la cola:'ana', 'juan' y 'pedro'");
cola1.Enqueue("ana");
cola1.Enqueue("juan");
cola1.Enqueue("pedro");
Console.WriteLine("Cantidad de elementos en la cola:" + cola1.Count);
Console.WriteLine("Extraemos un elemento de la cola:" + cola1.Dequeue());
Console.WriteLine("Cantidad de elementos en la cola:" + cola1.Count);
Console.ReadKey();
}
}
}
Debemos importar el espacio de nombres donde están definidas las clases Queue<T> y Stack<T>:
using System.Collections.Generic;
Creamos un objeto de la clase Stack<T>, debemos indicar el tipo de datos que almacenará la pila:
Stack<int> pila1 = new Stack<int>();
Para insertar elementos en la pila utilizamos el método Push:
pila1.Push(10);
pila1.Push(25);
pila1.Push(70);
Para conocer la cantidad de elementos que almacena la colección de tipo Stack<T> accedemos a la propiedad Count:
Console.WriteLine("Cantidad de elementos en la pila:"+pila1.Count);
Para extraer un elemento de la pila llamamos al método Pop:
Console.WriteLine("Extraemos un elemento de la pila:" + pila1.Pop());
La clase Queue<T> también se encuentra en el espacio de nombres 'System.Collections.Generic' y creamos un objeto mediante la sintaxis:
Queue<string> cola1 = new Queue<string>();
Para insertar elementos empleamos el método Enqueue:
cola1.Enqueue("ana");
cola1.Enqueue("juan");
cola1.Enqueue("pedro");
Y extraemos mediante el método Dequeue:
Console.WriteLine("Extraemos un elemento de la cola:" + cola1.Dequeue());
También esta clase tiene una propiedad Count que indica la cantidad de elementos de la cola:
Console.WriteLine("Cantidad de elementos en la cola:" + cola1.Count);
El resultado de ejecutar este programa es:
Problema 1:
Este práctico ya lo resolvimos cuando vimos el concepto de pilas e implementamos manualmente una clase Pila y sus métodos.
Todo compilador o intérprete de un lenguaje tiene un módulo dedicado a analizar si una expresión está correctamente codificada, es decir que los paréntesis estén abiertos y cerrados en un orden lógico y bien balanceados.
Se debe desarrollar un programa que tenga las siguientes responsabilidades (clase Formula):
- Ingresar una fórmula que contenga paréntesis, corchetes y llaves.
- Validar que los ( ) [] y {} estén correctamente balanceados.
Para la solución de este problema la clase formula utilizará la clase Stack<T>.
Veamos como nos puede ayudar el empleo de una pila para solucionar este problema.
Primero cargaremos la fórmula en un TextBox.
Ejemplo de fórmula: (2+[3-12]*{8/3})
El algoritmo de validación es el siguiente:
Analizamos caracter a caracter la presencia de los paréntesis, corchetes y llaves.
Si vienen símbolos de apertura los almacenamos en la pila.
Si vienen símbolos de cerrado extraemos de la pila y verificamos si está el mismo símbolo pero de apertura: en caso negativo podemos inferir que la fórmula no está correctamente balanceada, debemos controlar antes de extraerlo que la pila no este vacía.
Si al finalizar el análisis del último caracter de la fórmula la pila está vacía podemos concluir que está correctamente balanceada.
Ejemplos de fórmulas no balanceadas:
}(2+[3-12]*{8/3})
Incorrecta: llega una } de cerrado y la pila está vacía.
{[2+4}]
Incorrecta: llega una llave } y en el tope de la pila hay un corchete [.
{[2+4]
Incorrecta: al finalizar el análisis del último caracter en la pila queda pendiente una llave {.
Programa:
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
namespace ProblemaPila1
{
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}
private void button1_Click(object sender, EventArgs e)
{
Stack<char> pila1;
pila1 = new Stack<char>();
string cadena = textBox1.Text;
for (int f = 0; f < cadena.Length; f++)
{
if (cadena.ElementAt(f) == '(' || cadena.ElementAt(f) == '[' || cadena.ElementAt(f) == '{')
{
pila1.Push(cadena.ElementAt(f));
}
else
{
if (cadena.ElementAt(f) == ')')
{
if (pila1.Count==0 || pila1.Pop() != '(')
{
Text = "Incorrecta";
return;
}
}
else
{
if (cadena.ElementAt(f) == ']')
{
if (pila1.Count == 0 || pila1.Pop() != '[')
{
Text = "Incorrecta";
return;
}
}
else
{
if (cadena.ElementAt(f) == '}')
{
if (pila1.Count == 0 || pila1.Pop() != '{')
{
Text = "Incorrecta";
return;
}
}
}
}
}
}
if (pila1.Count==0)
{
Text = "Correcta";
}
else
{
Text = "Incorrecta";
}
}
}
}
La clase Form1 tiene como atributos: un TextBox y un Button
En el método Click verifica si la fórmula están correctos los parentesis, corchetes y llaves.
En este analizamos la fórmula para verificar si está correctamente balanceada.En este método es donde está gran parte del algoritmo de este problema. Mostramos en el titulo del Form si la formula esta correctamente balanceada.
Definimos una pila y extraemos el contenido del TextBox:
Stack<char> pila1;
pila1 = new Stack<char>();
string cadena = textBox1.Text;
El for se repite tantas veces como caracteres tenga el TextBox.
Se deben procesar sólo los símbolos ( [ { y ) ] }.
Si el símbolo es un ( [ { de apertura procedemos a cargarlo en la pila:
if (cadena.ElementAt(f) == '(' || cadena.ElementAt(f) == '[' || cadena.ElementAt(f) == '{')
{
pila1.Push(cadena.ElementAt(f));
}
En caso de ser un ) cerrado debemos verificar si la pila está vacía o en la pila no coincide con el paréntesis de apertura '(' la fórmula está incorrecta:
if (cadena.ElementAt(f) == ')')
{
if (pila1.Count==0 || pila1.Pop() != '(')
{
Text = "Incorrecta";
return;
}
}
El mismo proceso es para los símbolos ] }.
Al finalizar el análisis de toda la cadena si la pila está vacía podemos afirmar que la fórmula está correctamente balanceada, en caso contrario quiere decir que faltan símbolos de cerrado y es incorrecta:
if (pila1.Count==0)
{
Text = "Correcta";
}
else
{
Text = "Incorrecta";
}
Es importante entender que la clase Form utiliza un objeto de la clase Stack<T> para resolver el algoritmo de verificar el balanceo de la fórmula.
Este proyecto lo puede descargar en un zip desde este enlace :ProblemaPila1.zip
Problema 2:
Este segundo problema también lo resolvimos implementando manualmente la clase Cola.
Este práctico tiene por objetivo mostrar la importancia de las colas en las Ciencias de la Computación y más precisamente en las simulaciones.
Las simulaciones permiten analizar situaciones de la realidad sin la necesidad de ejecutarlas realmente. Tiene el beneficio que su costo es muy inferior a hacer pruebas en la realidad.
Desarrollar un programa para la simulación de un cajero automático.
Se cuenta con la siguiente información:
- Llegan clientes a la puerta del cajero cada 2 ó 3 minutos.
- Cada cliente tarda entre 2 y 4 minutos para ser atendido.
Obtener la siguiente información:
1 - Cantidad de clientes que se atienden en 10 horas.
2 - Cantidad de clientes que hay en cola después de 10 horas.
3 - Hora de llegada del primer cliente que no es atendido luego de 10 horas (es decir la persona que está primera en la cola cuando se cumplen 10 horas)
Programa:
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
namespace ProblemaCola1
{
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}
private void button1_Click(object sender, EventArgs e)
{
Random ale = new Random();
int estado = 0;
int llegada = 2 + ale.Next(0, 2);
int salida = -1;
int cantAtendidas = 0;
Queue<int>cola = new Queue<int>();
for (int minuto = 0; minuto < 600; minuto++)
{
if (llegada == minuto)
{
if (estado == 0)
{
estado = 1;
salida = minuto + 2 + ale.Next(0, 3);
}
else
{
cola.Enqueue(minuto);
}
llegada = minuto + 2 + ale.Next(0, 2);
}
if (salida == minuto)
{
estado = 0;
cantAtendidas++;
if (cola.Count!=0)
{
cola.Dequeue();
estado = 1;
salida = minuto + 2 + ale.Next(0, 3);
}
}
}
label1.Text = "Atendidos:" + cantAtendidas.ToString();
label2.Text = "En cola:" + cola.Count.ToString();
label3.Text = "Minuto llegada:" + cola.Count.ToString();
}
}
}
La clase Form1 define tres objetos de la clase Label para mostrar los resultados de la simulación.
El método más importante es el click del botón, veamos las distintas partes de dicho método:
Random ale = new Random();
int estado = 0;
int llegada = 2 + ale.Next(0, 2);
int salida = -1;
int cantAtendidas = 0;
Queue<int>cola = new Queue<int>();
La variable estado almacena un cero si el cajero está libre y un uno cuando está ocupado.
La variable llegada almacena en que minuto llegará el próximo cliente (debemos generar un valor entre 2 y 3)
La variable salida almacenará en que minuto terminará el cliente de ser atendido (como al principio el cajero está vacío inicializamos esta variable con -1)
Llevamos un contador para saber la cantidad de personas atendidas (cantAtendidas)
Luego definimos un objeto de la clase Cola para poder almacenar las personas que llegan al cajero y se lo encuentran ocupado.
Creamos un objeto de la clase Random para poder utilizar el método Next que nos retorna un valor aleatorio en el rango que le pasamos como parámetros (si pasamos un 0 y 2 luego nos puede retornar un 0 o un 1)
Disponemos un for que se repita 600 veces (600 minutos o lo que es lo mismo 10 horas)
for (int minuto = 0; minuto < 600; minuto++)
Dentro del for hay dos if fundamentales que verifican que sucede cuando llega una persona o cuando una persona se retira:
if (llegada == minuto)
{
............
}
if (salida == minuto)
{
............
}
Cuando llega una persona al cajero primero verificamos si el cajero está desocupado:
if (llegada == minuto)
{
if (estado==0)
{
Si está desocupado lo ocupamos cambiando el valor de la variable estado y generando en que minuto esta persona dejará el cajero (un valor aleatorio entre 2 y 4 minutos):
estado = 1;
salida = minuto + 2 + ale.Next(0, 3);
Si el cajero está ocupado procedemos a cargar dicha persona en la cola (insertamos el minuto que llega):
else
{
cola.Enqueue(minuto);
}
Luego generamos el próximo minuto que llegará otra persona:
llegada = minuto + 2 + ale.Next(0, 2);
El otro if importante es ver que sucede cuando sale la persona del cajero:
if (salida == minuto) {Si sale una persona del cajero cambiamos el valor de la variable estado, incrementamos en uno el contador cantAtendidos y si la cola no está vacía extraemos una persona, cambiamos a uno la variable estado y generamos en que minuto dejará esta persona el cajero:
estado = 0;
cantAtendidas++;
if (cola.Count!=0)
{
cola.Dequeue();
estado = 1;
salida = minuto + 2 + ale.Next(0, 3);
}
Fuera del for actualizamos las tres Label:
label1.Text="Atendidos:" + cantAtendidas.ToString();
label2.Text="En cola" + cola.Cantidad().ToString();
label3.Text="Minuto llegada:" + cola.Extraer().ToString();
Este proyecto lo puede descargar en un zip desde este enlace :ProblemaCola1.zip