• Author / Uploaded
• Ledwin Manuel Peralta

Citation preview

INTRODUCCION En este capítulo se estudian en detalle las estructuras de datos pilas y colas que son probablemente las utilizadas y más frecuentemente en los programas más usuales. Son estructuras de datos que almacenan y recuperan sus elementos atendiendo a un estricto orden. Las pilas se conocen también como estructuras LIFO (Last-in, first-out, último en entrar-primero en salir) y las colas como estructuras FIFO (nirSt-in, First-out, primero en entrm-primero en salir). 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. Las colas se utilizan en sistemas informáticos, transportes y operaciones de investigación (entre otros), dónde los objetos, personas o eventos son tomados como datos que se almacenan y se guardan mediante colas para su posterior procesamiento. La variable utilizada para representar la cola para programar en c++ es la letra “Q” Usos concretos de la cola La utilización de este método programático es que sólo podemos acceder al primer y al último elemento de la estructura, de tal manera que los elementos sólo se pueden eliminar por el principio y sólo se pueden añadir por el final de la cola. Ejemplos de colas en la vida real serían: personas comprando en un supermercado, esperando para entrar a ver un partido de béisbol, esperando en el cine para ver una película, una pequeña peluquería, etc. La idea esencial es que son todas líneas de espera.

Representación de las colas Un elemento se inserta en la cola (parte final) de la lista y se suprime o elimina por la frente (parte inicial, cabeza) de la lista. Las aplicaciones utilizan una cola para almacenar elementos en su orden de aparición o concurrencia

Los elementos se eliminan (se quitan) de la cola en el mismo orden en que se almacenan y, por consiguiente, una cola es una estructura de tipoFIFO (first-iidfirs-out, primero en ciitrar//?primero en salir o bienprimero en llegar/primero en ser servido). Las colas se representan por listas enlazadas o por arrayas. Se necesitan dos punteros: frente (f) y final(r), y la lista o arraya de “n” elementos (LONGMAX).

En la figura la (a) representa una cola mediante un aray y la (b) mediante una lista enlazada

Las operaciones básicas de las colas son: Crear: se crea la cola vacía. Encolar (añadir, entrar, push): se añade un elemento a la cola. Se añade al final de esta. · Desencolar (sacar, salir, pop): se elimina el elemento frontal de la cola, es decir, el primer elemento que entró. · Frente (consultar, front): se devuelve el elemento frontal de la cola, es decir, el primero elemento que entró. TIPOS DE COLAS 1. Cola circular o anillo: Una cola circular o anillo es una estructura de datos en la que los elementos están de forma circular y cada elemento tiene un sucesor y un predecesor. Los elementos pueden consultarse, añadirse y eliminarse únicamente desde la cabeza del anillo que es una posición distinguida. Esta avanza en el sentido de las agujas del reloj. · ·

En la figura mostrada muestra una cola circular con un solo dato almacenado. La variable “final” es la posición en donde se hizo la última inserción. Después que se ha producido una inserción, final se mueve circularmente a la derecha. La implementación del movimiento circular se realiza utilizando la “teda” de los restos: Mover final adelante -Mover cabeza adelante cabeza

( final

+ 1) R MaxTdmQ

(frente i 1) 'o MdxTamQ

2. Cola de prioridades: Una cola de prioridades se utiliza para que los elementos se atienden en el orden indicado por una prioridad asociada a cada uno. Si varios elementos tienen la misma prioridad, se atenderán de modo convencional según la posición que ocupen.

Este tipo especial de colas tienen las mismas operaciones que las colas, pero con la condición de que los elementos se atienden en orden de prioridad. Ejemplos de la vida diaria serían la sala de urgencias de un hospital, ya que los enfermos se van atendiendo en función de la gravedad de su enfermedad. Estas colas se dividen en dos tipos *Colas de prioridades con ordenamiento ascendente: en ellas los elementos se insertan de forma arbitraria, pero a la hora de extraerlos, se extrae el elemento de menor prioridad. *Colas de prioridades con ordenamiento descendente: son iguales que las colas de prioridad con ordenamiento ascendente, pero al extraer el elemento se extrae el de mayor prioridad. Consideremos el siguiente ejemplo como un numero de 15 hijos y se ordena segur la prioridad de: como es mayor que, se intercambia con este, y como es mayor que, también se intercambia con este, y el proceso termina porque es menor que.

3. Doble Cola(bicola): es un tipo de cola especial que permiten la inserción y eliminación de elementos de ambos extremos de la cola. Puede representarse a partir de un vector y dos índices, siendo su representación más frecuente una lista circular doblemente enlazada. Todas las operaciones de este tipo de datos tienen coste constante.

·

Existen dos tipos de la doble cola: Doble cola de entrada restringida: acepta inserciones solo al final de la cola.

·

Doble cola de salida restringida: acepta eliminaciones solo al frente de la cola.

OPERAR COLAS EN C++ Se utiliza la expresión como guía: struct nodo { int dato; struct nodo *siguiente; }; Las operaciones con las colas son: -insert (q, x): Insertar el elemento x en la parte posterior de la cola q -remove(q): Suprime el elemento delantero de la cola q -empty(q): Retorna True o false, si la cola tiene elementos o no. Tipo Cola Implementado como Arreglo

La figura de arriba, muestra la forma de implementar una cola, como arreglo, en la que cada casilla, representa una estructura compuesta por el tipo de dato a guardar (o bien otra estructura). Las variables q.rear y q.front, se van modificando cada vez que añadimos o eliminamos datos de nuestra cola. Para determinar la cantidad de elementos en cualquier momento utilizamos la expresión: Cant=q.rear-q.front+1 A continuación se presentara un ejemplo del funcionamiento de las colas, implementadas como arreglos: Supongamos que en una cola vamos a almacenar elementos de tipo carácter. insert(&q,‘A’);

q.rear=0, q.front=0 insert (&q,‘B’)

q.rear=1

q.front=0 insert (&q, ‘C’);

q.rear=2 q.front=0 remove(&q);

q.rear=2 q.front=1 remove(&q);

q.rear=2 q.front=2 insert(&q, ‘D’);

01234 q.rear=3 q.front=2 insert(&q, ‘E’);

q.rear=4 q.front=2 Ejercicios 1.- Realizar un programa que pueda almacenar cierto número de enteros en una estructura de tipo Cola, diseñe una solución que permita, leer, eliminar datos de la cola.

#include #include #include /*declaracion de la cola*/ struct nodo { int elemento; struct nodo *siguiente; }; typedef struct nodo Nodo; typedef struct { Nodo *frente; Nodo *final; }Cola; /*declaracion de las funciones*/ void CrearCola(Cola *cola); void insert (Cola *cola, int x); int remover(Cola *cola); int empty(Cola cola); main() { int x, opc=8, j=0; Cola cola; CrearCola(&cola); clrscr(); while(opc!=3) { printf("\t\t\tMENU PRINCIPAL\n\n\n"); printf("\t 1. Insertar\n");

printf("\t 2. Eliminar\n"); printf("\t 3. Salir\n"); scanf("%d", &opc); switch(opc) { case 1: printf("Ingrese el numero a introducir:\n"); scanf("%d", &x); insert(&cola, x); ++j; break; case 2: printf("%d fue eliminado de la cola\n", remover(&cola)); --j; getch(); break; } clrscr(); } getch(); return 0; } /*definicion de las funciones*/ void CrearCola(Cola *cola) { cola->frente=cola->final=NULL; } /*funcion que inserta el dato en la parte final de la cola*/ void insert (Cola *cola, int x) { Nodo *nuevo; nuevo=(Nodo*)malloc(sizeof(Nodo)); nuevo->elemento=x; nuevo->siguiente=NULL; if(empty(*cola)) { cola->frente=nuevo; } else cola->final->siguiente=nuevo;

cola->final=nuevo; } /*elimina el elemento que esta aL frente de la cola*/ int remover (Cola *cola) { int temp=NULL; if(!empty(*cola)) { Nodo *nuevo; nuevo=cola->frente; temp=cola->frente->elemento; cola->frente=cola->frente->siguiente; free(nuevo); } else printf("ERROR, cola vacia, se puede eliminar\a\n"); return (temp); } int empty(Cola cola) { return (cola.frente==NULL); } 2.- En

