COLAS

Definición
Una cola es una lista de elementos en la que éstos ingresan por un extremo y se eliminan por el otro. Los elementos se eliminan de la cola en el mismo orden en el que ingresaron a ella, por esta razón, las colas, también son conocidas como estructuras FIFO (First-In, First-Out: Primero en entrar,Primero en salir).
Algunos ejemplos de colas en la vida real son: colas de personas para ingresar a un cine, colas de archivos para ser impresos, colas de pedidos en un restaurante, etc.

Representación de colas
Las colas se representan mediante el uso de arreglos unidimensionales o de listas ligadas. A continuación se presentan representaciones gráficas de las pilas utilizando para ello, arreglos unidimensionales o vectores.
Inicialmente se deben definir tres valores básicos para trabajar con colas:
• Frente, indica la posición en la que está ubicado el primer elemento de la cola
• Final, indica la posición en la que está ubicado el último elemento de la cola
• Máximo, indica el tamaño de la cola

2.2 Operaciones con colas
• Insertar un elemento, las inserciones se llevan a cabo por el final de la cola
• Eliminar un elemento, las eliminaciones se llevan a cabo por el frente de la cola
Es importante aclarar que cuando un elemento es eliminado, los demás NO se desplazan dentro de la cola, es decir, ningún elemento “sube” a ocupar la posición que ha dejado libre el elemento eliminado. De igual forma, cuando un elemento ingresa a una cola, NO “empuja” a los elementos que ya están en el interior de la estructura.

Algoritmo para insertar en una cola sencilla

Algoritmo para eliminar en una cola sencilla

Colas circulares
En este tipo de estructuras, el primer elemento puede estar precedido por el último. Los siguientes ejemplos gráficos representan el comportamiento de una cola en la cual se han eliminado de forma secuencial dos elementos (XX , YY) y luego se ingresa un nuevo elemento (PP), a pesar de que FINAL = MAX, sin embargo como la cola es circular, el último elemento queda en la posición 1:



Algoritmo para insertar en una cola circular


Algoritmo para eliminar de una cola circular

Doble cola
En este tipo de estructura los elementos pueden ser insertados o eliminados por cualquiera de los dos extremos que posee, (frente o final). La siguiente es una representación gráfica de una doble cola:

La doble flecha en cada extremo indica que se pueden insertar o eliminar elementos por cada “lado”.
Cuando sólo uno de los dos extremos recibe ambas operaciones (insertar y eliminar), se dice que tenemos un caso de Doble cola con entrada o salida restringida, así:
• Entrada restringida

• Salida restringida

Taller de vectores y matrices

Taller Nº 1 de Estructuras de Datos (Individual o en parejas), valor 10%.

Fecha de entrega: Lunes, 02 de marzo de 2009

1. Se tienen dos arreglos unidimensionales con datos no repetidos. Uno de ellos con N elementos y el otro con M elementos. Los elementos de los dos arreglos se encuentran ordenados de forma ascendente. Elabore un algoritmo que lea los dos vectores y forma uno nuevo de N + M elementos, el cual contendrá los elementos de los dos arreglos ordenados de menor a mayor. Es posible que entre ambos vectores existan elementos comunes, y en el vector resultado NO deben haber elementos repetidos.
2. Elaborar un algoritmo que genere y llene una matriz de orden M x N. luego intercambie el contenido de la primera y la última columna, de la segunda y la penúltima y así hasta obtener una matriz con columnas invertidas. Imprima ambas matrices. (Considere que M puede ser par o impar).

Evaluación 1

1. Genere y llene dos vectores A y B de tamaño M; luego genere un tercer vector C con la unión de la primera mitad del vector A y la segunda mitad del vector B. (Asuma que M es par). Ejemplo gráfico:


2. Genere y llene un vector A de tamaño M y una matriz B de tamaño M x N, luego inserte el vector A antes de la primera columna de la matriz B. Ejemplo gráfico:

Solución a evaluación 1

Ejercicios propuestos de matrices

1. Ingrese datos numéricos a una matriz cuadrada A, de orden N, luego encuentre la suma de los elementos ubicados en la diagonal principal y la suma de los elementos ubicados en la diagonal secundaria.












2. Encuentre e imprima la transpuesta de una matriz A. ()La transpuesta de una matriz se encuentra intercambiando las filas y las columnas)































3. Elabore una aplicación que lea una matriz de F filas y C columnas y calcule la suma de las filas y de columnas, dejando los resultados en dos vectores, uno con la suma de las filas y otro con la suma de las columnas. Imprima ambos vectores.
4. La siguiente imagen representa un tablero de damas. Un uno (1) representa la presencia de una ficha roja, un dos (2) representa la presencia de una ficha negra y un cero (0) representa la ausencia de ficha. Hacer una aplicación que calcule el número de fichas de cada color y el número total de fichas.













