Merging two sorted stacks

Question

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.

Answer 1

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!

Answer 2

You just have to create a temporary stack where you keep pushing the maximum of the stacks heads until both of them are empty, and if you want it ordered in the original order direction, just push all stack elements from the temporary stack into a new stack one after another.

Answer 3

The reason you have to reverse the order is because you can only access the top elements of the stacks at a time to compare and pop.

This means that regardless of whether stack1 and stack2 are in descending or ascending order, you will need to create two new stacks.

• The first new stack (helperStack) is what you will push your compared/popped elements into
• The second new stack (sortedStack) serves the sole purpose of putting them in the reverse order which can be done by:

//reverses the order of the helperStack
//and pushes result into new sortedStack

while(!helperStack.empty())
   {
   sortedStack.push(helperStack.pop());
   }