algorithm - 将 2 个堆栈的所有值添加到 1 个堆栈并对其进行排序

Question

有 3 个堆栈 - A、B、C

堆栈 A 和 B 已排序（堆栈顶部的数字最大）。Stack C is Empty 只允许 5 次操作：

push
pop 
top 
is_empty
create

我们需要编写一个函数来接收堆栈 A 和 B，将堆栈 A 和 B 中的所有数字移动到堆栈 C 并且堆栈 C 必须排序（最大的数字在顶部）。

Answer 1

对于第一次切割，将问题分成两部分：

• 将元素从 A 和 B 移到 C 中，最小的元素在顶部。
• 将顶部元素最少的 C 转换为顶部元素最高的 C，即颠倒排序顺序。

一旦你有了这个，你可以看看是否有更好/更有效的算法。

Answer 2

查找河内的塔，一个标准的问题/谜题。

Answer 3

随着堆栈的排序，您可以应用合并排序机制。我的想法类似于user1930928。但是添加这个是为了更清晰和扩展数据反转。

算法如下

1. 比较 A 的顶部和 B 的顶部

2. 弹出最少元素并推入堆栈 C

3. 重复步骤 2，直到任何堆栈（A 或 B）变为空

4. 将剩余元素从非空堆栈移动到 C。现在您拥有 C 中的所有元素，但按升序排列。（这是顶部的最少元素）。

5. 将所有元素从 C 移动到 A。（A 中的内容按降序排列）

6. 将所有元素从A移动到B。（B中的内容按升序排列）

7. 将所有元素从 B 移动到 C。

现在 C 的内容是按降序排序的，这是期望的结果。

我鼓励你尝试编写程序。如果你真的想，我可以写。