Estoy tratando de construir mi propia pila en TypeScript y tengo problemas para implementar una función pop() que puede ejecutarse en una complejidad de tiempo O(1) para imitar la función pop() nativa de Javascript. Puedo eliminar el elemento superior, pero Javascript mantiene el índice en la pila como undefined . Para combatir esto, filtro la pila para eliminar lo indefinido, lo que genera una complejidad de tiempo O(n). Cualquier otra idea para implementar esto en O(1) es apreciada. Código actual:
public pop(): T { if (this.isEmpty()) { throw new Error('Empty Stack'); } const popped = this.storage[this.size() - 1]; this.stackSize--; delete (this.storage[this.size() - 1]); this.storage = this.storage.filter(x => x !== undefined); return popped; }No es necesario que elimine el elemento de la matriz
si simplemente llamas
this.stackSize--;implícitamente dices que lo quitaste
la cuestión es que necesita cambiar todas sus otras funciones para trabajar con índice en lugar de funciones nativas
por lo que la parte superior () debería ser como
top(){ return this.stack[this.stackSize-1] }y así...
Esto logrará O (1)
En JavaScript, puede acortar la matriz de esta manera:
this.storage.length = this.storage.length-1