5. Elabore una matriz que contenga la información sobre ventas de N productos, grabando en la primera columna el código del artículo y en las siguientes el número de unidades vendidas durante el mes (meses de 30 días). Cada fila corresponde a los datos para un artículo; utilizar las tres columnas siguientes para calcular: promedio de ventas diarias, promedio de ventas por cada artículo y número de días en los que sí se vendió. Imprima la matriz.
6. Elabore una aplicación que entre una matriz de orden N*M elementos y muestre la suma total de los elementos ubicados en la primera fila, primera columna, última fila y última columna.
7. Dada una matriz de N filas por M columnas que debe ser leída, elaborar un algoritmo que ordene todos los elementos en forma descendente por filas.
8. En las elecciones para Alcalde del PUEBLITO PAISA se han presentado tres candidatos (A,B,C). El Pueblito se ha dividido en 5 zonas de votación. Elk reporte de votos de la zona se recibe en orden: primero la zona 1, la 2, etc.
Elabore una aplicación que:
a. Forme una matriz de 5 filas y 3 columnas que contenga, en cada fila, los votos reportados por las zonas para cada uno de los tres candidatos.
b. Encuentre el total de votos obtenidos por cada candidato y el porcentaje que éste representa.
c. Muestre un mensaje declarando ganador a un candidato, si éste obtuvo más del 50% de la votación. De lo contrario muestre un mensaje indicando: “No hay ganador”

Taller de vectores (Preparado por la docente Sixta Rosa Camacho)

TALLER VECTORES
1. Leer 5 números y crear un vector con ellos.
2. Realizar un programa que genere los números pares de 2 a 200 y llenar un vector con ellos.
3. Llenar un vector con los 10 primeros múltiplos de 3., sumar el vector
4. Crear un vector de 20 posiciones con valores diferentes. Hallar el mayor valor y su posición y el valor promedio
5. Leer un vector de N elementos. Imprimir cuantas veces se repite el elemento 25., sume los elementos de las posiciones pares. Imprimir los elementos del vector empezando por el último elemento.
6. Se tiene un vector de 15 elementos imprimir la suma y el promedio
7. De los elementos de un vector de 50 posiciones. Cuantos son: pares, impares, negativos y positivos .calcule el valor promedio del vector
8. Genere un vector de tamaño 10, con números reales leídos desde teclado. Calcule el promedio e indique cuantos elementos del vector son mayores que el promedio y cuantos menores o iguales.
9. Dado un vector con 10 elementos numéricos enteros ya almacenados, indique cuántos de ellos son múltiplos de 3
10. Se tiene un vector con las notas de un grupo de 30 estudiantes hallar e imprimir la nota más alta y la más baja. Cuantas personas perdieron y la nota promedio del grupo.
11. Hacer un diagrama que lea dos vectores de N y M posiciones. Crear un vector con la unión de ambos vectores e imprimirlos.
12. Cargar 2 vectores, uno con los códigos de los estudiantes que perdieron Estructura de Datos, el segundo con los códigos de los estudiantes que perdieron Cálculo Integral. Se pide crear otro vector formado por los códigos de los estudiantes que perdieron ambas materias. Imprimir el vector resultante.
13. Se tienen 3 vectores A, B, C de M elementos. Se debe crear otro vector NUEVO de tres elementos, donde cada elemento tenga la suma de los elementos de cada vector.
14. Lea un vector de S posiciones e inviértalo. Utilice otro Vector.
15. Dado un vector con 8 elementos y un número cualquiera, se debe colocar el número en la 5 posición del vector desplazando los demás valores hacia la derecha. La dimensión del vector es de 12.
16. Llenar un vector de 20 elementos, imprimir la posición y el valor del elemento mayor almacenado en el vector. Suponga que todos los elementos del vector son diferentes.
17. Almacenar 500 números en un vector, elevar al cuadrado cada valor almacenado en el vector, almacenar el resultado en otro vector. Imprimir el vector original y el vector resultante.
18. Almacenar 300 números en un vector, imprimir cuantos son ceros, cuántos son negativos, cuantos positivos. Imprimir además la suma de los negativos y la suma de los positivos.
19. Teniendo un vector de 95 posiciones con elementos numéricos enteros diferentes, realice un algoritmo en subprogramas que le permita:
• Buscar el elemento mayor y en qué posición lo encontró
• Calcular el promedio
• Sumar los elementos de las posiciones pares e imprimir la suma;
• Contar cuantos elementos del vector hay mayores que el promedio
• Buscar cuántos elementos del vector son mayores de 50 y menores de 100;
• Hallar cuántos elementos del vector son múltiplos de 7 los no múltiplos sumarlos.
• Llenar un vector con los elementos de las posiciones impares
• Imprimir los vectores de manera inversa.