How to write a pop function for a stack in Javascript/Typescript in O(1)-CodePudding

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

CodePudding user response：

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)

CodePudding user response：

In JavaScript, you can shorten the array like this:

this.storage.length = this.storage.length-1