Weird stack problem

[ResidentBiscuit]

For my data structures class we've been given a weird stack problem. Not sure what he's wanting. Here's the gist of it:
We're given an array with each element representing the index of the next element to visit. For example, index 0 has element 7, so we would then visit index 7. Index 7 has element 3, so we would then go to index 3. And so on. This ends at index 19, that has element -1. (Supposedly, this is how FAT works on windows).

If we output the indices as we get to them, we get the forward path through the array. As we do this, we push each visited index onto a stack. If we output each element popped of the stack, we will be given the backwards path through the array.

This is where I'm confused:

While you are popped off your stack, construct an array that will have links whose path will visit the elements in the opposite order of the original array. You should be able to start at the last element (#19) and follow the links to the first element (whick will contain a -1). Print out this array after it is constructed.

[LB]

Instead of 7 pointing to 3, 3 points to 7. Where is the confusion in this?

[ResidentBiscuit]

Is it asking to use this second array as the links to follow through the first array, or is it asking to just traverse the second array using the backwards links?

[LB]

Let's look at a simple example of 4 elements:

0 1 2 3
2 3 1 -1

Stack:

0 2 1 3

New Array:

0 1 2 3
w x y z

The first two numbers you pop off the stack are 3 and 1, so in the new array element 3 needs to be 1:

0 1 2 3
w x y 1

Then you pop off 2, so element 1 needs to be 2:

0 1 2 3
w 2 y 1

Then you pop off 0, so element 2 needs to be 0:

0 1 2 3
w 2 0 1

The stack is empty now, so element 0 needs to be -1:

 0 1 2 3
-1 2 0 1

[ResidentBiscuit]

So, the second array is populated like:

int temp = stack.pop();
while(!stack.isEmpty())
   {
      arr[temp] = stack.peek();
      temp = stack.pop();
   }
   arr[0] = -1;

?

I was originally just populating the array in a linear fashion, but your example shows that it needs to be done otherwise.

EDIT:
Well actually I don't think this will work. Pretty sure it's going to fail at the last element. Hmm

[LB]

I wouldn't hard-code assigning -1 to index 0 like that, what if a change to the problem requires to you have a different starting point? (I doubt it, but still...magic numbers seem wrong)

[ResidentBiscuit]

Ah well now that I know what exactly this problem is asking I'll give it a try when I'm at my other computer.

[cire]

It is basically a singly linked list with each link being an index into the array.

I'd handle things a bit differently than L B.

std::stack<int> stackify( const std::vector<int>& v )
{
    std::stack<int> stack ;

    std::size_t index = 0 ;
    while ( v[index] != sentinel )
    {
        stack.push(v[index]) ;
        index = v[index] ;
    }

    return stack ;
}

std::vector<int> unstackify( std::stack<int>& stack )
{
    std::vector<int> v(stack.size()+1) ;

    std::size_t index = 0 ;
    while ( !stack.empty() )
    {
        v[index] = stack.top() ;
        index = v[index] ;

        stack.pop() ;
    }
    v[index] = sentinel ;

    return v ;
}

Incidentally, I was playing around with it a bit and the following should generate random vectors following the pattern required.

std::vector<int> generate_sequence(unsigned elements)
{
    std::vector<int> v(elements) ;
    std::vector<std::size_t> index(elements-1) ;

    std::iota(index.begin(), index.end(), 1) ;
    std::shuffle( index.begin(), index.end(), std::mt19937(std::random_device()())) ;

    std::size_t i=0;
    for ( auto idx : index )
    {
        v[i] = idx ;
        i = idx ;
    }
    v[i] = sentinel ;

    return v ;
}