La pila directa sobre nodos guarda cima y
n, y no usa nodoEn ni las posiciones del medio. Las
dos líneas de punteros de apilar quedan a la vista, y su orden
no es libre.
1. Las dos líneas al revés
La pila tiene 5 1 8 leído desde
cima y llega apilar(3), pero escrito al revés:
cima = nuevo; primero y
nuevo->siguiente = cima; después. ¿Qué queda?
2. Cuántos punteros escribe cada operación
Contando solo las escrituras de puntero de la
estructura, las que cambian cima o el campo
siguiente de un nodo, ¿cuántas hace cada operación?
apilar
desapilar
tope
Lo que quedó
Las tres operaciones escriben dos punteros, uno y
ninguno, y ninguna depende de cuántos elementos haya: Θ(1) las tres, con
Θ(n) de espacio y un puntero por elemento. Lo que no es libre es el orden:
cada línea lee el valor que la anterior dejó, así que el nodo nuevo tiene
que tomar la cadena antes de que cima lo tome a él, y en
desapilar el nodo que sale se guarda antes de mover
cima porque después del delete ya no se puede
leer.