algorithm - 堆栈问题 : pop out in a pattern

Question

在运行时我想输入两种类型的数据类型，double 和 string。 其中一个条件是 String 应该按照我输入的顺序弹出，而 double 将按照通常的堆栈行为 LIFO 弹出。另一个条件是堆栈限制为最大大小 10

例如一个运行时示例

输入 Hello 1 World 2 blah blah 3 4 5

输出 Hello 5 World 4 blah blah 3 2 1

我的第一个问题是有多少种方法可以解决这个问题？ 我使用 3 个堆栈解决了这个问题，一个存储 double ，一个存储字符串，一个用于反转字符串顺序。

我需要保存模式以便程序知道 double 的顺序，因此我将模式保存到字符串堆栈。由于堆栈的大小限制为 10，因此我需要以另一种方式保存模式。

这就是我的字符串堆栈在推送后的样子

1. 你好*
2. 世界*
3. 废话
4. 等等***

因此，在第一次阅读时，我需要在堆栈位置进行特定阅读，然后从中提取 Hello。当我告诉程序下一个 pop 是 double 时，星号 * 留待以后使用。

我的第二个问题是我想知道是否有其他更优雅的解决方案来解决这个问题。因为我的解决方案将涉及一些字符串操作来解决这个问题。至于现在，我实际上并没有在字符串大小写中使用 pop 函数，因为它应该被使用。顺便说一句，我用 C++ 做了解决方案。

Answer 1

你所做的很好，除了如果你必须使用一个堆栈，那么你就不能访问堆栈中的随机位置——你只能压入/弹出——而且修改输入字符串并在其中存储星号也不是很好。

您可以使用 仅 5 个堆栈的推/弹出操作来解决此问题(从技术上讲，一次只能使用 4 个，但由于它们的类型不同，您需要声明所有 5 个在你的程序中):

堆栈 1:按输入顺序压入 double

堆栈 2:按输入顺序压入字符串

堆栈 3:按输入顺序推送数据类型( double 或字符串)

堆栈 4:反转堆栈 2 中字符串的顺序

堆栈 5:反转堆栈 3 中数据类型的顺序

现在从堆栈 5 中一次弹出一个数据类型，如果是 double 型，则从堆栈 1 弹出，否则从堆栈 5 弹出，并打印弹出的值。

编辑:@jleedev 提出了一个很好的观点，即当堆栈大小受到限制时，没有通用的解决方案。我上面描述的内容假设您被允许使用多个堆栈，并且每个堆栈可以容纳与输入中存在的项目一样多的项目。