Interview Question: Reverse Stack

I implemented it by applying bubble sort logic of swapping top two element of stack in each function call , till stack has 1 element in it. I need to do this for 'n' times, at each iteration topmost element of originals stack will be at its correct position. My code was messy.
But your code is very clean. Great video !! Thank you 🙂

since temp = stack.pop(), shouldn't temp be 3 instead of 1 since its stack is LIFO?

space also O(n). Our recursion call stack will also grow based on stack size.

why 2 functions are needed? You code actually alternates the reversing. This is enough –
public Stack<Integer> reverse(Stack s)
{
if (s.empty())
return s;
int temp = (int)s.remove(0);
reverse(s);
s.add(temp);
return s;
}

I love you

There's so many variables to keep track of in this problem in terms of what is stored in the call stack.
as soon as I start running thru the code in my head Iget lose on where/what I'm returning… no way in hell I'd ever solve this withuout just remembering pieces of the code from rot memorization.

Hi Sam, can you please explain as to why did you use return after stack.push(x). I always get confused as to what purpose does it serve here. The method is void so why do we specifically write a return. I have seen this return mentioned in many other recursion problem.

Could you use some animation while explaining it, so it would be better understood

The top level function doesn't need to be recursive, it can just be a loop, for example:

def reverse(stack):

def insert_at(elem, at):
if at == 0:
stack.append(elem)
else:
top = stack.pop()
insert_at(elem, at – 1)
stack.append(top)

for count in range(len(stack) – 1, 0, -1):
insert_at(stack.pop(), count)

Its a little less brain damaging that way.

Here is a faster algorithm in C++ that uses a combination of recursion and iteration and fulfill the conditions:

void pushToBottom(stack<int> & st, int elm, int level) {
if (st.size() <= level) {
st.push(elm);
return;
}
int x = st.top();
st.pop();
pushToBottom(st, elm, level);
st.push(x);
}

void reverse(stack<int> & st) {
const size_t size = st.size();
for (size_t i = 0; i < size; i++) {
int x = st.top();
st.pop();
pushToBottom(st, x, i);
}
}

how can i can call this reverse function in main ?

Great, but Stack is not recommended to use for years ago, use Deqeue instead

This is tough to answer in an interview without knowing about it before hand

Super Awesome..!

Where the reversed stack can be used. Can you please tell me it's real time applications

Here is my simple solution :

take 2 variables one to keep tract of bottom and another for top of stack. Traverse the stack from bottom to mid way and each time swap( stack(bott_ref) , stack( top_ref )). By the time u reach mid way all elements are revered right? What's wrong with this solution?

What stack allows you to push elements on the bottom? Kind of defeats the purpose of a stack.

Without knowing the solution, it's very hard to solve this in interview

Thanks for the video…I never understood recursion but now I am a lot more confident in recursion…
PS for anyone who wants to check/improve their recursion/stack skills,try sorting a stack in ascending/descending order using recursion.

Thank you so much for the video, Sam! Great explanation of the intuition behind the question as well as the general approach! It looks like the first line of the insertAtBottom method should be if(stack.isEmpty() || stack.peek()<x) though.

This is actually a great question to demonstrate that the call stack is not a stack in the traditional data structure sense because while it can be used to store an arbitrary type and number of values, it cannot be accessed in the same way. The call stack gives us the space we would have were we to solve the problem using another stack, but we cannot access it like a stack.

Hiya Sam, great work on these videos! Several times I noticed you mentioning the limitations of recording your session in a simple text editor and I was wondering if you have any plans to get yourself something like a Wacom tablet. Illustrations would be immensely helpful in demonstrating and clarifying your thought processes.