I am trying to build my own stack in TypeScript and I am having trouble implementing a pop() function that can run in O(1) time complexity to mimic Javascript's native pop() function. I am able to delete the top-most item, but Javascript keeps the index in the stack as undefined. To combat this, I filter the stack to remove undefined, causing O(n) time complexity. Any other ideas to implement this in O(1) is appreciated. Current code:
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;
}
You don't need to actually remove the item from the array
if you simply call
this.stackSize--;
you implicitly say that you removed it
the thing is that you need to change all of your other functions to work with index instead of native functions
so the top() should be like
top(){
return this.stack[this.stackSize-1]
}
and so on...
This will achieve O(1)
In JavaScript, you can shorten the array like this:
this.storage.length = this.storage.length-1