How reverse Stack without using any (extra) data structure?

Technology Community › Category: Stacks › How reverse Stack without using any (extra) data structure?

VietMX Staff asked 3 years ago

With O(n) extra space it is trivial. A simple solution for reversing a stack is to create another stack. Pop elements from the old stack into the new stack and we will have the reversed contents in the new stack.

Without extra space, you need recursion to hold values. The idea of the solution is to hold all values in Function Call Stack until the stack becomes empty. When the stack becomes empty, insert all held items one by one at the bottom of the stack.

The reverse() function checks whether the stack is empty or not. If the stack is not empty, we pop the top element and store it in temp variable. We then call reverse() function again (first recursion) on the updated stack. When this child function returns, we call the helper function insertAtBottom().
The base case for this recursive function is:
```
if s.isEmpty(stack) :  return
```
The insertAtBottom() function (second recursion) recursively inserts an element at the bottom of a stack. If the stack is empty, it simply pushes the item else, it pops the top element and stores in the temp variable. Then call the function again on the updated stack. When this child function returns it pushes temp back in the stack.

Complexity Analysis

We are using two functions in which first function is calling itself recursively as well as the second function in each call. Also the second function is calling itself recursively, so Time complexity is O(n²).
We are storing both the functions in call stack one after another, so Space complexity is O(2n) = O(n).

Implementation

public void reverse(Stack < Integer > stack) {

    if (stack.isEmpty() == false) {

        //pop out all the items from the stack and store it in function stack
        int x = stack.pop();
        reverse(stack);

        //now insert the items into stack in reversed order
        //last item popped from the stack
        insert_at_bottom(stack, x);
    }
}

public void insert_at_bottom(Stack < Integer > stack, int x) {

    //check if stack is empty
    if (stack.isEmpty()) {
        stack.push(x);
        return;
    }
    //take out the existing items in stack and keep it in function stack
    int y = stack.pop();
    //push x to the bottom
    insert_at_bottom(stack, x);

    //push back all the items from function stack to stack
    stack.push(y);
}

Question Tags: Middle Level, Stacks