CODEWITHSUNDEEP
javaarraysalgorithmstack
FuegoJohnson
FuegoJohnson

Reputation: 392

Reverse the elements in an array and push the reversed elements onto a stack using a single for loop

I've been working on an algorithm that reverses the order of an array using a single for loop and then pushes each element of the reversed array onto the stack. I've been having a hard time getting this to work properly, but I may be interpreting the instructions incorrectly. The instructions are as follows:

Describe in pseudocode an efficient algorithm for reversing the order of the numbers in A using a single for-loop that indexes through the cells of A, to insert each element into a stack, and then another for-loop that removes the elements from the stack and puts them back into A in reverse order.

I can easily reverse the order of the array, but my stack does not fill before the for loop terminates. My code:

public static void reverseAndPush(int[] a, int start, int end)
{

    for (int i = 0; i < end; i++)
    {
        int temp = a[start];
        a[start] = a[end];
        //only elements 5 and 4 get pushed to the stack
        stack.push(a[start]);
        a[end] = temp;
        start++;
        end--;
    }
}

If I remove the stack portion, the array is reversed successfully. What changes would need to be made to make this code run successfully? I think it has something to do with my execution statement i < end but nothing I've tried works correctly (lots of index out of bound exceptions). The instructions say to do in pseudocode, but I wanted to actually try and write the algorithm anyway just to play around with it.

Edit

For the second for loop, I had thought of doing something like this:

for n to 1 do
     stack.pop()

But this is assuming that I must push all the elements into the stack using the first for loop. I could be mistaken.

Upvotes: 0

Views: 2324

Answers (3)

RAZ_Muh_Taz
RAZ_Muh_Taz

Reputation: 4099

The trick here is to understand how stacks work, more specifically where items end up when you add/remove them from the stack. The stack data structure is a LIFO (last in, first out) data structure, therefore the last item you add is the first item you get when you call pop(). Here is a function to do what is being described by your question using the characteristics of a stack

public static int[] reverseArrayWithStack(int[] arrayToReverse)
{
    Stack<Integer> stack = new Stack<>();

    for(int i = 0; i < arrayToReverse.length; i++)
        stack.push(arrayToReverse[i]);

    for(int j = 0; j < arrayToReverse.length; j++)
        arrayToReverse[j] = stack.pop();

    return arrayToReverse;
}

Example

given an array of arr = {1,2,3,4,5}

1st for-loop - stack = {1,2,3,4,5}, all values are pushed onto the stack

2nd for-loop - start with index 0 again because when we pop from stack we will get back 5 therefore arr[0] = stack.pop() = 5, arr[1] = statck.pop() = 4, arr[2] = statck.pop() = 3 etc. This allows us to use the behavior of the stack's pop() method to place the items in reverse order starting at index 0.

Upvotes: 1

Sudarshana Gurusinghe
Sudarshana Gurusinghe

Reputation: 46

  1. Loop the array from the end and push each element to the stack. This should have the first element in the array as first element. In the meantime you could use another array and populate it within the same loop, which would be in reverse order

2.In the second loop, pop elements from the stack and assign it to the array from the end. This way the array would be reversed.

public static void reverseAndPush(int[] a) {

int sizeOfArray = a.length-1;
int[] tmp = new int[sizeOfArray];
for (int i = sizeOfArray; i <= 0; i--)
{
    tmp[i] = a[i];
    stack.push(a[i]);
}

for (int i = sizeOfArray; i <= 0; i--)
{
    a[i] = stack.pop();
}

}

Upvotes: 1

fjf2002
fjf2002

Reputation: 882

In Pseudocode:

FOR EACH INDEX I IN ARRAY A
    PUSH A[I]
NEXT

FOR EACH INDEX I IN ARRAY A
    POP A[I]
NEXT

Upvotes: -1

Related Questions