1

I'm trying to demonstrate some search algorithms on a webpage. DFS, BFS, and A*. The end goal is to have the user click a grid box and watch the search function light up the grid tiles as it searches them. I'm having issues getting my data structures to work properly in Javascript though. So this is my Stack prototype.

function Stack()
{
    this._size = 0;
    this._stack = {};
}
Stack.prototype.push = function(node)
{
    var size = this._size++;
    this._stack[size] = node;
}
Stack.prototype.pop = function()
{
    var size = this._size;
    if(size > 0)
    {
        var popped = this._stack[size];
        delete this._stack[size];
        this._size--;
        return popped;
    }
}
Stack.prototype.isEmpty = function()
{
    var size = this._size;
    return size <= 0;
}
Stack.prototype.stringify = function()
{
    var size = this._size
    var str = "Stack:"+ this._size + ":{";
    if(size > 0)
    {
        for(var i = 0; i < size; i++)
        {
            str = str + this._stack[i].stringify();
            if(i+1 < size)
            {
                str = str + ", ";
            }
            else
            {
                str = str + "}";
            }
        }
    }
    else
    {
        str = str + "Empty}";
    }
    return str;
}

Here is the prototype I am pushing and popping to test with

function TILE(x, y, w, h, id)
{
    this._x = x;
    this._y = y;
    this._w = w;
    this._h = h;
    this._id = id;
}
TILE.prototype.X = function(){return this._x;}
TILE.prototype.Y = function(){return this._y;}
TILE.prototype.WIDTH = function(){return this._w;}
TILE.prototype.HEIGHT = function(){return this._h;}
TILE.prototype.ID = function(){return this._id;}
TILE.prototype.stringify = function()
{
    var str = "Tile:"+this._id;
    return str;
};

Here is my test function.

function testStack()
{
    var s = new Stack();
    console.log(s.stringify());
    s.push(new TILE(10, 10, 15, 15, 69));
    console.log(s.stringify());
    s.push(new TILE(10, 10, 15, 15, 70));
    console.log(s.stringify());
    var thing = s.pop();
    console.log(s.stringify());
    console.log(thing.stringify());
}

And here is my console output

Stack:0:{Empty}
Stack:1:{Tile:69}
Stack:2:{Tile:69, Tile:70}
Stack:1:{Tile:69}
TypeError: thing is undefined

I'm somewhat new to Javascript. I understand its not really an object oriented language but it looks to me like the stack working properly up until I try to set 'popped' in TILE.js. Can anyone maybe enlighten me on what's happening here? Can Javascript prototypes be used like this?

2
  • FYI prototype.js and object.prototype are two entirely different things.
    – Liam
    Dec 7, 2015 at 13:57
  • Oh. Sorry, I didn't know. I just clicked the first prototype tag that popped up.
    – Riggy
    Dec 7, 2015 at 14:02

1 Answer 1

2

The problem is the way you increment your "pointer" size (or rather, it's how you later use that "pointer" as we'll see shortly):

var size = this._size++;
this._stack[size] = node;

You are using a postfix increment operator (++) which means in this case size gets the value of this._size before it increments. After pushing something onto your stack this._size will be 1 and the object backing your stack will have a single property 0.

When you then attempt to pop from your stack this is what you do:

var size = this._size;
if(size > 0)
{
    var popped = this._stack[size];
    delete this._stack[size];
    this._size--;
    return popped;
}

Remember we just established that this._size is 1? There's the problem. The this._stack object doesn't have a key of 1. You could subtract one from the size in the pop method to fix it:

var size = this._size - 1;
if(size > 0)
{
    var popped = this._stack[size];
    delete this._stack[size];
    this._size--;
    return popped;
}
3
  • 1
    You're absolutely right. Your fix has it working now. Thanks for the speedy reply!
    – Riggy
    Dec 7, 2015 at 14:08
  • Alternately I found I can remove this._size--; and change the top line to var size = --this._size;
    – Riggy
    Dec 7, 2015 at 14:10
  • @Riggy - Yep, that's much nicer. Good spot. Glad I could help. Dec 7, 2015 at 14:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.