合并两个已排序的堆栈

Question

我的老师给我做了以下练习：

"Given two sorted stacks, stack1 and stack2, design an algorithm to create a new sorted stack, stack3, merge between stack1 and stack2"

我在寻找解决此练习的最简单方法时遇到问题，任何人都可以向我推荐最简单的方法吗？我想也许我可以将 stack1 和 stack2 都存储到其他结构中（也许是 array？）然后继续排序，但这看起来很长，请问有没有其他简单的方法。

P.S.: 我只能使用 push 和 pop 来 insert/extract 堆栈中的一个元素。

Answer 1

关于这个问题要记住的是堆栈已经排序。作为人类，你会怎么做？

我猜你会做如下的事情：

1. 查看每个堆栈中的顶部元素并比较这两个元素。

2. 较大的（或较小的，取决于它们的排序方式）将被添加到新堆栈

3. 重复。

也许尝试将这个人类算法解释为伪代码并尝试实现它，您可能会得到一些有用的东西。我希望这能引导您朝着正确的方向前进！

Answer 2

之所以要颠倒顺序是因为一次只能访问栈顶元素进行比较和弹出。

也就是说不管stack1和stack2是降序还是升序，都需要新建两个stack。

• 第一个新堆栈 (helperStack) 是您将 compared/popped 元素推入的
• 第二个新堆栈 (sortedStack) 的唯一目的是将它们按相反的顺序排列，可以通过以下方式完成：

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

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