Download - Pilas y Colas
OutlinePilas y Colas
PilasColas
Pilas y Colas
Roberto Carlos Abreu Dıaz
January 22, 2010
Roberto Carlos Abreu Dıaz Pilas y Colas
OutlinePilas y Colas
PilasColas
1 Pilas y Colas
2 PilasCodigo
3 ColasCodigo
Roberto Carlos Abreu Dıaz Pilas y Colas
OutlinePilas y Colas
PilasColas
Pilas y Colas
Los arreglos son apropiados para aplicaciones de bases dedatos: facilitan la manipulacion de la data
Operaciones para insertar, eliminar, modificar y buscarelementos son relativamente facil de implementar
Las pilas y colas, en contraste, tienen un tiempo de vida mascorto; esto es, se crean para llevar a cabo una tarea y almomento de que esta se realiza se descartan
A diferencia de los arreglos, solo se puede acceder o al ultimoelemento o al primero en cualquier tiempo: tienen accesorestringido.
Roberto Carlos Abreu Dıaz Pilas y Colas
OutlinePilas y Colas
PilasColas
Codigo
Pilas
Es una estructura de tipo LIFO (Last-In, First-Out)O UEPS : Ultimo en Entrar, Primero en Salir :-)
Es caracterizada por dos operaciones fundamentales: push (oapilar) y pop (o desapilar)Es una herramienta util para algoritmos aplicados a ciertasestructuras de datos complejas
Ayuda a recorrer un arbol binario y a buscar vertices de grafos
Los microprocesadores usan pilas: cuando una funcion sellama, su direccion de retorno y argumentos se apilan en unapila y, cuando retorna, se desapilan.
Roberto Carlos Abreu Dıaz Pilas y Colas
OutlinePilas y Colas
PilasColas
Codigo
Apilar
Codigo
// top c o n t r o l a c u a l e l emento// e s e l u l t i m o agregado
p u b l i c void a p i l a r ( i n t elem ) {i f ( top == s t a c k A r r a y . l e n g t h )
return ;s t a c k A r r a y [++top ] = elem ;
}
Roberto Carlos Abreu Dıaz Pilas y Colas
OutlinePilas y Colas
PilasColas
Codigo
Desapilar
Codigo
p u b l i c i n t d e s a p i l a r ( ) {i f ( top > 0)
return s t a c k A r r a y [ top−−];return −1;
}
Roberto Carlos Abreu Dıaz Pilas y Colas
OutlinePilas y Colas
PilasColas
Codigo
Eficiencia
Los elementos pueden ser apilados y desapilados en tiempoconstante O(1). En otras palabras, el tiempo no depende decuantos elementos esten en la pila.
Roberto Carlos Abreu Dıaz Pilas y Colas
OutlinePilas y Colas
PilasColas
Codigo
Colas
Colas
La cola (o en ingles, ’queue’) es una coleccion en la cual loselementos se mantienen por el orden de llegada. Las operacionesprincipales son adicionar, donde el elemento a anadir se almacenaal final de la cola; y eliminar, donde el elemento a eliminar se tomadel principio de la cola.
Roberto Carlos Abreu Dıaz Pilas y Colas
OutlinePilas y Colas
PilasColas
Codigo
¿Como se ve una cola en el mundo real?
Roberto Carlos Abreu Dıaz Pilas y Colas
OutlinePilas y Colas
PilasColas
Codigo
Insertar
Codigo
// Se anade a l f i n a l
p u b l i c void i n s e r t a r ( i n t elem ){
i f ( e l F i n a l == queArray . l e n g t h − 1){
e l F i n a l = −1;}queArray[++ e l F i n a l ] = elem ;numElems++;
}
Roberto Carlos Abreu Dıaz Pilas y Colas
OutlinePilas y Colas
PilasColas
Codigo
Eliminar
Codigo
// e l i m i n a a l que e s t a// en e l f r e n t e
p u b l i c i n t e l i m i n a r ( ){
i n t temp = queArray [ f r e n t e ++];i f ( f r e n t e == queArray . l e n g t h ){
f r e n t e = 0 ;}numElems−−;return temp ;
}
Roberto Carlos Abreu Dıaz Pilas y Colas
OutlinePilas y Colas
PilasColas
Codigo
Ejercicios practicos en clase
Para hacer
Clase Pila
Clase Cola
Emparejamiento de delimitadores
Roberto Carlos Abreu Dıaz Pilas y Colas