PARTE 5

Pilas

Acceso limitado al ultimo elemento insertado ´
Operaciones basicas: ´ apilar, desapilar y cima.
desapilar o cima en una pila vacıa es un error en el TDA pila.
Quedarse sin espacio al apilar es un error de implementacion. ´
Cada operacion deberıa tardar una cantidad constante de tiempo
en ejecutarse.
Con independencia del numero de elementos apiladas.

Colas

Operaciones basicas: ´ insertar, quitarPrimero y primero.
Cada rutina deber´ıa ejecutarse en tiempo constante.
Implementacion circular a base de vectores (i) ´

La implementacion circular devuelve ´ cabeza y fin al principo del
vector cuando rebasan la ultima posici ´ on. ´
final
1) Crear Cola (C)
c
Implementacion circular a base de vectores (i) ´
La implementacion circular devuelve ´ cabeza y fin al principo del
vector cuando rebasan la ultima posici ´ on. ´
final
1) Crear Cola (C)
cabeza
final
2) Insertar en Cola (a,C) a
cabeza

Listas

Operaciones basicas: ´
Visualizar su contenido.
Buscar la posicion de la primera ocurrencia de un elemento. ´
Insertar y Eliminar un elemento en alguna posicion. ´
Buscar k esimo, que devuelve el elemento
de la posicion indicada


Implementacion de listas a base de vectores ´
Tiene que declararse el tamano de la lista. ˜
Exige sobrevaloracion. ´
Consume mucho espacio.
Complejidad computacional de las operaciones:
Buscar k esimo, tiempo constante
Visualizar y Buscar, tiempo lineal.
Insertar y Eliminar son costosas.
Insertar o eliminar un elemento exige, en promedio,
desplazar la mitad de los valores, O(n).
La construccion de una lista o la eliminaci ´ on´
de todos sus elementos podr´ıa exigir un tiempo cuadratico.

Implementacion de listas a base de apuntadores ´
Cada nodo apunta al siguiente; el ultimo no apunta a nada. ´
La lista es un puntero al primer nodo (y al ultimo). ´
Complejidad computacional de las operaciones:
Visualizar y Buscar, tiempo lineal.
Buscar k esimo, tiempo lineal.
Eliminar realiza un cambio de apuntadores y
una orden dispose, O(1).
Usa Buscar anterior cuyo tiempo de ejecucion es lineal. ´
Insertar tras una posicion´ p require una llamada a new y
dos maniobras con apuntadores, O(1).
Buscar la posicion´ p podr´ıa llevar tiempo lineal.
Un nodo cabecera facilita la insercion y la eliminaci ´ on al comienzo ´
de la lista.

Implementacion de listas doblemente enlazadas ´

Cada nodo apunta al siguiente y al anterior.

Duplica el uso de la memoria necesaria para los punteros.

Duplica el coste de manejo de punteros al insertar y eliminar.

La eliminacion se simplifica. ´

No es necesario buscar el elemento anterior.