View
1
Download
0
Category
Preview:
Citation preview
Estructura de Datos
Pilas – Colas
Prof.: Mauricio Solar Prof.: Lorna Figueroa
Primer Semestre, 2010
Universidad Técnica Federico Santa María - Departamento de Informática
Indice
• TDA: Pilas• TDA: Colas• Colas de Prioridad• Anillos• BiColas• BiColas Circulares
Universidad Técnica Federico Santa María - Departamento de Informática
Pilas - Stack
• Una de las estructuras de datos más primitivas y más antiguas en la ciencia de los computadores.
• A pesar de ser tan simple, es esencial en los compiladores, SS.OO., etc.
• Se pueden representar como una lista lineal que crece y decrece por el mismo extremo.• El último elemento que se incorpora a la estructura, es el
único que se puede consultar y eliminar.
trabajos
LIFOEntradaSalida
Universidad Técnica Federico Santa María - Departamento de Informática
Pilas - Stack
• Es un tipo lineal de datos, secuencia de elementos de un tipo, una estructura tipo LIFO (Last In First Out) último en entrar primero en salir.
• Son un subconjunto de las listas, en donde las eliminaciones e inserciones se realizan en un solo extremo.
trabajos
LIFOEntradaSalida
Universidad Técnica Federico Santa María - Departamento de Informática
Aplicaciones de las Pilas
Aplicaciones Directas:• Histórico de páginas visitadas en un browser de web.• Secuencia de “undo” en un editor de textos.• Cadena de llamadas a métodos en JVM o medioambiente
runtime en C++• Parsers en Compiladores (reconocedores sintácticos).• SSOO.• Convertir notación infija a posfija o prefija.• Implementación de recursividad.
Aplicaciones Indirectas:• Estructuras de datos auxiliares para algoritmos • Componentes de otras estructuras de datos.
Universidad Técnica Federico Santa María - Departamento de Informática
Ejemplo – Aplicación de las pilas
• Suponga que se quiere evaluar una expresión aritmética, mediante un proceso que se basa en guardar dicha expresión en dos pilas:• una de operadores (+, -, * y /) y • otra de operandos (números naturales).
Universidad Técnica Federico Santa María - Departamento de Informática
Ejemplo – Aplicación de las pilas
• El método consiste en seguir el siguiente proceso de forma reiterada:
1. Si la pila de operadores está vacía, la cima de la de operandos contiene el resultado final.
2. En caso contrario, tomar los dos operandos de la cima de la pila y operarlos según el operador de la cima de la otra pila. El resultado colocarlo en la cima de la pila de operandos.
*-+
4231
-+
831 +
51 9
Iteración 1 Iteración 2 Iteración 3
Universidad Técnica Federico Santa María - Departamento de Informática
Definición del TAD Pilas
• Se definirá la semántica de las operaciones del TDA Pila en términos de las operaciones del TDA Lista.
• Operaciones:• CrearPilaVacía( P )• PilaVacía( P ) → B• Apilar( x, P )• Desapilar( P )• Tope( P ) → E
apilar desapilar
tope
Universidad Técnica Federico Santa María - Departamento de Informática
Definición del TAD Pilas
• CrearPilaVacía: Pila → Pila • CrearPilaVacía(P) = CrearListaVacía(P)
• Invocación: CrearPilaVacía(P)
• CrearPilaVacía: Pila → Pila • CrearPilaVacía(P) = CrearListaVacía(P)
• Invocación: CrearPilaVacía(P)
• PilaVacía: Pila → Lógico• PilaVacía(P) = ListaVacía(P)
• Invocación: PilaVacía(P)
• PilaVacía: Pila → Lógico• PilaVacía(P) = ListaVacía(P)
• Invocación: PilaVacía(P)
• Apilar: Elemento x Pila → Pila • Apilar( x, P ) = Insertar( x, Primera(P), P )
• Invocación: Apilar(x,P)
• Apilar: Elemento x Pila → Pila • Apilar( x, P ) = Insertar( x, Primera(P), P )
• Invocación: Apilar(x,P)
Universidad Técnica Federico Santa María - Departamento de Informática
Definición del TAD Pilas
• Desapilar: Pila → Pila
Desapilar( P ) {Si (no ListaVacía(P))
Eliminar( Primera(P), P )sino Error
}
• Invocación: Despilar(P)
• Desapilar: Pila → Pila
Desapilar( P ) {Si (no ListaVacía(P))
Eliminar( Primera(P), P )sino Error
}
• Invocación: Despilar(P)
Universidad Técnica Federico Santa María - Departamento de Informática
Definición del TAD Pilas
• Tope: Pila → Elemento
Tope( P ) {Si (no ListaVacía(P))
Retornar( Recuperar(Primera(P), P) )Sino Error
}
• Invocación: Tope(P)
• Tope: Pila → Elemento
Tope( P ) {Si (no ListaVacía(P))
Retornar( Recuperar(Primera(P), P) )Sino Error
}
• Invocación: Tope(P)
Universidad Técnica Federico Santa María - Departamento de Informática
Aplicaciones con TAD Pila
void MostrarPila(Pila P) {Pila p1;CrearPilaVacia( p1 )PasarPila( P, p1 ) // definirlamientras no PilaVacia( p1 ) {
Imprimir( Tope(p1) )Apilar( Tope(p1), P )Desapilar( p1 )
}}
void MostrarPila(Pila P) {Pila p1;CrearPilaVacia( p1 )PasarPila( P, p1 ) // definirlamientras no PilaVacia( p1 ) {
Imprimir( Tope(p1) )Apilar( Tope(p1), P )Desapilar( p1 )
}}
Universidad Técnica Federico Santa María - Departamento de Informática
Pila PasarPila( Pila Origen ) {Pila Dest;mientras (no PilaVacia( Origen ))
Apilar( Tope(Origen), Dest )Desapilar( Origen )
}return Dest;
}
Pila PasarPila( Pila Origen ) {Pila Dest;mientras (no PilaVacia( Origen ))
Apilar( Tope(Origen), Dest )Desapilar( Origen )
}return Dest;
}
Aplicaciones con TAD Pila
Universidad Técnica Federico Santa María - Departamento de Informática
PILAS
• La representación gráfica de una pila es como la de cualquier estructura dinámica:
...
tope
NULL
Universidad Técnica Federico Santa María - Departamento de Informática
PILAS – Implementaciones
typedef struct nodoP {tElemento info;struct nodoP* sig;
}
• Las pilas se implementan como una lista enlazada simple. • El puntero de la lista (el tope) apunta al primer nodo de la
pila.
pila
tope a1a2 an….
Universidad Técnica Federico Santa María - Departamento de Informática
boolean EstaVacia (struct nodoP* tope) {return (tope → sig = = NULL);// Verdadero si está vacía
}
boolean EstaVacia (struct nodoP* tope) {return (tope → sig = = NULL);// Verdadero si está vacía
}
PILAS – Implementaciones
Universidad Técnica Federico Santa María - Departamento de Informática
PILAS – Implementaciones
void Push (tElemento x, struct nodoP* tope) {struct nodoP* q;q = (struct nodoP*) malloc (sizeof (struct nodoP));q → info = x; // almacena el elemento q → sig = tope; // enlaza al nodo con el resto tope = q; // y lo pone en la cabeza
}
void Push (tElemento x, struct nodoP* tope) {struct nodoP* q;q = (struct nodoP*) malloc (sizeof (struct nodoP));q → info = x; // almacena el elemento q → sig = tope; // enlaza al nodo con el resto tope = q; // y lo pone en la cabeza
}
Universidad Técnica Federico Santa María - Departamento de Informática
tElemento Pop (struct nodoP* tope) {struct nodoP* temp;
tElemento x;if (EstaVacía(tope))
printf (“Error: pila vacía”);else {
x = tope → info;temp = tope; // Se eliminará el tope tope = tope → sig;free(temp);return(x);
}}
tElemento Pop (struct nodoP* tope) {struct nodoP* temp;
tElemento x;if (EstaVacía(tope))
printf (“Error: pila vacía”);else {
x = tope → info;temp = tope; // Se eliminará el tope tope = tope → sig;free(temp);return(x);
}}
PILAS – Implementaciones
Universidad Técnica Federico Santa María - Departamento de Informática
Ejemplo
10 10
100
10
100
1000
10
100
10
100
1
10
100
push(10) push(100) push(1000) pop() push(1) pop()
Universidad Técnica Federico Santa María - Departamento de Informática
Expresiones infijas, prefijas, postfijas
• Ejemplo de suma de dos operandos:• Infija → A + B (operador va entre operandos )• Prefija o polaca → + A B (operador va antes que
operandos)• Postfija o polaca inversa → A B + (operador va después de
operandos)• Solo existe una expresión prefija y una postfija para cada
expresión algebraica. • Para evaluar estas expresiones se usan las pilas.
Universidad Técnica Federico Santa María - Departamento de Informática
Notación polaca inversa (postfija)
• Para evaluar la expresión aritmética:
• Se sigue el orden indicado por las flechas, (según prioridad de operadores y uso de paréntesis).
2b b 4 a c2 a
− ± − ∗ ∗∗
(b + (b^2 – 4 * a * c) ^ 0.5) / (2 * a)
6 1 4 2 3 5 8 7
Universidad Técnica Federico Santa María - Departamento de Informática
Notación polaca inversa (postfija)
• Para eliminar esta dificultad, se hace una traducción de las expresiones aritméticas a notación postfija.
• Esta notación tiene la ventaja de que las operaciones aparecen en el orden en que se efectúa realmente la evaluación.
Universidad Técnica Federico Santa María - Departamento de Informática
Notación postfija
• La idea básica detrás de la notación de cadenas polacas es que los operadores se escriben al final y no en medio de las expresiones. • A + B se escribe como A B +. • En esta forma, el operador + se considera como una
instrucción para sumar los valores de las dos variables que lo preceden inmediatamente. Ejemplo:
• La clave de la traducción de notación infija a posfija es la prioridad de los operadores: ( ), + -, * /, ^
Universidad Técnica Federico Santa María - Departamento de Informática
Notación postfija
Reglas básicas para convertir expresiones infijas a posfijas:1. Si el elemento es un ‘(‘ se coloca directamente en la pila de
operadores.2. Si el elemento es un ‘)’, los operadores de la pila se transfieren
uno a uno, al extremo derecho de la expresión posfija hasta llegar a un ‘(‘. Este se saca pero no va a la salida.
3. Si el elemento localizado es una variable, se coloca inmediatamente en el extremo derecho de la expresión posfijaque se está creando.
4. Si el elemento es un operador y es de menor precedencia que el operador en la pila, el operador de la pila se saca y va a lasalida, continuando de esta manera hasta encontrar un ‘(‘ o hasta que el operador de la pila sea de menor precedencia. Cuando esto ocurre, el operador en turno se apila.
Universidad Técnica Federico Santa María - Departamento de Informática
Conversión infija a postfija
• Ecuación cuadrática
• En notación infija:
( -b + ( b ^ 2 – 4 * a * c ) ^ ( 1 / 2 ) ) / ( 2 * a )
• En notación postfija:
-b b 2 ^ 4 a c * * – 1 2 / ^ + 2 a * /
2b b 4 a c2 a
− ± − ∗ ∗∗
Universidad Técnica Federico Santa María - Departamento de Informática
1. Implementar la pila 2. Repetir hasta encontrar el fin de la expresión postfija
• Tomar un carácter. • Si el carácter es un operando colocarlo en la pila. • Si el carácter es un operador entonces sacar los dos
valores del tope de la pila (operando2 operando1), aplicar el operador (operando1 operador operando2) y colocar el resultado en el nuevo tope de la pila.
• Estructura de datos y organización de archivos. Mary E. Loomis. Prentice Hall. 2a Ed.
www.itlp.edu.mx/publica/tutoriales/estru1/33.htmthales.cica.es/rd/Recursos/rd99/ed99-0636-03/notacion_polaca.html
Algoritmo
Universidad Técnica Federico Santa María - Departamento de Informática
Para evaluar una expresión postfija con pilas:i = 1Mientras i < Longitud(expresion)
si expresión[i] es operandoInsertar expresion[i] en la pila
sino {es operador}Extraer dos elementos de la pilaoperarlos según el operador,insertar el resultado de nuevo en la pila
FinMientrasvalor = cimaPila
Algoritmo para evaluar una expresión postfija
Universidad Técnica Federico Santa María - Departamento de Informática
Aplicación: Invertir una Pila
nodoP InvPila(nodoP *tope) {
// Función que invierte una pilatElemento x;nodoP *tope1;while( !EstaVacia(tope) ) {
x = Pop(tope); Push(x, tope1);
}return(tope1);
}
nodoP InvPila(nodoP *tope) {
// Función que invierte una pilatElemento x;nodoP *tope1;while( !EstaVacia(tope) ) {
x = Pop(tope); Push(x, tope1);
}return(tope1);
}
Universidad Técnica Federico Santa María - Departamento de Informática
Implementación en C
#include <stdlib.h>#include <stdio.h>
typedef struct nodoP {int valor;struct nodoP *sig;
} tipoNodo;
typedef tipoNodo *pNodo;typedef tipoNodo *Pila;
// Prototipo de las funciones void Push(Pila *p, int x);int Pop(Pila *p);
#include <stdlib.h>#include <stdio.h>
typedef struct nodoP {int valor;struct nodoP *sig;
} tipoNodo;
typedef tipoNodo *pNodo;typedef tipoNodo *Pila;
// Prototipo de las funciones void Push(Pila *p, int x);int Pop(Pila *p);
Universidad Técnica Federico Santa María - Departamento de Informática
Ejemplo
• Algoritmo para encontrar el factorial de un número mediante pilas
leer n;mientras n > 1 {push(n);n = n-1;
}factorial = 1;mientras pila no está vacía
factorial = factorial * pop();
Universidad Técnica Federico Santa María - Departamento de Informática
Ejercicios
1. Evaluar, indicando en cada paso el estado de la pila:Pila p = (Pila *)malloc(sizeof(Pila));
a) Pop ( Pop ( Push ( 3, Pop ( Push ( 4, Push ( 5, Push ( 6, p ) ) ) ) ) ) )
b) EstaVacia(Pop(Pop(Push( 8,p))))
c) InvPila( Push ( 3, Pop ( Push ( 4, Push ( 5, Push ( 6, p ) ) ) ) ) ) ) )
2. Escribir una función que permita contar todos los elementos pares que están en una pila dada.
Universidad Técnica Federico Santa María - Departamento de Informática
COLASCOLAS
Universidad Técnica Federico Santa María - Departamento de Informática
Colas - queue
• Es una abstracción útil con muchos paralelismos en la vida real: colas de espera en bancos, supermercados, etc• Ello hace que su importancia sea crucial en simulaciones.
• Computacionalmente hay muchos casos en los que aparecen colas de espera, por ejemplo:• Procesos que esperan a ser ejecutados en sistemas
multitarea• Procesos batch de cálculo intensivo• Acceso a recursos compartidos (impresora)
Universidad Técnica Federico Santa María - Departamento de Informática
Colas - queue
Aplicaciones Indirectas:
• Estructuras de datos auxiliares para algoritmos.• Componentes de otras estructuras de datos.
Universidad Técnica Federico Santa María - Departamento de Informática
Colas
• Tipo de dato lineal con estructura FIFO (First In, First Out),indica que el primer elemento que se incorporó a la estructura, será el primero que salga, y el único que se puede consultar en un momento dado.
trabajos
entrada
salida
FIFO
Universidad Técnica Federico Santa María - Departamento de Informática
Colas
• Las colas son un subconjunto de las listas, en donde las eliminaciones se dan al comienzo de la lista y las inserciones al final.
• Los elementos se procesan en el orden como se reciben (similar a la cola de impresión en redes).
• Cuando se desea accesar un elemento que no está en un extremo, obligadamente se debe realizar una operación desplazamiento de los nodos anteriores (o posteriores) a él.
trabajos
entrada
salida
FIFO
Universidad Técnica Federico Santa María - Departamento de Informática
Definición del TAD Cola
• CrearColaVacía( C )• ColaVacía( C ) → B• PonerEnCola( x, C )• SacarDeCola( C )• Frente( C ) → E
encolar
desencolar
final
frente
Universidad Técnica Federico Santa María - Departamento de Informática
Definición del TAD Cola
• CrearColaVacía: Cola → Cola CrearColaVacía(C) = CrearListaVacía(C)
• Invocación: CrearColaVacía(C)
• CrearColaVacía: Cola → Cola CrearColaVacía(C) = CrearListaVacía(C)
• Invocación: CrearColaVacía(C)
• ColaVacía: Cola → LógicoColaVacía(C) = ListaVacía(C)
• Invocación: ColaVacía(C)
• ColaVacía: Cola → LógicoColaVacía(C) = ListaVacía(C)
• Invocación: ColaVacía(C)
• PonerEnCola: Elemento x Cola → Cola PonerEnCola( x, C ) = Insertar( x, Fin(C), C )
• Invocación: PonerEnCola(x, C)
• PonerEnCola: Elemento x Cola → Cola PonerEnCola( x, C ) = Insertar( x, Fin(C), C )
• Invocación: PonerEnCola(x, C)
Universidad Técnica Federico Santa María - Departamento de Informática
Definición del TAD Cola
• SacarDeCola: Cola → Cola
SacarDeCola( C ) {Si (no ListaVacía(C))
Eliminar( Primera(C), C )sino Error
}
• Invocación: SacarDeCola (C)
• SacarDeCola: Cola → Cola
SacarDeCola( C ) {Si (no ListaVacía(C))
Eliminar( Primera(C), C )sino Error
}
• Invocación: SacarDeCola (C)
Universidad Técnica Federico Santa María - Departamento de Informática
Definición del TAD Cola
• Frente: Cola → Elemento
Frente( C ) {Si (no ListaVacía(C))
retornar( Recuperar(Primera(C), C) )Sino Error
}
• Invocación: Frente(C)
• Frente: Cola → Elemento
Frente( C ) {Si (no ListaVacía(C))
retornar( Recuperar(Primera(C), C) )Sino Error
}
• Invocación: Frente(C)
Universidad Técnica Federico Santa María - Departamento de Informática
Colas - Implementación
Estructura para los nodos:
typedef struct TColas {tElemento info;struct tColas* sig;
}TColas *tCola;
info sig
Entrada de Dato
Salida de Dato
Universidad Técnica Federico Santa María - Departamento de Informática
Colas
• Representación gráfica:
...
frente
NULL
final
Por aquí se sale Por aquí entran
Universidad Técnica Federico Santa María - Departamento de Informática
Colas
• Otra representación:
Universidad Técnica Federico Santa María - Departamento de Informática
Colas
• Se dispone de un puntero más.• Cuando la cola está vacía se tiene la siguiente situación:
frente
NULL
final
Universidad Técnica Federico Santa María - Departamento de Informática
ColasINSERTAR(dato;frente;final) {
Nuevo(p); p->info = dato;
if final = = NULL {frente = p; // 1afinal = p; // 2a
}
else {final->sig = p; // 1bfinal = p; // 2b
}
p->sig = null; // 3}
INSERTAR(dato;frente;final) {Nuevo(p); p->info = dato;
if final = = NULL {frente = p; // 1afinal = p; // 2a
}
else {final->sig = p; // 1bfinal = p; // 2b
}
p->sig = null; // 3}
p
dato
final
frente
p
datonull
31a
2a
3
...
frente 1bnull
finalp
dato
2b
final
Universidad Técnica Federico Santa María - Departamento de Informática
Colas
Algoritmo Eliminar(frente) {if frente = = NULL
“cola vacía”
else {p = frente; // 1frente = frente->sig; // 2free(p); // 3
}}
Algoritmo Eliminar(frente) {if frente = = NULL
“cola vacía”
else {p = frente; // 1frente = frente->sig; // 2free(p); // 3
}}
...
frente
1 null
finalfrente23
p
frente null
Universidad Técnica Federico Santa María - Departamento de Informática
Colas - Implementación
boolean EstaVacía (tCola **frente, tCola **final) {// Verificación de cola vacía
if ((*final == NULL) && ( *frente == NULL))return( true); // Verdadero si está vacía
elsereturn (false);
}
boolean EstaVacía (tCola **frente, tCola **final) {// Verificación de cola vacía
if ((*final == NULL) && ( *frente == NULL))return( true); // Verdadero si está vacía
elsereturn (false);
}
Universidad Técnica Federico Santa María - Departamento de Informática
Colas - Implementación
void Enqueue (tCola **frente ,tCola **final) { tElemento dato;printf("Ingrese elemento "); scanf("%d",&dato);if( *frente == NULL) {
*frente=(tCola *) malloc(sizeof(tCola));(*frente)->info = dato; // los paréntesis son requeridos por(*frente)->sig = NULL; // precedencia de operandos *final = *frente;
}else {
tCola *q = (tCola *) malloc (sizeof (tCola) );q->info= dato;q->sig = NULL;*final = (*final)->sig = q;
}}
void Enqueue (tCola **frente ,tCola **final) { tElemento dato;printf("Ingrese elemento "); scanf("%d",&dato);if( *frente == NULL) {
*frente=(tCola *) malloc(sizeof(tCola));(*frente)->info = dato; // los paréntesis son requeridos por(*frente)->sig = NULL; // precedencia de operandos *final = *frente;
}else {
tCola *q = (tCola *) malloc (sizeof (tCola) );q->info= dato;q->sig = NULL;*final = (*final)->sig = q;
}}
Universidad Técnica Federico Santa María - Departamento de Informática
tElemento Dequeue (TCola **top, TCola **final) {tCola *temp;if (EstaVacia(frente,final))
printf("Error (cola vacia)");else {
tElemento x=(*frente)->info;temp = *frente;*frente = (*frente)-> sig;temp->sig=NULL;free(temp);return(x);
}}
tElemento Dequeue (TCola **top, TCola **final) {tCola *temp;if (EstaVacia(frente,final))
printf("Error (cola vacia)");else {
tElemento x=(*frente)->info;temp = *frente;*frente = (*frente)-> sig;temp->sig=NULL;free(temp);return(x);
}}
Colas - Implementación
Universidad Técnica Federico Santa María - Departamento de Informática
Ejemplo
a
a b
a b c
b c
No es necesario movertodos los elementos
a b
a b c
b c
Apuntadores al frentey al final
a
Universidad Técnica Federico Santa María - Departamento de Informática
Colas - Ejercicios
Escribir una función que, dada una cola que almacena números enteros, cuente la cantidad de múltiplos de 5 que contiene.Solución:int Mul5EnCola(tCola**frente, tCola**final) {// Contar los números múltiplos de 5 almacenados en la cola
int cont=0;tCola *aux =*frente;while (*aux!= NULL) {
int temp = Dequeue(aux, final);if(temp % 5 == 0)
cont++;}return(cont);
}
Escribir una función que, dada una cola que almacena números enteros, cuente la cantidad de múltiplos de 5 que contiene.Solución:int Mul5EnCola(tCola**frente, tCola**final) {// Contar los números múltiplos de 5 almacenados en la cola
int cont=0;tCola *aux =*frente;while (*aux!= NULL) {
int temp = Dequeue(aux, final);if(temp % 5 == 0)
cont++;}return(cont);
}
Universidad Técnica Federico Santa María - Departamento de Informática
#include <stdlib.h>#include <stdio.h>#include <malloc.h>struct tColas {
int info;struct TColas* sig;
};
typedef TColas tCola;
void Enqueue(tCola **frente, tCola **final);int Dequeue (tCola **frente, tCola **final);int Multiplos5EnCola(tCola **frente, tCola **final);int EstaVacia(tCola **final, tCola **frente);
#include <stdlib.h>#include <stdio.h>#include <malloc.h>struct tColas {
int info;struct TColas* sig;
};
typedef TColas tCola;
void Enqueue(tCola **frente, tCola **final);int Dequeue (tCola **frente, tCola **final);int Multiplos5EnCola(tCola **frente, tCola **final);int EstaVacia(tCola **final, tCola **frente);
Colas – Ejercicios
Universidad Técnica Federico Santa María - Departamento de Informática
void main() {int m5, i, max;tCola *final = NULL;tCola *frente = NULL;
// Ingresar datos a la colaprintf("Cuantos datos a ingresar? "); scanf("%d",&max);for(i=0;i < max; i++)
Enqueue(&frente,&final);// Buscar los múltiplos de 5m5= Multiplos5EnCola(&frente, &final);printf("\n\nNumeros multiplos de 5: %d",m5);getch();
}
void main() {int m5, i, max;tCola *final = NULL;tCola *frente = NULL;
// Ingresar datos a la colaprintf("Cuantos datos a ingresar? "); scanf("%d",&max);for(i=0;i < max; i++)
Enqueue(&frente,&final);// Buscar los múltiplos de 5m5= Multiplos5EnCola(&frente, &final);printf("\n\nNumeros multiplos de 5: %d",m5);getch();
}
Colas – Ejercicios
Operaciones:
A
BA
A B C
B C
B C D
C D
1.1.-- Insertar AInsertar A
2.2.-- Insertar BInsertar B
Estado de la cola:
3.3.-- Insertar CInsertar C
4.4.-- Remover ElementoRemover Elemento
5.5.-- Insertar DInsertar D
6.- Remover Elemento
Inicio: Cola Vacía
Universidad Técnica Federico Santa María - Departamento de Informática
Tipos de colas
• Colas de prioridad• Anillos • BiColas• BiColas circulares
Universidad Técnica Federico Santa María - Departamento de Informática
Tipos de colas: Colas de Prioridad
• Una cola de prioridad es una generalización de los conceptos de pila y cola en la que, tras entrar en la cola, la salida de los elementos no se basa necesariamente en el orden de llegada sino que se basa en un orden definido entre ellos.
• 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.
Universidad Técnica Federico Santa María - Departamento de Informática
Tipos de colas: Colas de Prioridad
• Los objetos se introducen de igual forma que en los casos anteriores;
• La diferencia aparece en el caso de la extracción y en la consulta del siguiente objeto a extraer. • El elemento que se saca es el menor de los que se han
introducido según la relación de orden total. • Si hay varios elementos menores, con el mismo valor, el que
se saca es aquél que se introdujo primero.
Universidad Técnica Federico Santa María - Departamento de Informática
Tipos de colas: Colas de Prioridad
• Existen dos formas de implementación:1. Añadir un campo a cada nodo con su prioridad. Resulta
conveniente mantener la cola ordenada por orden de prioridad.
cp
dato2 pr2pr1dato1... daton prn
typedef struct {// Informacion// PrioridadCola *sgte;
} Cola_Prioridad;
Universidad Técnica Federico Santa María - Departamento de Informática
Tipos de colas: Colas de Prioridad
2. Crear tantas colas como prioridades haya, y almacenar cada elemento en su cola.
I11 I12 I13P1
P2
P3
P4 I41 I42
I21
prim
ult
Frente Final
Universidad Técnica Federico Santa María - Departamento de Informática
Algunas aplicaciones de las colas de prioridad
• Gestión de procesos en un SO. 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, 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 costo mínimo, son ejemplos representativos.
Universidad Técnica Federico Santa María - Departamento de Informática
Convertir una expresión aritmética infija en postfija:Dada una expresión aritmética E formada por números y los operadores: +, -, *, / expresada en formato infijo, transformarla a formato postfijo.
Ejemplos del uso TDA Cola Prioridad
Universidad Técnica Federico Santa María - Departamento de Informática
Cola Convertir( Cola Infija ) {Cola Post; Pila P; Elem token;
CrearPilaVacia( P );CrearColaVacia( Post );CrearElem( token );REPETIR
Asignar(token, Frente(Infija)),SacarDeCola( Infija );Si Operando( token )
PonerEnCola( token, Post );SinoSi (no PilaVacia(P)) && (Prioridad(token) <= Prioridad(Tope(P))) {
PonerEnCola( Tope(P), Post )Desapilar( P )
}
Cola Convertir( Cola Infija ) {Cola Post; Pila P; Elem token;
CrearPilaVacia( P );CrearColaVacia( Post );CrearElem( token );REPETIR
Asignar(token, Frente(Infija)),SacarDeCola( Infija );Si Operando( token )
PonerEnCola( token, Post );SinoSi (no PilaVacia(P)) && (Prioridad(token) <= Prioridad(Tope(P))) {
PonerEnCola( Tope(P), Post )Desapilar( P )
}
Ejemplos del uso TDA Cola Prioridad
Universidad Técnica Federico Santa María - Departamento de Informática
Apilar( token, P );}HASTA ColaVacia( Infija )mientras (no PilaVacia(P))
PonerEnCola( Tope(P), Post );Desapilar( P );
}return Post;
}
Apilar( token, P );}HASTA ColaVacia( Infija )mientras (no PilaVacia(P))
PonerEnCola( Tope(P), Post );Desapilar( P );
}return Post;
}
Ejemplos del uso TDA Cola Prioridad
Estructuras de datos y algoritmos - 2007 - Clase 3Mg. Sergio Alejandro Gómez
Universidad Técnica Federico Santa María - Departamento de Informática
Anillos – Cola circular
• Las colas lineales tienen un grave problema:• como las extracciones sólo pueden realizarse por un
extremo, puede llegar un momento en que el apuntador A sea igual al máximo número de elementos en la cola, siendo que al frente de la misma existan lugares vacíos, y al insertar un nuevo elemento nos mandará un error de overflow (cola llena).
• Para solucionar el problema de desperdicio de memoria se implementaron las colas circulares, en las cuales existe un apuntador desde el último elemento al primero de la cola.
Universidad Técnica Federico Santa María - Departamento de Informática
Anillos – Cola circular
• Es una secuencia de elementos dispuestos de forma circular.• Los elementos pueden añadirse y eliminarse desde un único
punto llamado cabeza del anillo. • El círculo de elementos se puede rotar en ambos sentidos, de
manera que los diferentes elementos van pasando por la cabeza del anillo.
• Un anillo es, pues, una estructura en la que todo elemento tieneun sucesor y un predecesor, y hay una posición distinguida llamada cabeza del anillo.
Universidad Técnica Federico Santa María - Departamento de Informática
Anillos – Cola circular
• Estructuras con características parecidas se presentan a distintos niveles:• redes de computadores con configuraciones de anillo y
comunicación mediante paso de mensajes • las interfaces de usuario, en los intérpretes de comandos,
que suelen utilizar un buffer de entrada estructurado como un anillo de líneas que se puede recorrer para recuperar líneas introducidas con anterioridad.
Universidad Técnica Federico Santa María - Departamento de Informática
Implementación en C – Anillos
• Declaración:struct tcola {
int clave; struct tcola *sig;
};
• Creación:void crear(struct tcola **cola) {
*cola = NULL; }
• Función que devuelve verdadero si la cola está vacía:int vacia(struct tcola *cola) {
return (cola == NULL); }
Universidad Técnica Federico Santa María - Departamento de Informática
Implementación en C – Anillos
• Poner_En_Cola:void encolar(struct tcola **cola, int elem) {
struct tcola *nuevo; nuevo = (struct tcola *) malloc(sizeof(struct tcola)); nuevo->clave = elem; if (*cola == NULL)
nuevo->sig = nuevo; else {
nuevo->sig = (*cola)->sig; (*cola)->sig = nuevo;
} (*cola) = nuevo;
}
Universidad Técnica Federico Santa María - Departamento de Informática
Implementación en C – Anillos
• Sacar_De_Cola:void desencolar(struct tcola **c1, int *elem) {
struct tcola *aux; *elem = (*c1)->sig->clave; if ((*c1) == (*c1)->sig) {
free(*c1); *c1 = NULL;
} else {
aux = (*c1)->sig; (*c1)->sig = aux->sig; free(aux);
} }
Universidad Técnica Federico Santa María - Departamento de Informática
Implementación en C – Anillos
• Programa de prueba:#include <stdio.h> #include <stdlib.h> int main(void) {
struct tcola *cola; int elem; crear(&cola); if (vacia(cola))
printf("\nCola vacia!"); encolar(&cola, 100); desencolar(&cola, &elem); return 0;
}
Universidad Técnica Federico Santa María - Departamento de Informática
Tipos de colas – BiColas
• Colas en donde los nodos se pueden insertar y eliminar por ambos extremos;
• Se les llama DEQUE (Double Ended QUEue).
Universidad Técnica Federico Santa María - Departamento de Informática
TAD BiCola
• Las operaciones son las mismas que la del TAD Cola, salvo que Primero, Insertar y Eliminar son sustituidas por 2 operaciones respectivamente:• PrimeroIzquierda: TipoDeque TipoElemento• PrimeroDerecha: TipoDeque TipoElemento• InsertarIzquierda: TipoElementox TipoDeque TipoDeque• InsertarDerecha: TipoElemento x TipoDeque TipoDeque• EliminarIzquierda: TipoDeque TipoDeque• EliminarIzquierda: TipoDeque TipoDeque
Universidad Técnica Federico Santa María - Departamento de Informática
Tipos de colas – BiColas
• Existen dos variantes:
• Bicolas de entrada restringida: Son aquellas donde la inserción sólo se hace por el final, aunque se puede eliminar al principio o al final.
• Bicolas de salida restringida: Son aquellas donde sólo se elimina por el final, aunque se puede insertar al principio y al final.
Universidad Técnica Federico Santa María - Departamento de Informática
BiColas circulares
• Permite la implementación eficiente de todas las operaciones del anillo normal, y de la cola doble.
• p puede apuntar ahora sin problemas a la cabeza del anillo, ya que se puede acceder sin problemas y de forma directa al último elemento.
Universidad Técnica Federico Santa María - Departamento de Informática
BiColas circulares
• Las rotaciones tanto a derecha como a izquierda no suponen tampoco complicación alguna, ya que se tienen punteros en ambas direcciones.
Universidad Técnica Federico Santa María - Departamento de Informática
Bibliografía - Webgrafía
• Abstracción de datos1. http://www14.uniovi.es/tutorED/abstraccion/abstraccionfr.html
• Estructura de Datos2. http://www14.uniovi.es/tutorED/estlineales/estlineafr.html3. http://www14.uniovi.es/tutorED/java-c++/java-c++fr.html4. Como programar en Java. Deitel y Deitel.
• Listas 5. http://www14.uniovi.es/tutorED/estlineales/interlistafr.htm
• 6. http://oviedo3.ccu.uniovi.es/martin/EDI/ListPage.htm
Universidad Técnica Federico Santa María - Departamento de Informática
Bibliografía - Webgrafía
• Listas, pilas y colas. Ejercicios7. Fundamentos de programación. Libro de problemas. Luis
Joyanes Aguilar8. http://old.algoritmia.net/listas.htm9. Estructura de datos y organización de archivos. Mary E.
Loomis. Prentice Hall. 2a Ed.10. Pilas y Colas. Cursos Propedéuticos 2006, Programación y
Estructuras de Datos. Manuel Montes, Claudia Feregrino.
Recommended