Creating a Stack like behavior is JavaScript/Node

Question

So I have a block of code that looks like this:

  stack.forEach(function(element){
    //sys.puts(sys.inspect(element, false, null));
    console.log('-----element start-----');
    console.log(element.type + ':' + element.raw);
    console.log('-----element end-----');

    if(element.children){
      element.children.forEach(function(childElement){
        stack.push(childElement);
      });
    }
  });

The issue is that this is not behaving like I would except a stack to behave and wondering if this in an issue with JavaScript itself. The issue I am seeing if that when I call the stack.push for each child to add it to the stack for processing, the initial stack.forEach() does not seem to be picking it up and it is only logging to top level elements. If I try to do another stack.forEach() directly after this one, it then displays the next level of child elements so I know .push is diffidently adding the child elements to the stack.

It almost seems like .forEach() grabs the data as it is and does not get an updates if they happen within the foreach. Is this true for JavaScript? Is there a different way I can accomplish the same thing (be able to process a top level element and all levels of children elements below it)?

HBP · Accepted Answer · 2012-10-24 13:26:03Z

3

Your supposition is correct. The ForEach function takes a snapshot of the array and any updates will not be processed.

You are trying to implement a classic tree traversal algorithm which can most easily be coded as a recursive function as follows :

  var stack = [];

  function traverse (element) {
    //sys.puts (sys.inspect(element, false, null));
    console.log ('-----element start-----');
    console.log (element.type + ':' + element.raw);
    console.log ('-----element end-----');

    stack.push (element);  // for preorder traversal (parent before children)

    if (element.children)
      element.children.forEach (traverse);

    // stack.push (element);  // for postorder traversal (children before parent)
  };

  traverse (document.body);  // for example

answered Oct 24, 2012 at 13:26

HBP

16.1k6 gold badges30 silver badges34 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Bergi Over a year ago

That's not entirely true: Only a snapshot of the length is taken, if you delete/splice or modify array items the behaviour changes.

Bergi · Accepted Answer · 2012-10-24 17:22:41Z

1

Yes, .forEach does only iterate over the range the array initially has, it works with a copy of the .length value. If you want to change that behavior, I'd recommend a classical loop which queries the length property each time:

var stack = […];
for (var i=0; i<stack.length; i++) {
    // process stack[i]
    stack.push(…);
}

or even a more list-like behavior with

var stack = […];
while (stack.length) {
    var cur = stack.shift();
    // process cur
    stack.push(…); // with variable arguments, you want to stop somewhen :-)
}

If you don't want/need to maintain the stack yourself, a recursive function is the proper choice for tree traversal.

answered Oct 24, 2012 at 17:22

Bergi

671k162 gold badges1k silver badges1.5k bronze badges

Collectives™ on Stack Overflow

Creating a Stack like behavior is JavaScript/Node

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related