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


PilasColas

1 Pilas y Colas

2 PilasCodigo

3 ColasCodigo



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.



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.



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 ;

}



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;

}



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.



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.



PilasColas

Codigo

¿Como se ve una cola en el mundo real?



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++;

}



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 ;

}



PilasColas

Codigo

Ejercicios practicos en clase

Para hacer

Clase Pila

Clase Cola

Emparejamiento de delimitadores


Business

Pilas y Colas