javascript - Checking if this is a Stack/DFS

Question

I'm doing some work that involves grabbing some specific nodes in a tree-like structure. My colleague claims that my implementation, which we are trying to use a stack and a DFS algorithm, is not that.

Here is my implementation of using a stack to create a basic DFS algorithm:

const findMatchingElements = (node, name, result) => {
  for(const child of node.children) {
    findMatchingElements(child, name, result)
  }
  if(node.name === name) result.push(node)
  return result
}

const getElements = (tree, name) => {
  return findMatchingElements(tree, name, [])
}

getElements(obj, 'foo')

And a sample input:

const obj = {
  id: 1,
  name: 'foo',
  children: [
    {
      id: 45,
      name: 'bar',
      children: [
        {
          id: 859,
          name: 'bar',
          children: []
        }
      ]
    },
    {
      id: 67,
      name: 'foo',
      children: [
        {
          id: 456,
          name: 'bar',
          children: []
        },
        {
          id: 653,
          name: 'foo',
          children: []
        }
      ]
    }
  ]
}

I am getting my expected output:

 [ { id: 653, name: 'foo', children: [] },
  { id: 67, name: 'foo', children: [ [Object], [Object] ] },
  { id: 1, name: 'foo', children: [ [Object], [Object] ] } ]

In the order I expect as well, but my colleague for some reason does not think this is a proper stack implementation. Am I missing something? Is it because of the way the final answer is printed out? To me, this feels like it is a stack.

标签： javascript

Answer 1

I'm a bit confused about what you're disagreeing about here but that output looks like a stack to me if you agree that it's LIFO once the client starts using it. Right now it's just a JavaScript array, but if you start pushing and popping on it, and only doing that, then it's a JavaScript implementation of a stack.