My teacher gave me the following exercise:
"Given two sorted stacks, stack1 and stack2, design an algorithm to create a new sorted stack, stack3, merge between stack1 and stack2"
I am having problems finding the easiest way to solve this exercise, can anyone recommend me the easy way to it? I thought that maybe I could store both stack1 and stack2 into some other structure (maybe an array?) and then proceed with the sorting but this looks long, I wonder if there is some other easy way.
P.S.: I can only use push and pop to insert/extract an element from the stacks.
The thing to keep in mind about this problem is that the stacks are already sorted. How would you do this as a human?
My guess is that you would do something like the following:
1. look at the top element in each stack and compare those two elements.
2. whichever is bigger(or smaller, depending on how they're sorted) will be added to the new stack
3. repeat.
Maybe try interpreting this human algorithm as psuedocode and try implementing it and you may get something that works. I hope that guides you in the right direction!