este .cpp se pide el ingreso por teclado de un conjunto de datos de manera iterativa hasta que se ingrese la palabra "fin" cuando la consola pida el dato "Nombre". Una vez finalizado el ingreso, y si hay datos en la cola, se procede a mostrarlos navegando mediante las estructuras (struct). Cada estructura contiene la posición de memoria de la estructura siguiente en la cola, por lo que se las recorrerá hasta el final y se las irá eliminando de la memoria (ya que conceptualmente un nodo debe leerse de memoria una única vez). 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12.

#include #include #include #include struct agenda { char nombre[50]; char telefono[25]; char mail[50]; };

13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60.

struct nodo { struct agenda dato; struct nodo *proximo; }; struct nodo *nuevonodo(); int colavacia(struct nodo *); struct nodo *creacola(struct nodo *, struct agenda); void mostrar(struct nodo *); void main() { struct nodo *pri=NULL, *ult=NULL; struct agenda x; printf("Ingrese nombre: "); gets(x.nombre); while(strcmpi(x.nombre,"fin")) { printf("Ingrese telefono: "); gets(x.telefono); printf("Ingrese mail: "); gets(x.mail); ult=creacola(ult,x); if(pri==NULL) pri=ult; // Si es la 1º pasada pongo en pri el valor del primer nodo printf("Ingrese nombre: "); gets(x.nombre); } if(colavacia(pri)==1) { printf("No se ingresaron registros"); getch(); } else mostrar(pri); } struct nodo *nuevonodo() { struct nodo *p; p=(struct nodo *)malloc(sizeof(struct nodo)); if(p==NULL) { printf("Memoria RAM Llena"); getch(); exit(0); } return p; } struct nodo *creacola(struct nodo *ult, struct agenda x) { struct nodo *p;

61. p=nuevonodo(); 62. (*p).dato=x; 63. (*p).proximo=NULL; 64. if(ult!=NULL) (*ult).proximo=p; // Si hay nodo anterior en prox pongo la direccion del nodo actual 65. return p; 66. } 67. 68. int colavacia(struct nodo *pri) 69. { 70. if(pri==NULL) return 1; 71. else return 0; 72. } 73. 74. void mostrar(struct nodo *pri) 75. { 76. struct nodo *aux; 77. while(pri!=NULL) 78. { 79. printf("Nombre: %s - Telefono: %s - Mail: %s\n",pri->dato.nombre,pri>dato.telefono,pri->dato.mail); 80. aux=pri; 81. pri=(*pri).proximo; 82. free(aux); 83. } 84. getch(); 85. }