COLAS
Una cola es una estructura de datos, caracterizada por ser una secuencia de elementos en la que la operación de inserción push se realiza por un extremo y la operación de extracción pop 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.
El tipo cola representa la idea que tenemos de cola en la vida real. La cola para subir al autobús está compuesta de elementos (personas), que dispone de dos extremos comienzo y fin. Por el comienzo se extraerá un elemento cuando haya comprado el billete para su viaje, y si llega una nueva persona con intención de usar el autobús, tendrá que colocarse al final y esperar que todos los elementos situados antes que él abandonen la cola.
CODIGO PRINCIPAL
public partial class frmPrincipal { // Variables globales public static string[] Cola; public static int Frente; public static int Final; public static int N; [STAThread] public static void Main(string[] args) { Application.EnableVisualStyles(); Application.SetCompatibleTextRenderingDefault(false); Application.Run(new frmPrincipal()); } public frmPrincipal() // Constructor { InitializeComponent(); Cola = new string[5]; // Arreglo lineal de 5 N = 4; Frente = -1; Final = -1; } void CmdInsercionClick(object sender, System.EventArgs e) { frmInsercion Insercion = new frmInsercion(); Insercion.Show(); } void CmdRecorridoClick(object sender, System.EventArgs e) { frmRecorrido Recorrido = new frmRecorrido(); Recorrido.Show(); } void CmdBusquedaClick(object sender, EventArgs e) { frmBusqueda Busqueda = new frmBusqueda(); Busqueda.Show(); } void CmdEliminacionClick(object sender, EventArgs e) { frmEliminacion Eliminar = new frmEliminacion(); Eliminar.Show(); } }
Corrida
Procedimiento 1: Inserción de elemento en Cola
Algoritmo Insertar(Cola, N, Frente, Final, Elemento)
1. [¿La Cola esta llena?]
Si Frente = 0 y Final = N
Escribir: Desbordamiento y Volver
Si Frente = Final + 1
Escribir: Desbordamiento y Volver
2. [Encontrar el nuevo valor de Final]
Si Frente = -1 , entonces: [La cola esta vacía]
Hacer Frente = 0 y Final = 0
Si no, Si Final = N, entonces:
Hacer Final = 0
Si no
Hacer Final = Final + 1
[Fin del condicional]
3. Hacer Cola[Final] = Elemento
CODIGO
void CmdInsertarClick(object sender, System.EventArgs e) { elemento = txtInsercion.Text; // Se verifica que haya espacio en la Cola if (frmPrincipal.Frente == 0 && frmPrincipal.Final == frmPrincipal.N) { MessageBox.Show("La Cola esta llena"); // Desbordamiento (Overflow) return; } if (frmPrincipal.Frente == frmPrincipal.Final + 1) { MessageBox.Show("La Cola esta llena"); // Desbordamiento (Overflow) return; } // Si la cola esta vacia se inicializan punteros if (frmPrincipal.Frente == -1) { frmPrincipal.Frente = 0; frmPrincipal.Final = 0; } else if (frmPrincipal.Final == frmPrincipal.N) { frmPrincipal.Final = 0; } else { frmPrincipal.Final = frmPrincipal.Final + 1; } // Se agrega elemento a la Cola frmPrincipal.Cola[frmPrincipal.Final] = elemento; txtInsercion.Text = ""; }
corrida
Procedimiento 2: Recorrido de elementos en Cola
Algoritmo Recorrido (Cola, Frente, Final, N)
1. [¿Cola Vacía?]
Si Frente = -1 y Final = -1, entonces
Escribir: Cola Vacía (Underflow)
2. Si no, si Frente = Final, entonces:
Escribir: Cola[Frente]
3. Si no, si Final < Frente
Hacer i = Frente
Repetir Mientras i <= N
Escribir: Cola[i]
Hacer i = i + 1
Hacer j = 0
Repetir Mientras j <= Final
Escribir: Cola[j]
Hacer j = j + 1
4. Si no
Hacer i = Frente
Repetir Mientras i <= Final
Escribir: Cola[i]
Hacer i = i + 1
CODIGO
void CmdRecorridoClick(object sender, System.EventArgs e) { if (frmPrincipal.Frente == -1 && frmPrincipal.Final == -1) { MessageBox.Show("Cola Vacia"); return; } else if (frmPrincipal.Frente == frmPrincipal.Final) { lsElemCola.Items.Add(frmPrincipal.Cola[frmPrincipal.Frente]); } else if (frmPrincipal.Final < frmPrincipal.Frente) { int i = frmPrincipal.Frente; do { lsElemCola.Items.Add(frmPrincipal.Cola[i]); i = i + 1; } while (i <= frmPrincipal.N); int j = 0; do { lsElemCola.Items.Add(frmPrincipal.Cola[j]); j = j + 1; } while (j <= frmPrincipal.Final); } else { int i = frmPrincipal.Frente; do { lsElemCola.Items.Add(frmPrincipal.Cola[i]); i = i + 1; } while (i <= frmPrincipal.Final); }
Procedimiento 3: Busqueda de elemento en cola
Algoritmo Búsqueda(Elemento, Cola, N, Frente, Final)
1. [¿Cola Vacía?]
Si Frente = -1 y Final = -1, entonces
Escribir: Cola Vacía (Underflow)
2. Si no, si Frente = Final, entonces:
Si Elemento = Cola[Frente]
Escribir: Cola[Frente] y Volver
3. Si no, si Final < Frente
Hacer i = Frente
Repetir Mientras i <= N
Si Elemento = Cola[i]
Escribir: Cola[i] y Volver
Si no
Hacer i = i + 1
Hacer j = 0
Repetir Mientras j <= Final
Si Elemento = Cola[j]
Escribir: Cola[j] y Volver
Si no
Hacer j = j + 1
4. Si no
Hacer i = Frente
Repetir Mientras i <= Final
Si Elemento = Cola[i]
Escribir: Cola[i] y Volver
Si no
Hacer i = i + 1
5. Escribir: “No se encuentra elemento en cola”
CODIGO
void CmdBuscarClick(object sender, EventArgs e) { string elemento = txtBuscar.Text; txtBuscar.Text = ""; txtBuscar.Focus(); if (frmPrincipal.Frente == -1) { MessageBox.Show("Cola Vacía"); return; } if (frmPrincipal.Frente == frmPrincipal.Final) { int res = string.Compare(elemento,frmPrincipal.Cola[frmPrincipal.Frente]); if (res == 0) { lsBusqueda.Items.Add(frmPrincipal.Cola[frmPrincipal.Frente]); return; } } else if (frmPrincipal.Final < frmPrincipal.Frente) { int i = frmPrincipal.Frente; do { int res = string.Compare(elemento,frmPrincipal.Cola[i]); if (res == 0) { lsBusqueda.Items.Add(frmPrincipal.Cola[i]); return; } else i = i + 1; } while (i <= frmPrincipal.N); int j = 0; do { int res = string.Compare(elemento,frmPrincipal.Cola[j]); if (res == 0) { lsBusqueda.Items.Add(frmPrincipal.Cola[j]); return; } else j = j + 1; } while (j <= frmPrincipal.Final); } else { int i = frmPrincipal.Frente; do { int res = string.Compare(elemento,frmPrincipal.Cola[i]); if (res == 0) { lsBusqueda.Items.Add(frmPrincipal.Cola[i]); return; } else i = i + 1; } while (i <= frmPrincipal.Final); } MessageBox.Show("No se encuentra elemento en cola"); }
Procedimiento 4: Eliminación de elemento en cola
Algoritmo Eliminación (Cola, Frente, Final, N)
1. [¿Cola Vacía?]
Si Frente = -1 entonces
Escribir: "Cola Vacía" (Underflow) y Volver
2. Hacer Elemento = Cola[Frente] 3. [Encontrar el nuevo valor de Frente]
Si Frente = Final, entonces [La cola solo tenía un elemento]
Hacer Frente = -1 y Final = -1
Si no, si Frente = N, entonces
Hacer Frente = 0
Si no
Hacer Frente = Frente + 1
[Fin de la condición]
4. Escribir: “Elemento eliminado (Elemento)” 5. Volver
Código
void CmdEliminarClick(object sender, EventArgs e) { if (frmPrincipal.Frente == -1) { MessageBox.Show("Cola Vacia"); return; } string elemento = frmPrincipal.Cola[frmPrincipal.Frente]; // si la cola tiene un solo elemento if (frmPrincipal.Frente == frmPrincipal.Final) { frmPrincipal.Frente = -1; frmPrincipal.Final = -1; } else if (frmPrincipal.Frente == frmPrincipal.N) { frmPrincipal.Frente = 0; } else { frmPrincipal.Frente = frmPrincipal.Frente + 1; } lsEliminado.Items.Add(elemento); }
